C Program To Implement Doubly Linked List - Insertion, Traversal, Searching, Delete Node & Delete List

Doubly linked list is a list in which each node consists of three fields.  They are data field, pointer to previous node and pointer to successor node.
Structure of a node: struct node {
           struct node *prev;
           int data;
           struct node *next; };
                        +---------------------------------+
                        |  prev    |   data   |   next   |
                        +---------------------------------+
prev - pointer to the previous node next - pointer to the successor node
How to create a node in doubly linked list? Dynamically allocate memory for the newnode and load the given data in it.
struct node * nodeCreation(int data) {
          struct node *newnode;
          newnode = (struct node *)malloc(sizeof (struct node));
          newnode->data = data;
          newnode->next = NULL;
          newnode->prev = NULL;
          return (newnode); }
Trick to simplify doubly linked list implementation:
Create two sentinels (head and tail - dummy nodes) and establish a connection between them.  This  simplifies insertion and deletion operation in doubly linked list.

+------------------------+       +------------------------+
|  NULL |  0  |  next -|<--->|- prev |  0   | NULL |
+------------------------+       +------------------------+
           head                               tail

In this case, we don't need to do any additional operation with head and tail.  All we need to do is to insert or delete nodes that are present between dummy sentinels.  This ensures safety and avoids additional overhead(operation with head and tail modification).

Insertion In Doubly Linked List:

+------------------------+        +----------------------+       +--------------------+
| NULL |  0   | 1200 -|<---->|- 1100 | 10 | 1300-|<--->|-1200 | 0 | NULL |
+------------------------+        +----------------------+       +--------------------+
          head(1100)                      node1(1200)                   tail(1300)

Here, head and tail are dummy nodes.  Insert a new node(node2) between node1 and tail.

                                        +----------------------+
                                        | NULL | 20 | NULL |
                                        +----------------------+
                                             newnode(1400)

newnode->prev = node1;
newnode->next = node1->next;
node1->next->prev = newnode;
node1->next = newnode;

+-----------------+      +-----------------+      +------------------+     +-------------------+
|NULL| 0 |1200|<-->|1100| 10 |1400|<-->|1200| 20 |1300|<-->|1400 | 0 | NULL|
+-----------------+      +-----------------+      +------------------+     +-------------------+
     head(1100)           node1(1200)            newnode(1400)             tail(1300)


Deletion In Doubly Linked List:
+-----------------+      +-----------------+      +-----------------+      +-------------------+
|NULL| 0 |1200|<-->|1100| 10 |1400|<-->|1200| 20 |1300|<-->|1400 | 0 | NULL|
+-----------------+      +-----------------+      +-----------------+      +-------------------+
     head(1100)          node1(1200)             newnode(1400)             tail(1300)

Delete newnode from the linked list.

node2->prev->next = node2->next;
node2->next->prev = node2->prev;
free(node2);


+------------------------+        +----------------------+       +-------------------+
| NULL |  0   | 1200 -|<---->|- 1100 | 10 | 1300-|<--->|-1200 | 0 | NULL|
+------------------------+        +----------------------+       +-------------------+
          head(1100)                      node1(1200)                   tail(1300)

C Program To Implement Doubly Linked List - Insert, Delete, Traverse & Search:

---

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

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

  struct node *head = NULL, *tail = NULL;
  int nodeCount = 0;

  struct node * createNode(int data) {
        struct node *newnode;
        newnode = (struct node *)malloc(sizeof (struct node));
        newnode->data = data;
        newnode->next = NULL;
        newnode->prev = NULL;
        return (newnode);
  }

  void createDummies() {
        head = (struct node *)malloc(sizeof (struct node));
        tail = (struct node *)malloc(sizeof (struct node));
        head->data = tail->data = 0;
        head->next = tail;
        tail->prev = head;
        head->prev = tail->next = NULL;
  }

  void insert(int data, int pos) {

        struct node *newnode, *temp1;

        int count = 1;

        newnode = createNode(data);

        temp1 =  head;

        while (temp1) {

                if (count == pos) {

                        newnode->next = temp1->next;

                        newnode->prev = temp1;

                        temp1->next->prev = newnode;

                        temp1->next = newnode;

                        nodeCount++;

                        break;

                }

                temp1 = temp1->next;

                count++;

        }

        return;

  }

  void insertAtStart(int data) {

        struct node *newnode = createNode(data);

        newnode->next = head->next;

        newnode->prev = head;

        head->next->prev = newnode;

        head->next = newnode;

        nodeCount++;

  }

  void insertAtEnd(int data) {

        struct node *newnode = createNode(data);

        newnode->next = tail;

        newnode->prev = tail->prev;

        tail->prev->next = newnode;

        tail->prev = newnode;

        nodeCount++;

  }

  void delete(int data) {

        struct node *temp1, *temp2;

        temp1 = head->next;

        while (temp1 != tail) {

                if (temp1->data == data) {

                        temp2 = temp1;

                        temp1->prev->next = temp1->next;

                        temp1->next->prev = temp1->prev;

                        free(temp2);

                        nodeCount--;

                        return;

                }

                temp1 = temp1->next;

        }

        printf("Given node is not present in the List\n");

        return;

  }

  void deleteList() {

        struct node *temp2, *temp1 = head->next;

        while (temp1 != tail) {

                temp1->prev->next = temp1->next;

                temp1->next->prev = temp1->prev;

                temp2 = temp1;

                free(temp1);

                temp1 = temp2->next;

        }

        nodeCount = 0;

        return;

  }

  void searchNode(int data) {

        struct node *temp = head->next;

        while (temp != tail) {

                if (temp->data == data) {

                        printf("Given node is present\n");

                        return;

                }

                temp = temp->next;

        }

        printf("Given node is not present in the list\n");

        return;

  }

  void walkList() {

        struct node *ptr = head->next;

        int flag = 1, i = 1;

        if (head->next == tail) {

                printf("List is Empty\n");

                return;

        }

        printf("Data in List:\n");

        while (ptr != tail) {

                if (ptr->prev != head) {

                        printf("           /\\ \n");

                        printf("           ||\n");

                        flag = 0;

                }

                printf("+------------------------+\n");

                printf("|node%2d addr:0x%08x  |\n", i, (unsigned int)ptr);

                printf("+------------------------+\n");

                printf("|data: %4d              |\n", ptr->data);

                printf("-------------------------+\n");

                printf("|prev: 0x%08x        |\n",

                        ptr->prev == head ? 0 : (unsigned int)ptr->prev);

                printf("+------------------------+\n");

                printf("|next: 0x%08x        |\n",

                        ptr->next == tail ? 0 : (unsigned int)ptr->next);

                printf("+------------------------+\n");

                ptr = ptr->next;

                if (ptr != tail) {

                        printf("    ||      \n");

                        printf("    \\/     \n");

                }

                i++;

        }

  }

  int main() {

        int data, ch, pos;

        createDummies();

        while (1) {

                printf("1. Insert\n2. Delete\n");

                printf("3. Walk List\n4. Search Node\n");

                printf("5. Delete List\n6. Insert At start\n");

                printf("7. Insert at End\n8. Exit\n");

                printf("Enter your choice:");

                scanf("%d", &ch);

                switch (ch) {

                        case 1:

                                printf("Enter the node position(1 - %d)", nodeCount+1);

                                scanf("%d", &pos);

                                if (pos <= 0 || pos > nodeCount+1) {

                                        printf("Please enter correct position\n");

                                } else {

                                        printf("Enter ur data to insert:");

                                        scanf("%d", &data);

                                        insert(data, pos);

                                }

                                break;

                        case 2:

                                printf("Enter the data to delete:");

                                scanf("%d", &data);

                                delete(data);

                                break;

                        case 3:

                                walkList();

                                break;

                        case 4:

                                printf("Enter the data to be searched:");

                                scanf("%d", &data);

                                searchNode(data);

                                break;

                        case 5:

                                deleteList();

                                break;

                        case 6:

                                printf("Enter ur data to  insert at start:");

                                scanf("%d", &data);

                                insertAtStart(data);

                                break;

                        case 7:

                                printf("Enter ur data to insert:");

                                scanf("%d", &data);

                                insertAtEnd(data);

                                break;

                        case 8:

                                exit(0);

                        default:

                                printf("U have entered wrong option\n");

                                break;

                }

        }

        return 0;

  }

 

Output: (Doubly Linked List Example)

  1. Insert
  2. Delete
  3. Walk List
  4. Search Node
  5. Delete List
  6. Insert At start
  7. Insert at End
  8. Exit
  Enter your choice:1
  Enter the node position(1 - 1)1
  Enter ur data to insert:10
  1. Insert
  2. Delete
  3. Walk List
  4. Search Node
  5. Delete List
  6. Insert At start
  7. Insert at End
  8. Exit
  Enter your choice:6
  Enter ur data to  insert at start:20
  1. Insert
  2. Delete
  3. Walk List
  4. Search Node
  5. Delete List
  6. Insert At start
  7. Insert at End
  8. Exit
  Enter your choice:7
  Enter ur data to insert:30
  1. Insert
  2. Delete
  3. Walk List
  4. Search Node
  5. Delete List
  6. Insert At start
  7. Insert at End
  8. Exit
  Enter your choice:3
  Data in List:
  +------------------------------+
  |node 1 addr:0x09af8038  |
  +------------------------------+
  |data:   20                      |
  +------------------------------+
  |prev: 0x00000000           |
  +------------------------------+
  |next: 0x09af8028            |
  +------------------------------+
      ||      
      \/     
             /\ 
             ||
  +------------------------------+
  |node 2 addr:0x09af8028  |
  +------------------------------+
  |data:   10                      |
  +------------------------------+
  |prev: 0x09af8038            |
  +------------------------------+
  |next: 0x09af8048            |
  +------------------------------+
      ||      
      \/     
             /\ 
             ||
  +------------------------------+
  |node 3 addr:0x09af8048  |
  +------------------------------+
  |data:   30                      |
  +------------------------------+
  |prev: 0x09af8028           |
  +------------------------------+
  |next: 0x00000000           |
  +------------------------------+
  1. Insert
  2. Delete
  3. Walk List
  4. Search Node
  5. Delete List
  6. Insert At start
  7. Insert at End
  8. Exit
  Enter your choice:2
  Enter the data to delete:10
  1. Insert
  2. Delete
  3. Walk List
  4. Search Node
  5. Delete List
  6. Insert At start
  7. Insert at End
  8. Exit
  Enter your choice:3
  Data in List:
  +------------------------------+
  |node 1 addr:0x09af8038  |
  +------------------------------+
  |data:   20                      |
  +------------------------------+
  |prev: 0x00000000           |
  +------------------------------+
  |next: 0x09af8048            |
  +------------------------------+
    ||      
    \/     
           /\ 
           ||
  +------------------------------+
  |node 2 addr:0x09af8048  |
  +------------------------------+
  |data:   30                      |
  +------------------------------+
  |prev: 0x09af8038            |
  +------------------------------+
  |next: 0x00000000            |
  +------------------------------+
  1. Insert
  2. Delete
  3. Walk List
  4. Search Node
  5. Delete List
  6. Insert At start
  7. Insert at End
  8. Exit
  Enter your choice:4
  Enter the data to be searched:30
  Given node is present
  1. Insert
  2. Delete
  3. Walk List
  4. Search Node
  5. Delete List
  6. Insert At start
  7. Insert at End
  8. Exit
  Enter your choice:5
  1. Insert
  2. Delete
  3. Walk List
  4. Search Node
  5. Delete List
  6. Insert At start
  7. Insert at End
  8. Exit
  Enter your choice:3
  List is Empty
  1. Insert
  2. Delete
  3. Walk List
  4. Search Node
  5. Delete List
  6. Insert At start
  7. Insert at End
  8. Exit
  Enter your choice:8