This blog is under construction

Saturday 25 May 2013

Sorting A Doubly Linked List (Descending Order)

See Also:


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)
  jp@jp-VirtualBox:~/$ ./a.out
  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



No comments:

Post a Comment