Doubly Linked Lists in C are complex compared to a singly linked list. A doubly linked list consists of two pointers that store the address of the next successive node and the address of the previous node. The traversal in a doubly linked list happens in both forward and backward directions.
What Is a Doubly Linked List in C?
A linked list is a linear data structure consisting of nodes where each node is divided into two parts, data, and address. Every node in a linked list is linked together.
A Doubly linked list is complex compared to a singly linked list. Each node is divided into three parts to store data and the addresses of the previous and next nodes. In a doubly linked list, the first node prev and last node next pointers point to the null, indicating no nodes before or after it.
It is easy to access elements in the doubly linked list since it consists of two pointers to traversal from forward and backward directions.
Up next, we will understand the Memory representation for Doubly linked lists.
Memory Representation of Doubly Linked List
Let's consider the below-given diagram and understand the memory representation of a doubly linked list.
Let's consider three elements to insert into the list. Each node consists of the data and addresses parts of the prev and next nodes. That is stored at random addresses.
The address of the first node is stored in the special node called the head node.
The first node's prev pointer is pointing to null, indicating no nodes before it, and the last node's next pointer is pointing to the null, which shows no nodes after it.
Every node in a linked list connects in two ways, forward and backward direction with the other through the pointers called prev and next that points to the address of its prev and next node. In this way, every node links with each other, and the arrows in this diagram represent it.
For example:
Let our elements to insert be 10, 20, and 30.
- The first node's next pointer holds the next node's address, address 1, and its prev pointer points to the null.
- Similarly, the second node holds the address of the third node, address 3, and its prev holds the address of the first node, address 1.
- Whereas the third node prev pointer is holding the address of its previous node, address 2, and the next is pointing to the null. In this way, they link together.
Moving ahead, we will look into the syntax to be followed to implement doubly linked lists.
Syntax of Doubly Linked List
Syntax:
struct node
{
int data;
struct node* prev;
struct node* next;
};
Let’s look at the simple, doubly linked list program.
#include <stdio.h>
#include <stdlib.h>
void display();
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
int main()
{
struct Node* head;
struct Node* first=NULL;
struct Node* second=NULL;
struct Node* third=NULL;
struct Node* fourth=NULL;
first = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
fourth = (struct Node*)malloc(sizeof(struct Node));
first->data = 10;
second->data = 20;
third->data = 30;
fourth->data = 40;
first->next = second;
first->prev=NULL;
second->next = third;
second->prev=first;
third->next = fourth;
third->prev=second;
fourth->next = NULL;
fourth->prev = third;
head=first;
display(first);
return 0;
}
void display(struct Node* ptr) {
struct Node* last;
printf("The doubly linked list elements are:\n");
while (ptr != NULL) {
printf("%4d ", ptr->data);
last = ptr;
ptr = ptr->next;
}
}
Output:
Now we know the syntax of a doubly linked list. Let's understand the operation performed on a doubly linked list.
Operations on Doubly Linked List
- Insertion operation
- Deletion operation
- Traversal operation
Insertion Operation
Operation |
Description |
Insertion at beginning |
Inserts the element at the beginning of the list |
Insertion at end |
Insert the element at the end of the list |
Insertion after certain node |
Insert element after specific element |
Program to perform insertion operation on doubly linked list.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
void insertionAtBegin(struct Node** head, int new_data) {
struct Node* new = (struct Node*)malloc(sizeof(struct Node));
new->data = new_data;
new->next = (*head);
new->prev = NULL;
if ((*head) != NULL)
(*head)->prev = new;
(*head) = new;
}
void insertionAtEnd(struct Node** head, int new_data)
{
struct Node* new = (struct Node*)malloc(sizeof(struct Node));
struct Node* lastnode = *head;
new->data = new_data;
new->next = NULL;
struct Node* temp = *head;
if (*head == NULL) {
new->prev = NULL;
*head = new;
return;
}
while (temp->next != NULL)
temp = temp->next;
temp->next = new;
new->prev = temp;
}
void insertionAfternode(struct Node* prev_node, int new_data) {
if (prev_node == NULL) {
printf("the given previous node cannot be NULL");
return;
}
struct Node* new = (struct Node*)malloc(sizeof(struct Node));
new->data = new_data;
new->next = prev_node->next;
prev_node->next = new;
new->prev = prev_node;
if (new->next != NULL)
new->next->prev = new;
}
void display(struct Node* node) {
struct Node* last;
while (node != NULL) {
printf(" %4d ", node->data);
last=node;
node = node->next;
}
}
int main()
{
struct Node* head = NULL;
insertionAtEnd(&head, 4);
insertionAtBegin(&head, 2);
insertionAtBegin(&head, 1);
insertionAfternode(head->next, 3);
insertionAtEnd(&head, 5);
printf("Linked list elements are: \n");
display(head);
}
Output:
Deletion Operation
Operation |
Description |
Deletion at beginning |
deletes the element from the beginning of the list |
Deletion at end |
delete the element from the end of the list |
Deletion after certain node |
delete element after specified element |
Program to perform deletion operation on doubly linked list.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
void insertionAtBegin(struct Node** head, int new_data) {
struct Node* new = (struct Node*)malloc(sizeof(struct Node));
new->data = new_data;
new->next = (*head);
new->prev = NULL;
if ((*head) != NULL)
(*head)->prev = new;
(*head) = new;
}
void insertionAtEnd(struct Node** head, int new_data) {
struct Node* new = (struct Node*)malloc(sizeof(struct Node));
struct Node* lastnode = *head;
new->data = new_data;
new->next = NULL;
struct Node* temp = *head;
if (*head == NULL) {
new->prev = NULL;
*head = new;
return;
}
while (temp->next != NULL)
temp = temp->next;
temp->next = new;
new->prev = temp;
}
void insertionAfternode(struct Node* prev_node, int new_data) {
if (prev_node == NULL) {
printf("the given previous node cannot be NULL");
return;
}
struct Node* new = (struct Node*)malloc(sizeof(struct Node));
new->data = new_data;
new->next = prev_node->next;
prev_node->next = new;
new->prev = prev_node;
if (new->next != NULL)
new->next->prev = new;
}
void deletionNode(struct Node** head, struct Node* node_delete)
{
if (*head == NULL || node_delete == NULL)
return;
if (*head == node_delete)
*head = node_delete->next;
if (node_delete->next != NULL)
node_delete->next->prev = node_delete->prev;
if (node_delete->prev != NULL)
node_delete->prev->next = node_delete->next;
free(node_delete);
}
void display(struct Node* node)
{
struct Node* last;
while (node != NULL) {
printf(" %4d ", node->data);
last=node;
node = node->next;
}
}
int main()
{
struct Node* head = NULL;
insertionAtEnd(&head, 4);
insertionAtBegin(&head, 2);
insertionAtBegin(&head, 1);
insertionAtEnd(&head, 5);
insertionAfternode(head->next, 3);
printf("Linked list elements are: ");
display(head);
printf("\nAfter deleting an element: \n");
deletionNode(&head, head->next->next->next->next);
display(head);
}
Output:
Moving ahead, let’s look at the traversal operation.
Traversal Operation
Operation |
Description |
Traversal |
Visiting every node in a list at least once |
In a doubly linked list traversal operation, we visit every node at least once to display all the data elements or perform operations.
Function to perform traversal operation on doubly linked list
void traversal (struct Node* node)
{
struct Node* last;
while (node != NULL) {
printf(" %4d ", node->data);
last=node;
node = node->next;
}
}
With that, you can conclude this tutorial on the Doubly Linked List program in c.
Master front-end and back-end technologies and advanced aspects in our Post Graduate Program in Full Stack Web Development. Unleash your career as an expert full stack developer. Get in touch with us NOW!
Next Steps
"Circular Linked List In C" can be your next topic. So far, you have learned the Doubly Linked List Program in C. The next fundamentals will be the data structures and the varieties in data structures used for different purposes.
If you are interested in building a career in software development, then feel free to explore Simplilearn's Courses that will give you the work-ready software development training you need to succeed today. Are you perhaps looking for a more comprehensive training program in the most in-demand software development skills, tools, and languages today? If yes, our Post Graduate Program in Full Stack Web Development should be the right thing for your career. Explore the course and enroll soon.
Please let us know in the comment section below if you have questions regarding the "Doubly Linked List In C” tutorial. Our experts will get back to you at the earliest.