How to insertion sort a doubly linked list in c

Question

I am trying to sort a doubly linked list by an integer value.

This is an example node:

struct Node
{

    struct Node* previous;
    struct Node* next;
    int* a;

}Node;

I was originally intending to use an insertion sort, but I am struggling severely to come up with the proper code.

My head and tail are simply struct Node* listHead and struct Node* listTail. They are both global variables.

Edit: I looked at several other posts on this topic, and I couldn't get the code to function properly. I apologize for my ineptitude.

Attempt so far:

    struct Node* key = listHead;
    struct Node* i;
    struct Node* temp;

    while(key!=NULL)
    {
        temp=key;
        iterator=key->previous;
        while(i != NULL && temp->a>i->a)
        {
            if(i->next->next!=NULL&& i->next!=NULL)
            {
                i=i->next->next;
                i=i->previous;
            }
        }
        if(i->next->next!=NULL && key->next!=NULL)
        {
        i->next->next = temp;
        key = key->next;
        }
    }

Edit: Second code attempt:

    struct Node* newHead = NULL;
    struct Node* newTail = NULL;

    struct Node* i;
    struct Node* move = listHead;
    struct Node* temp;
    while(move->next!=NULL && move!=NULL)
    {
        if(newHead==NULL)
        {
            temp=move;
            newHead=temp;
        }else if(newTail==NULL)
        {
            temp=move;
            newTail=temp;
        }else if(newHead->next->next==NULL)
        {
            temp=move;
            insert_node(newHead, newTail, temp);
        }
        else
        {
            i=newHead->next;
            while(inserter->previous!=NULL)
            {
                if(i->previous->a < i->a)
                {
                    temp=move;
                    insert_node(i->previous,i,temp);
                    break;
                }
                i=i->previous;
            }
        }
        move=move->next;
    }
    listHead=newHead;
    listTail=newTail;

This second block of code only appears to sort the last element.

My insert function:

void insert_node(struct Node* first, struct Node* last, struct Node* insert)
{
    first->next=insert;
    insert->previous=first;
    last->previous=insert;
    insert->next=last;
}

Answer 1

Create a new doubly linked list. Remove one element at a time from original doubly linked list and insert into the new doubly linked list at the correct position according to insertion sort (as you have mentioned you are using insertion sort).

I guess this is where you are having problem (while implementing this). Try to break down the problem. Learn to create a doubly linked list, insert an element in the beginning, insert an element in the end, remove element from the beginning, remove element from the ending, insert element at some specific position, remove element at some specific position, swapping two elements of the list.

Once you have learnt all this you code will break down to something like this :

1) creating a new empty doubly linked list

2) removing the last element from the original doubly linked list and inserting it into the new doubly linked list

3) removing the last element from original doubly linked list and inserting it at the correct position in the new linked list (such that the element on one side is smaller and element on other side is greater)

4) repeating set 3 till there are elements in original linked list

You just need to call the methods for the respective operations here. If you are still having issues, please try pasting your code here.

EDIT : You won't have unnecessary nodes at any time. But still, if your teacher insists to use only one list :

1) Create a new pointer A to mark the node before which you have your doubly linked list sorted (initially this will be the fist element of your original doubly linked list)

2) Now considering the value of the element at pointer A, iterate over the sorted list (that is the list before element at pointer A), find a position where element at pointer A fits (i.e. element before is smaller, element after is greater). Now insert the node pointed by pointer A at that position. And make A point to the next node element.

3) Repeat this till you reach the end.