Doubly Linked List Implementation

Doubly Linked List (DLL) is a complex data structure and an advanced version of a simple linked list in which the node has a pointer to the next node only. As we can traverse the elements in only one direction, reverse traversing is not possible. To solve this problem, a doubly-linked list came into the picture as each node contains the address of the previous and next node, so both the forward and backward traversing of the list is possible. So every node in a doubly-linked list contains 3 parts, i.e., the node which stores the actual item and the other parts contain the pointers containing the address of the previous and next node in the sequence. In this topic, we are going to learn about the Doubly linked list in C.

A Doubly Linked List is a unique type of Data Structure where there are a chain of nodes, that are connected to one another using pointers, where any individual node has 3 components -

Data - *prev
Previous Pointer - data
Next Pointer - *next

For any node, its previous pointer contains the address of the previous node and the next pointer contains the address of the next node in the chain of nodes.

Following is a Doubly Linked List representation.

Algorithm

Operations on Doubly Linked List

Node creation :

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

Other Operations :

Insertion at beginning - Adding the node into the linked list at beginning.
Insertion at end - Adding the node into the linked list to the end.
Insertion after specified node - Adding the node into the linked list after the specified node.
Deletion at beginning - Removing the node from beginning of the list
Deletion at the end - Removing the node from end of the list.
Deletion of the node having given data - Removing the node which is present just after the node containing the given data.
Searching - Comparing each node data with the item to be searched and return the location of the item in the list if the item found else return null.
Traversing - Visiting each node of the list at least once in order to perform some specific operation like searching, sorting, display, etc.

Program using C

//DOUBLY LINKED LIST IMPLEMENTATION
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
struct node
{
int info;
struct node *next, *prev;
};
struct node *start=NULL, *end=NULL;
void ins_at_any_pos(int);
void del_at_any_pos(int);
void display();
void main()
    {
        int ch, pos;
        while (1)
        {
            printf("\nMENU\n1. Insert\n2. Delete\n3. Display\n4. Exit\nEnter your choice: ");
            scanf("%d",&ch);
            switch(ch)
            {
                case 1:
                    printf("Enter the position: ");
                    scanf("%d",&pos);
                    ins_at_any_pos(pos);
                    break;
                case 2:
                    printf("Enter the position: ");
                    scanf("%d",&pos);
                    del_at_any_pos(pos);
                    break;
                case 3:
                    display();
                    break;		
                case 4: exit(0);
                default: printf("Wrong choice\n");	
            }
        }
    }
    
    void ins_at_any_pos(int num)
    {
        struct node *curr, *t, *new_node;
        int n=1;
        new_node=(struct node*)malloc(sizeof(struct node));
        printf("Enter into the info part of the node: ");
        scanf("%d",&new_node->info);
        if(num==1)
        {
            new_node->next=start;
            new_node->prev=NULL;
            if(start==NULL)
                start =end=new_node;
            else
            {
                start->prev=new_node;
                start=new_node;
            }
            return;
        }
        curr=start;
        while(curr !=NULL && n<num)
        {
            t=curr;
            curr=curr->next;
            n++;
        }
        if(n==num && curr != NULL)
        {
            new_node->next=curr;
            new_node->prev=t;
            t->next=new_node;
            curr->prev=new_node;
            return;
        }
        if(n==num && curr == NULL)
        {
            t->next=new_node;
            new_node->next=NULL;
            new_node->prev=t;
            end = new_node;
        }
        else
            printf("Invalid position\n");
    }
    
    void display()
    {
        struct node *curr = start;
        printf("The Doubly linked list: Start->");
        while(curr != NULL)
        {
            printf("%d<->",curr->info);
            curr=curr->next;
        }
        printf("End\n");
        printf("\nThe reverse of the linked list list is: End->");
        curr=end;
        while(curr != NULL)
        {
            printf("%d<->",curr->info);
            curr=curr->prev;
        }
        printf("START\n");
    }
    
    void del_at_any_pos(int num)
    {
        struct node *t;
        int n=1;
        if(start == NULL)
            printf("Underflow!\n");
        else
        {
            t=start;
            if(num==1)
            {
                start =start->next;
                start->prev=NULL;
                free(t);
                if(start == NULL)
                    end=NULL;
            }
            else
            {
                while(t!=NULL && n<num)
                {
                    t=t->next;
                    n++;
                }
                if(t!=NULL && n==num)
                {
                    t->prev->next = t->next;
                    if(t->next==NULL)
                        end = t->prev;
                    else
                        t->next->prev = t->prev;
                    free(t);		
                }
                else
                    printf("Node not found. Invalid num!!\n");
            }
        }	
    }