Sorting A Doubly Linked List (Descending Order)

Example Program To Sort A Doubly Linked List (in C):

---

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

  struct dllNode {
        int data;
        struct dllNode *previous, *next;
  };

  struct dllNode *head = NULL;
  static int totNodes = 0;

  struct dllNode *createNode(int);
  void insertNode(int);
  void deleteNode(int);
  void insertionSort();
  void traverseList();

  /* creating a new node */
  struct dllNode* createNode(int data) {
        struct dllNode *nPtr = (struct dllNode *)malloc(sizeof (struct dllNode));
        nPtr->data = data;
        nPtr->previous = NULL;
        nPtr->next = NULL;
        return (nPtr);
  }

  /* Insert a newnode at the end of the list */

  void insertNode(int data) {

        struct dllNode *tmp, *nPtr = createNode(data);

        if (!head) {

                head = nPtr;

                totNodes++;

                return;

        } else {

                tmp = head;

                while (tmp) {

                        if (tmp->next == NULL) {

                                tmp->next = nPtr;

                                nPtr->previous = tmp;

                                totNodes++;

                                return;

                        }

                        tmp=tmp->next;

                }

        }

  }

  /* delete the node with given data */

  void deleteNode(int data) {

        struct dllNode *nPtr, *tmp = head;

        if (head == NULL) {

                printf("Data unavailable\n");

                return;

        } else if (tmp->data == data) {

                nPtr = tmp->next;

                tmp->next = NULL;

                free(tmp);

                head = nPtr;

                totNodes--;

        } else {

                while (tmp->next != NULL && tmp->data != data) {

                        nPtr = tmp;

                        tmp = tmp->next;

                }

                if (tmp->next == NULL && tmp->data != data) {

                        printf("Given data unvavailable in list\n");

                        return;

                } else if (tmp->next != NULL && tmp->data == data) {

                        nPtr->next = tmp->next;

                        tmp->next->previous = tmp->previous;

                        tmp->next = NULL;

                        tmp->previous = NULL;

                        free(tmp);

                        printf("Data deleted successfully\n");

                        totNodes--;

                } else if (tmp->next == NULL && tmp->data == data) {

                        nPtr->next = NULL;

                        tmp->next = tmp->previous = NULL;

                        free(tmp);

                        printf("Data deleted successfully\n");

                        totNodes--;

                }

        }

  }

  /* sort the given list - insertNode sort*/

  void insertionSort() {

        struct dllNode *nPtr1, *nPtr2;

        int i, j, tmp;

        nPtr1 = nPtr2 = head;

        for (i = 0; i < totNodes; i++) {

                tmp = nPtr1->data;

                for (j = 0; j < i; j++)

                        nPtr2 = nPtr2->next;

                for (j = i; j > 0 && nPtr2->previous->data < tmp; j--) {

                        nPtr2->data = nPtr2->previous->data;

                        nPtr2 = nPtr2->previous;

                }

                nPtr2->data = tmp;

                nPtr2 = head;

                nPtr1 = nPtr1->next;

        }

  }

  /* traverse the doubly linked list and print data in each node */

  void traverseList() {

        struct dllNode *nPtr = head;

        int i = 0;

        while (nPtr) {

                printf("%d ", nPtr->data);

                nPtr = nPtr->next;

                i++;

        }

  }

  int main() {

        int ch, data;

        while (1) {

                printf("1.Insertion\t2.Delete Operation\n");

                printf("3.Sort List\t4.Display\t");

                printf("5.Exit\nEnter ur choice:");

                scanf("%d", &ch);

                switch (ch) {

                        case 1:

                                printf("Enter data to insert:");

                                scanf("%d", &data);

                                insertNode(data);

                                break;

                        case 2:

                                printf("Enter data to delete:");

                                scanf("%d", &data);

                                deleteNode(data);

                                break;

                        case 3:

                                insertionSort();

                                break;

                        case 4:

                                traverseList();

                                printf("\n");

                                break;

                        case 5:

                                exit(0);

                        default:

                                printf("Wrong Option!!\n");

                                break;

                }

        }

  }

Output: (Sort Doubly Linked List In Descending Order - Example in C)

  1.Insertion 2.Delete Operation
  3.Sort List 4.Display 5.Exit
  Enter ur choice:1
  Enter data to insert:100
  1.Insertion 2.Delete Operation
  3.Sort List 4.Display 5.Exit
  Enter ur choice:1
  Enter data to insert:20
  1.Insertion 2.Delete Operation
  3.Sort List 4.Display 5.Exit
  Enter ur choice:1
  Enter data to insert:300
  1.Insertion 2.Delete Operation
  3.Sort List 4.Display 5.Exit
  Enter ur choice:1
  Enter data to insert:15
  1.Insertion 2.Delete Operation
  3.Sort List 4.Display 5.Exit
  Enter ur choice:4
  100 20 300 15 
  1.Insertion 2.Delete Operation
  3.Sort List 4.Display 5.Exit
  Enter ur choice:5