This blog is under construction

Monday, 25 February 2013

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

See Also:


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



Posted by at 01:20

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)