C Program To Perform Insertion, Deletion & Sorting In Doubly Linked List

Example Program To Sort Data(Ascending Order) in a Doubly Linked List:

---

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

  struct node {
        int data;
        struct node *prev, *next;
  };

  struct node *head = NULL;
  static int node_count = 0;

  struct node *createNode(int);
  void insertNode(int);
  void deleteNode(int);
  void sortList();
  void display();

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

  /* Insert a new node at the end of the list */

  void insertNode(int data) {

        struct node *temp, *ptr = createNode(data);

        if (!head) {

                head = ptr;

                node_count++;

                return;

        } else {

                temp = head;

                while (temp) {

                        if (temp->next == NULL) {

                                temp->next = ptr;

                                ptr->prev = temp;

                                node_count++;

                                return;

                        }

                        temp=temp->next;

                }

        }

  }

  /* delete the node with given data */

  void deleteNode(int data) {

        struct node *ptr, *temp = head;

        if (head == NULL) {

                printf("Data unavailable\n");

                return;

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

                ptr = temp->next;

                temp->next = NULL;

                free(temp);

                head = ptr;

                node_count--;

        } else {

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

                        ptr = temp;

                        temp = temp->next;

                }

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

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

                        return;

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

                        ptr->next = temp->next;

                        temp->next->prev = temp->prev;

                        temp->next = NULL;

                        temp->prev = NULL;

                        free(temp);

                        printf("Data deleted successfully\n");

                        node_count--;

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

                        ptr->next = NULL;

                        temp->next = temp->prev = NULL;

                        free(temp);

                        printf("Data deleted successfully\n");

                        node_count--;

                }

        }

  }

  /* sort the given list - insertion sort*/

  void sortList() {

        struct node *ptr1, *ptr2;

        int i, j, temp;

        ptr1 = ptr2 = head;

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

                temp = ptr1->data;

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

                        ptr2 = ptr2->next;

                for (j = i; j > 0 && ptr2->prev->data > temp; j--) {

                        ptr2->data = ptr2->prev->data;

                        ptr2 = ptr2->prev;

                }

                ptr2->data = temp;

                ptr2 = head;

                ptr1 = ptr1->next;

        }

  }

  void display() {

        struct node *ptr = head;

        int i = 0;

        while (ptr) {

                printf("data in node%d : %d\n", i, ptr->data);

                ptr = ptr->next;

                i++;

        }

  }

  int main() {

        int ch, data;

        while (1) {

                printf("1.Insertion\n2.Deletion\n");

                printf("3.Sort List\n4.Display\n");

                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:

                                sortList();

                                break;

                        case 4:

                                display();

                                break;

                        case 5:

                                exit(0);

                        default:

                                printf("please enter right option\n");

                                break;

                }

        }

  }

 

Output: (Example Program To Sort Doubly Linked List In Ascending Order)

  1.Insertion
  2.Deletion
  3.Sort List
  4.Display
  5.Exit
  Enter ur choice:1
  Enter data to insert:10
  1.Insertion
  2.Deletion
  3.Sort List
  4.Display
  5.Exit
  Enter ur choice:1
  Enter data to insert:5
  1.Insertion
  2.Deletion
  3.Sort List
  4.Display
  5.Exit
  Enter ur choice:1
  Enter data to insert:100
  1.Insertion
  2.Deletion
  3.Sort List
  4.Display
  5.Exit
  Enter ur choice:1
  Enter data to insert:50
  1.Insertion
  2.Deletion
  3.Sort List
  4.Display
  5.Exit
  Enter ur choice:3
  1.Insertion
  2.Deletion
  3.Sort List
  4.Display
  5.Exit
  Enter ur choice:4
  data in node0 : 5
  data in node1 : 10
  data in node2 : 50
  data in node3 : 100
  1.Insertion
  2.Deletion
  3.Sort List
  4.Display
  5.Exit
  Enter ur choice:2
  Enter data to delete:50
  Data deleted successfully
  1.Insertion
  2.Deletion
  3.Sort List
  4.Display
  5.Exit
  Enter ur choice:4
  data in node0 : 5
  data in node1 : 10
  data in node2 : 100
  1.Insertion
  2.Deletion
  3.Sort List
  4.Display
  5.Exit
  Enter ur choice:5