What is wrong with Insertion Sort on Doubly Linked list?

Question

I am getting some random result. I have gone through the flow and did dry run several time but can't figure out exactly what's wrong with the code.

flow of program: linked list : 5 4 3 2 1

1. current is at 2nd position i.e. 4 , also storing this value to variable temp.
2. previous is at 1st position i.e. 5
3. 1st while loop runs until current becomes null.
4. 2nd nested while loop runs from predecessor of current to head node along with the condition tempdata. if condition is true then move temp to its correct position.
5. at last repeat the first loop.

#include <iostream>
using namespace std;
​
class Node {
public:
    int data;
    Node *next;
    Node *prev;
​
    Node(int data) {
    this->data = data;
    next = NULL;
    prev = NULL;
    }
};
​
void insert(Node *&head, Node *&tail, int data) {
    if (head == NULL) {
    Node *temp = new Node(data);
    temp->next = temp;
    head = temp;
    tail = temp;
    } else {
    Node *temp = new Node(data);
    tail->next = temp;
    temp->prev = tail;
    tail = temp;
    }
}
​
void display(Node *head) {
    Node *temp = head;
    while (temp != NULL) {
    cout << temp->data << " ";
    temp = temp->next;
    }
    cout << endl;
}
​
void insertionSort(Node *&head, int size) {
    Node *current = head->next;
    Node *previous; 
    while (current!= NULL) { 
    int temp = current->data;     
    previous = current->prev; 
    while (previous != head && temp < previous->data) { 
        previous->next->data = previous->data; 
        previous = previous->prev;             
    }
    previous->data = temp;   
    current = current->next; 
    }
}
​
int main() {
    Node *head = NULL;
    Node *tail = NULL;
    int size;
    int data;
    cout << "Linked-List Size: ";
    cin >> size;
    cout << "Enter Elements: ";
    for (int i = 0; i < size; i++) {
    cin >> data;
    insert(head, tail, data);
    }
    display(head);
    insertionSort(head, size);
    display(head);
}

Answer 1

Trace through your code by hand while drawing what happens:

At the start you have

temp = 4     
previous = current->prev

5 -> 4 -> 3 -> 2 -> 1
^    ^
p    c

Now previous != head is false, so the loop isn't entered, and you

previous->data = temp
current = current->next

4 -> 4 -> 3 -> 2 -> 1
^         ^
p         c

This is beginning to look bad - the 5 has disappeared...

Next iteration:

temp = 3     
previous = current->prev
    
4 -> 4 -> 3 -> 2 -> 1
     ^    ^
     p    c

previous != head && temp < previous->data is true, so enter the loop:

previous->next->data = previous->data;

4 -> 4 -> 4 -> 2 -> 1
     ^    ^
     p    c

previous = previous->prev;

4 -> 4 -> 4 -> 2 -> 1
^         ^
p         c

Now previous != head is false, exit the loop.

previous->data = temp
current = current->next

3 -> 4 -> 4 -> 2 -> 1
^              ^
p              c

And so on.

To solve this, draw your lists and what needs to happen before writing any code.
(And don't forget to handle the empty list.)