Updated March 30, 2023
Introduction to Doubly linked list in C
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.
Syntax:
As every node in the sequence in a doubly-linked list contains 3 parts and stores the address of the next and previous nodes, it is implemented as follows in a C program:
struct node {
struct previous*;
int item;
struct next*
} node_name;where,
- previous: It is a pointer that stores the address of the previous node in the sequence.
- next: It is a pointer that stores the address of the next node in the sequence.
- item: It is the actual data that is stored in the doubly linked list.
- node_name: It is a name given to a whole node on the C program.
How does doubly Linked List works in C?
As already told before, a node in a doubly-linked list contains 3 sections, one with the item and the other two holding the addresses. Let us understand it with the pictorial representation of it in the memory:
Head:
| 10 |
| Memory Address | Previous | Data | Next |
| 10. | null | 7700 | 30 |
| 20. | 50 | 8100 | null |
| 30. | 10 | 7800 | 50 |
| 40. | 50 | 8000 | 20 |
| 50. | 30 | 7900 | 40 |
As we can see in the above table, the ‘Head’ of the list contains the memory address 10, i.e., the starting address of the list. The first element in the list would be 7700. As it is the first element of the doubly linked list, the previous pointer of it points to ‘null,’ and the next pointer is pointing to 30. So the next element in the list would be at the memory address 30, which is 7800. The previous pointer holds the address 10 of the previous node, and the text contains the address of the next node. This process keeps on going until the last element of the list.
Points to remember:
- The previous pointer of the first element of the doubly linked list points to null as it is the first element, and there is no previous address of it.
- The next pointer of the last element of the doubly linked list points to null as it is the last element, showing the end of the list.
- Programmer traverses the whole list in the forward direction until it finds the ‘null’ in the ‘next’ pointer of the node.
- While inserting/ deleting any node in the list, pointers holding the address of the previous and next node are changed, which points to the exact next and previous node in the sequence.
Example of Doubly linked list in C
There are various operations that can be performed in the Doubly Linked List:
Insertion:
- Insertion of node at the beginning of the list.
- Insertion of node at the end of the list
- Insertion of node at a particular position in the list (before/ after a given node).
Deletion:
- Deletion of node at the beginning of the list.
- Deletion of node at the end of the list.
- Deletion of a node from the particular position in the list (before/ after a given node).
Traversing (Display):
- Displaying the list in the forward direction.
- Displaying the list in the backward direction.
C Program to represent the insertion, deletion, and displaying the data of Doubly Linked List:
#include<stdio.h>
#include<stdlib.h>
struct Node {
struct Node *previous;
int item;
struct Node *next;
};
// head pointer holding the address of the first node of list
struct Node *head;
//Creating a new node
struct Node *GetNewNode(int ele) {
struct Node *ptr
= (struct Node*)malloc(sizeof(struct Node));
ptr->item = ele;
ptr->previous = NULL;
ptr->next = NULL;
return ptr;
}
//Inserting a node in the beginning of the list
void InsertBeginning(int ele) {
struct Node *ptr = GetNewNode(ele);
// checking if the list is empty or not
if(head == NULL) {
head = ptr;
return;
}
// if there is some item in the list pointed by head
head->previous = ptr;
ptr->next = head;
head = ptr;
}
//delete a Node from the starting of the list
void DeleteBeginning()
{
struct Node *ptr;
//checking if the list is empty or not
if(head == NULL)
{
printf("\n Sorry there are no items in the list");
}
//if there is only one item present in the list
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nCongratulations!! Node has been successfully deleted \n");
}
//if there are more than one item present in the list
else
{
ptr = head;
head = head -> next;
head -> previous = NULL;
free(ptr);
printf("\n Congratulations!! Node has been successfully deleted \n");
}
}
//Printing all the elements of the list in forward direction
void DisplayForward() {
struct Node *ptr1 = head;
if(ptr1 == NULL)
{
printf("\n Sorry there are no items in the list");
}
else
{
printf("Elements in the forward Direction ");
while(ptr1 != NULL) {
printf("%d ",ptr1->item);
ptr1 = ptr1->next;
}
printf("\n");
}
}
//Printing all the elements in the reverse direction
void DisplayReverse() {
struct Node *ptr1 = head;
if(ptr1 == NULL)
{
printf("\n Sorry there are no items in the list");
}
else
{
// traversing till the last node
while(ptr1->next != NULL) {
ptr1 = ptr1->next;
}
// Traversing backward with the help of previous pointer
printf("Elements in the Reverse Direction ");
while(ptr1 != NULL) {
printf("%d ",ptr1->item);
ptr1 = ptr1->previous;
}
printf("\n");
}
}
//Main function of the program
int main() {
// empty the list
head = NULL;
InsertBeginning(12);
InsertBeginning(23);
InsertBeginning(33);
InsertBeginning(56);
DisplayForward();
DisplayReverse();
DeleteBeginning();
DisplayForward();
DisplayReverse();
}Output1: When there are 4 items in the list
Output2: When there is only one item present in the list:
Conclusion
The above description clearly explains the doubly linked list and its actual implementation in the C program. The doubly Linked list is used widely in solving difficult problems as the traversing and fetching the data of the previous node is quite easy in it using the pointer of the previous node. Programmers must be very clear with pointers and structures concepts to implement and use doubly linked lists in C.
Recommended Articles
This is a guide to Doubly linked list in C. Here we discuss How does doubly Linked List works in C along with the examples and outputs. You may also have a look at the following articles to learn more –
