Doubly Linked List in Data Structures and Algorithms

The linked list concept is used quite commonly in the real world. When we use Spotify to play the next song in the queue, the concept of a single linked list that we learned comes into action. But what exactly can one do to play the previous song in the queue? 

In this blog, we shall understand another concept associated with data structures, which is a Doubly Linked List. We shall also discuss its implementation using C and real-time applications.

What Is a Doubly Linked List?

A linked list is a type of linear data structure that includes nodes connected in a sequential manner. The node contains three fields, i.e., data stored at that reference address and the two pointers pointing to the consequent nodes both left and right of the reference node. 

The left node pointer stores the memory address of the previous node in the sequence, while the right node stores the memory address of the next node. We use dynamic memory allocation here instead of arrays so that the size of memory can be allocated or de-allocated at run time based on the operations performed. 

In this example, the head points to the first node. The left pointer of the reference node stores NULL, and the same happens in the case of the right pointer of the last node.

To have operations done on this example, we can further change it accordingly. 

Implementation of Doubly Linked List

1. Insert Node at the Front

To fulfill the above operation first, create a node and allocate memory using the dynamic memory. Point the head to the new node and store NULL values in both the left and right nodes.

void front_add(){
      //allocate memory using dynamic memory allocation.
       newnode -> data = NULL;
       newnode -> prev = NULL;
       newnode -> next = head;
       head= newnode;
}

2. Delete the Node at the Front

To delete the node from the front, we have to store the right node value of the reference address in the head and free the first node. 

void front_del(){
         newnode=head;
         head= head->next ;
         head->prev = NULL;
         free(newnode);
}

3. Inserting Node at the End

To add the node at the end, we must traverse till the end and point the last node to the reference new node and vice versa.

void end_add(){
     //allocate memory to newnode
     newnode -> data= item; // temp=head
     while(temp ->next !=NULL)
     {
         temp = temp->next;
     }
     temp->next= newnode;
     newnode -> prev = temp;
     newnode-> next = NULL;

}

4. Deleting Node at the End

To delete a node at the end, we must traverse the list and reach the end. We will use a pointer pointing toward the last-second node. Then free the last node.

void rear_del(){
    
     while(temp -> next!=NULL)
     {
         temp = temp->next;          //temp=head
     }
     temp ->prev-> next = NULL;
     free(temp);
}

Now that we have understood the basic operations, we will now walk through the implementation of a doubly linked list using C.

#include<stdio.h>
#define MAX 5

struct node{
    int data;
    struct node * prev;
    struct node * next;
};
struct node *head;
void front_add();
void front_del();
void rear_add();
void rear_del();
void display();

int main(){

    int choice=0;
    while(choice!=6){
    printf("enter choice:\n");
    printf("\n1.front_add\n2.front_Del\n3.rear_add\n4.rear_del\n5.display\n6.exit");
    scanf("%d\n",&choice);

    switch(choice){
        case 1:
           front_add();
           break;
        case 2:
           front_del();
           break;
        case 3:
           rear_add();
           break;
        case 4:
           rear_del();
           break;
        case 5:
           display();
           break;
        case 6:
           printf("exiting...\n");
           break;
        default:
           printf("unknown choice\n");
    }
  }
}
void front_add(){
     struct node* newnode;
     int item;
     newnode = (struct node*)malloc(sizeof(struct node));

     printf("enter item value:\n");
     scanf("%d", &item);
     if(head == NULL)
     {
       newnode -> next = NULL;
       newnode -> prev = NULL;
       newnode -> data = item;
       head = newnode;
     }
     else
     {
       newnode -> data = item;
       newnode -> prev = NULL;
       newnode -> next = head;
       head->prev = newnode;
       head= newnode;
       }
}
void front_del(){
     struct node *newnode;
     if(head->next == NULL)
       {
        head = NULL;
        free(head);
        printf("\nnode deleted\n");
       }
       else
        {
         newnode=head;
         head= head->next ;
         head->prev = NULL;
         free(newnode);
         printf("deleted\n");
       }
}
void rear_add(){
     struct node *temp,*newnode;
     int item;
     newnode = (struct node*)malloc(sizeof(struct node));
     printf("enter item");
     scanf("%d", &item);
     newnode -> data= item;
     temp = head;
     while(temp ->next !=NULL)
     {
         temp = temp->next;
     }
     temp->next= newnode;
     newnode -> prev = temp;
     newnode-> next = NULL;
     printf("inserted\n");

}
void rear_del(){
     struct node *temp;
     temp=head;
     if(head->next==NULL)
     {
         head = NULL;
         free(head);
         printf("deleted\n");
     }
    else{
     while(temp -> next!=NULL)
     {
         temp = temp->next;
     }
     temp ->prev-> next = NULL;
     free(temp);
     printf("deleted\n");

}
}
void display(){
     struct node *temp;
     temp = head;
     if(head==NULL)
     {
         printf("empty\n");
     }
     else{
     while(temp!=NULL)
     {
         printf("%d", temp->data);
         temp = temp->next;
     }
     }
}

This code will give you the desired output of:

Have you ever wondered how these multi-player games are developed, that the players get chances on repeated loops? This means the last player is linked to the first player again to form a loop.

For making this possible, we lead to another concept related to linked lists. A circular linked list is useful in such cases.

Circular Linked List

In the circular singly linked list, the last node of the list contains a pointer to the first node of the list. Both doubly and single-linked lists can use this concept.

The only difference this list has from the other two lists is the right pointer of the last node points to the first node, and the head node always points to the first node itself.

Conclusion

In my opinion, the concept of a linked list is very important and useful during solving complex problems. Both Doubly linked lists and circular singly linked lists come hand in hand while walking through various scenarios. I hope you enjoyed reading this blog. Please do like and comment on your views on today's topic. Happy learning!! 

Do check my previous blogs on data structures, System integration using APIs:

• Stack in Data Structures
• Queue in Data Structures and Algorithms 
• Linked List in Data Structure and Algorithms
• Build RAML-Based API Specification Using MuleSoft Platform
• Publishing API to Anypoint Exchange Using MuleSoft Platform