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β
-
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);
} -
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;
}
}
} -
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);
}
} -
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);
}
} -
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:
- Insertion :
- Deletion:
-
Space Complexity:
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.