Linked List: How to Sort Doubly Linked List?

Question

This is the code for my doubly linked list. It works fine. I need help with sorting the data elements of this linked list.

#include <stdio.h>
#include <stdlib.h>

struct Node{
int data;
struct Node* next;
struct Node* prev;
};
struct Node* head;//global variable

int GetNewNode(int x)
{
struct Node* newNode=(struct Node*)malloc(sizeof(struct Node));
newNode->data=x;
newNode->prev=NULL;
newNode->next=NULL;
return newNode;
}

int InsertAtHead(int x)
{
struct Node* newNode =GetNewNode(x);
if(head==NULL)//list empty
{
    head=newNode;
    return;
}
head->prev=newNode;
newNode->next=head;
head=newNode;
}

void print()
{
struct Node* temp=head;//start printing from head
printf("Forward: ");
while(temp!=NULL)
{
    printf("%d ",temp->data);
    temp=temp->next;
}
    printf("\n");
}

   int main()
   {
   head=NULL;// initially taking it as null
   InsertAtHead(2);print();
   InsertAtHead(5);print();
   InsertAtHead(3);print();
   InsertAtHead(9);print();

   return 0;
   }

I want to sort the Data elements here. I tried this:

void sort()
{
struct Node* temp=head;
int numTemp;
while(temp!=NULL)
{
    if(temp->prev > temp->next)
    {
        numTemp=temp->next;
        temp->next= temp->prev;
        temp->prev=numTemp;
    }
}
}

But this compares the address, not the data of the linked list, How do i compare data and sort them accordingly ?

You access the data... temp->prev->data and such. Just don't dereference any NULL pointers. — StoryTeller - Unslander Monica

maigar maigar · Accepted Answer · 2017-03-29T07:35:09

head,next and prec in your Node struct are pointers and thus, they will just point to the respective node, in the same way as temp(in sort() function)is the pointer to the node you are currently accessing.

For accessing the data of node pointed by temp, you will do temp->data. Similarly, if you want to access the data of the next node(having address temp->next), you will do temp->next->data.

It seems, there is a problem with iterating through the linked list too. To iterate forward in the linked list, you have to make temp point to the next node.

while(temp!=NULL)
{
    ...
    temp=temp->next;
}

This is how you can iterate through the list.

Linked List: How to Sort Doubly Linked List?

1 Answers