Skip to main content

Doubly Linked List Data Structure (C Language)

Introduction to Doubly Linked List​

A Doubly Linked List (DLL) is a type of linked list where each node has three fields: the data itself, a pointer to the next node in the sequence, and a pointer to the previous node. Unlike a Singly Linked List, where traversal is only possible in one direction (from head to tail), a doubly linked list allows for both forward and backward traversal, making it more flexible for operations like insertions, deletions, and reversals.

In C, doubly linked lists are implemented using structs and pointers. Each node is dynamically allocated using memory functions, such as malloc(), allowing the list to grow or shrink in size as needed. This data structure is particularly useful when you need efficient manipulation of a sequence of elements and quick access in both directions.

Doubly Linked list Structure in C​

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

Pseudocode​

Basic Operations​

  1. Creation:

     node*create() 
    {
    node*h,*p,*s,*head;
    int x,i,num;
    //memory allocation
    h=(node*)malloc(sizeof(node));
    h->prev=h->next=NULL;
    //ask user that how many elements they want to insert
    printf("\nenter no. of elements_");
    scanf("%d",&x);
    //taking user input
    printf("\nenter data_");
    scanf("%d",&h->data);
    //taking two pointer at start and at the end
    p=h;
    for(i=1;i<x;i++)
    {
    p->next=(node*)malloc(sizeof(node));
    s=p;
    p=p->next;
    p->prev=s;
    p->next=NULL;
    printf("\nenter data_");
    scanf("%d",&p->data);
    }
    head=p;
    //can make choice of where side of control user want to start
    printf("\nChoice to give control from start or from last if(num =1 last node pointer will be pass)");
    scanf("%d",&num);
    if(num==1)
    return(h);
    return(head);
    }
  2. Traversal:

     void display(node*head) 
    {
    node*p;
    p=head;
    //checking if the pointer pass from front or from end (in my case but you can create your creativity)
    if(p->next!=NULL)
    {
    printf("\nDLL is:(by going with next)\n");
    while(p!=NULL)
    {
    printf("%d\t",p->data);
    p=p->next;
    }
    }
    else
    {
    printf("\nDLL is:(by going with previous)\n");
    while(p!=NULL)
    {
    printf("%d\t",p->data);
    p=p->prev;
    }
    }
    }
  3. Insertion (begining , last , or any location):

     void insertion(node*head) 
    {
    int loc,i;
    node*p,*q,*s;
    p=(node*)malloc(sizeof(node));
    p->next=p->prev=NULL;
    printf("\nenter inerting element_");
    //making your data's node to insert
    scanf("%d",&p->data);
    //enter location where you want to insert
    printf("\nenter location_");
    scanf("%d",&loc);
    q=head;
    //insertion at begining
    if(loc==1)
    {
    p->next=head;
    head->prev=p;
    display(p);
    }
    else
    {
    for(i=2;i<loc;i++)
    q=q->next;
    s=q->next;
    p->next=s;
    s->prev=p;
    q->next=p;
    p->prev=q;
    //see the inserted linked list
    display(head);
    }
    }
  4. Deletion (at begining , at last , or at any location):

     void delete(node*head) 
    {
    node*p,*q,*s;
    int loc,i;
    //from where you want to delete
    printf("\nenter location_");
    scanf("%d",&loc);
    //at begining
    if(loc==1)
    {
    head=head->next;
    head->prev=NULL;
    //see the deleted DLL
    display(head);
    }
    else
    {
    p=head;
    for(i=2;i<loc;i++)
    p=p->next;
    q=p->next->next;
    p->next=NULL;
    p->next=q;
    q->prev=p;
    //see the deleted DLL
    display(head);
    }
    }
  5. Main function:

     void main() 
    {
    node*head;
    printf("Doubly Linked list\n");
    //creating function
    head=create();
    //display function
    display(head);
    //insertion function
    insertion(head);
    //delete function
    delete(head);
    }

Complexity​

  • Time Complexity:

    • Traversal: O(n)O(n)
    • Insertion : O(1)O(1)
    • Deletion: O(1)O(1)
  • Space Complexity: O(1)O(1)

Advantages:​

-Bidirectional traversal: You can traverse the list both forward and backward. -Efficient insertion and deletion: Insertion and deletion operations are efficient at both ends of the list as well as in the middle, as you don’t need to shift elements like you would in an array.

Disadvantages:​

Extra memory: Each node requires additional memory for storing the pointer to the previous node. More complex code: The management of two pointers (previous and next) makes the implementation more complex than a singly linked list.

Use Cases:​

Browser History: Moving forward and backward through previously visited pages. Undo/Redo Operations: Navigating through changes in a document or application. Navigation systems: Efficiently traversing elements in both directions in applications such as playlists or slideshows.

Conclusion​

In this C implementation, we cover fundamental operations such as inserting and deleting nodes at both ends, as well as traversing the list in both directions. Understanding doubly linked lists is essential for mastering dynamic data structures and memory management in C.