Doubly Linked List

Doubly Linked List

Doubly linked list is another kind of Linked list. Doubly linked list contains two pointers for navigation. In this, we can traverse the list in both directions, either forward or backward as compared to the singly linked list. For traversing in both directions, as we said we have two pointers e.g. Next – the next pointer contains the address of next node; Prev – the prev pointer contains the address of the previous node.

Operations on Doubly Linked List

• Insert a node in the linked list:

We can insert a node into the linked list at the front, the end or anywhere in the linked list. The time complexity of these operations is as follows:

• If we insert the node at the front of linked list; takes O(1)
• If we insert the node at the end of linked list; takes O(n)
• If we insert the node anywhere in the linked list; takes O(n)

• Remove a node from the linked list:

We can remove a node from the front of the linked list, the end or anywhere of the linked list. The time complexity of these operations is as follows:

• If we remove the node from the front of linked list; takes O(1)
• If we remove the node from the end of linked list; takes O(n)
• If we remove the node from anywhere in the linked list; takes O(n)

• Search a node in the linked list:

 Searching a node in the linked list takes O(n) time in the worst case.

Doubly Linked List Program in C Language

 #include<stdio.h>
 #include<conio.h>
 #include<stdlib.h>
 struct node
 {
 int info;
 struct node *next;
 struct node *back;
 };
 struct node *start = NULL;
 struct node *uni = NULL;
 void begin(int item)
 {
     struct node *p, *t, *k;
     if(start == NULL)
     {
     p = start;
     t = (struct node *)malloc(sizeof(struct node ));
     start = t;
     start -> info = item;
     start -> next = p;
     start -> back = NULL;
     }
     else
     {
     k = start -> back;
     p = start;
     t = (struct node *)malloc(sizeof(struct node ));
     start = t;
     start -> info = item;
     start -> next = p;
     start -> back = NULL;
     k = start;
     }
 }
 void Specificposition(int item,int pos)
 {
     int i;
 struct node *t, *p, *temp;
 p = start;
 t = (struct node *)malloc(sizeof(struct node ));
 for(i = 1; i<pos-1; i++)
 {
     p = p -> next;
 }
   temp = p -> next;
   t -> back = p;
   t -> next = temp;
   t -> info = item;
   p -> next = t;
 }
 void End(int item)
 {
 struct node *t,*p;
 t = (struct node *)malloc(sizeof(struct node ));
 if(start == NULL)
 {
 start = t;
 start -> info = item;
 start -> next = NULL;
 start -> back = NULL;
 return;
 }
 else
 {
 struct node *p = start,*k;
 while(p -> next != NULL)
 {
 p = p -> next;
 }
 k = p;
 p -> next = t;
 p = p -> next;
 p -> info = item;
 p -> next = NULL;
 p -> back = k;
 uni = p;
 }
 }
 void delbegin()
 {
     struct node *t,*p;
     p = start;
     t = start -> next;
     start = t;
     start -> back = NULL;
     free(p);
 }
 void delend()
 {
      struct node *t;
      t = start;
      while(t -> next -> next !=  NULL)
      {
          t = t -> next;
      }
      t -> next = NULL;
      return;
 }
 void delspecificposition(int pos)
 {
     int i;
     struct node *t, *p;
     t = start;
    for(i = 1; i<pos-1; i++)
    {
        t = t -> next;
    }
    p = t -> next -> next;
    p -> back = t;
    t -> next = t -> next -> next;
     return;
 }
 void traverse(struct node * t)
 {
 if(t == NULL)
 {
             printf(" Linked list is empty\n");
                                     }
                                     while(t -> next !=  NULL)
                                     {
                         printf("%d< -> ",t -> info);
                         t = t -> next;
                         }
                         printf("%d\n",t -> info);
 }
 void main()
 {
 int n,data,i,item,pos;
 while(1)
 {
 printf(" 1. Insert at begin");
 printf("\n 2. Insert at specific position");
 printf("\n 3. Insert at End");
 printf("\n 4. Delete at beginning");
 printf("\n 5. Delete specific position");
 printf("\n 6. Delete at End");
 printf("\n 7. Traverse the list");
 printf("\n 8. Exit\n");
 printf("Enter the choice:-\n");
 scanf("%d",&n);
 switch(n)
 {
 case 1:
        printf("Enter the item do wanna insert:-\n");
        scanf("%d",&item);
        begin(item);
        break;
 case 2:
      printf("Enter the position where do wanna insert:-\n");
      scanf("%d",&pos);
      printf("enter the item do wanna insert at position:-\n");
      scanf("%d",&item);
      Specificposition(item,pos);
      break;
 case 3:
        printf("Enter the item do wanna insert at end:-\n");
        scanf("%d",&item);
        End(item);
        break;
 case 4:
        delbegin();
        break;
 case 5:
          printf("Enter the position which do wanna delete :-\n");
          scanf("%d",&pos);
          delspecificposition(pos);
          break;
 case 6:
       delend();
       break;
 case 7:
        printf("your list is:");
        traverse(start);
        getch();
        break;
 case 8:
         exit(0);
 }
 }
 } 

Output