Last Updated on July 31, 2023 by Mayank Dham
Welcome to our comprehensive guide on "Insertion in Doubly Linked Lists in C." Doubly linked lists are fundamental data structures used to store and manage collections of elements in a sequential manner. They provide an efficient way to insert, delete, and traverse elements both forwards and backwards in the list.
In this article, we will delve into the concept of doubly linked lists, discuss the various types of insertions, and provide clear, step-by-step explanations of the insertion process with illustrative C code examples. Whether you’re a beginner learning the basics of data structures or an experienced programmer looking to refresh your knowledge, this article will serve as an excellent resource to help you understand and implement insertion in doubly linked lists in C.
What is Doubly Linked List in C programming?
A doubly linked list is a type of linked list that allows for easy navigation in both forward and backward directions. This is different from a singly linked list, which only allows for forward traversal. To understand Doubly Linked Lists, it is important to know the key terms associated with this data structure
- data − Each data of a linked list is used to store data called an element.
- Next − Each link of a linked list contains a link to the next link called Next.
- Prev − Each link of a linked list contains a link to the previous link called Prev.
The below image shows a general doubly linked list.
Here is the representation of the DLL node:
struct node {
int data;
struct node *next;
struct node *prev;
}
Let’s Discuss insertion in the doubly linked list in c.
Insertion in Doubly Linked List
A node can be added in 3 ways in the doubly linked list:
- At the front of the DLL.
- After a Given Node.
- At the end of the DLL.
1. Insertion in Doubly Linked List: At the Front
In this insertion, we will add the node at the front of the doubly linked list.
- Create a new node
- Allocate memory for newNode.
- Assign data to the newNode.
- Set prev and next pointers of the new node
- point next of newNode to the first node of the doubly linked list
- point prev to null
- Make new node as head node
- Point prev of the first node to newNode (now the previous head is the second node)
- Point head to newNode
Below is the implementation of the insertion in doubly linked list in C at the beginning:
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
new_node->prev = NULL;
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
(*head_ref) = new_node;
}
2. Insertion in Doubly Linked List: Adding Node After the Given Node
We are given a pointer to a node as prev_node, and the new node is inserted after the given node.
Let’s add one node in the DLL. We have to add a new node with value E in the DLL with nodes A->B->C->D. We have to add a new node after node with value A.
- Create a node
- Allocate memory for newNode
- Assign data to the newNode.
- Set the next pointer of the new node and the previous node
- assign the value of next from the previous node to the next of newNode
- assign the address of newNode to the next of the previous node
- Set the prev pointer of the new node and the next node
- assign the value of prev of the next node to the prev of newNode
- assign the address of newNode to the prev of next node
The final doubly linked list after insertion is shown in the image given below.
Below is the implementation of insertion in doubly linked list in C after the given node:
void append(struct Node** head_ref, int new_data)
{
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref; /* used in step 5*/
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL) {
new_node->prev = NULL;
*head_ref = new_node;
return;
}
while (last->next != NULL)
last = last->next;
last->next = new_node;
new_node->prev = last;
return;
}
3. Insertion in Doubly Linked List: Adding a Node at the End
In this insertion, we will add the node at the end of the doubly linked list.
Let’s discuss it by adding a new node with value E at the end of the linked list with nodes A->B->C->D.
- Create a node
- Allocate memory for newNode
- Assign data to the newNode.
- Set prev and next pointers of the new node and the previous node
If the linked list is empty, make the new node the head node. Otherwise, traverse to the end of the doubly linked list and perform the operations as shown below:
The Final list will be
Here is the implementation of insertion in doubly linked list in C at the end:
void append(struct Node** head_ref, int new_data)
{
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref; /* used in step 5*/
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL) {
new_node->prev = NULL;
*head_ref = new_node;
return;
}
while (last->next != NULL)
last = last->next;
last->next = new_node;
new_node->prev = last;
return;
}
Below is the Complete Program for the Insertion in Doubly Linked List in C
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
new_node->prev = NULL;
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
(*head_ref) = new_node;
}
void insertAfter(struct Node* prev_node, int new_data)
{
if (prev_node == NULL) {
printf("the given previous node cannot be NULL");
return;
}
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
new_node->prev = prev_node;
if (new_node->next != NULL)
new_node->next->prev = new_node;
}
void append(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref;
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL) {
new_node->prev = NULL;
*head_ref = new_node;
return;
}
while (last->next != NULL)
last = last->next;
last->next = new_node;
new_node->prev = last;
return;
}
void printList(struct Node* node)
{
struct Node* last;
printf("\nTraversal in forward direction \n");
while (node != NULL) {
printf(" %d ", node->data);
last = node;
node = node->next;
}
printf("\nTraversal in reverse direction \n");
while (last != NULL) {
printf(" %d ", last->data);
last = last->prev;
}
}
int main()
{
struct Node* head = NULL;
append(&head, 2);
push(&head, 4);
push(&head, 6);
append(&head, 8);
insertAfter(head->next, 10);
printf("Created DLL is: ");
printList(head);
getchar();
return 0;
}
Output:
Created DLL is:
Traversal in forward direction
6 4 10 2 8
Traversal in reverse direction
8 2 10 4 6Conclusion
In this article, we have discussed the insertion in doubly linked list in C. Throughout this article, we’ve explored three main types of insertions in doubly linked lists: insertion at the beginning, insertion at the end, and insertion after a specific node. We’ve also provided detailed C code examples for each type, guiding you through the implementation process.
Frequently Asked Questions(FAQs) on insertion in doubly linked list in C
Here are some Frequently Asked Questions related to insertion in doubly linked list in C.
Q1: Are doubly linked lists suitable for large datasets?
Doubly linked lists are efficient for certain operations, but they may not be the best choice for extremely large datasets due to their higher memory overhead compared to other data structures like arrays or singly linked lists. For large datasets, consider using more advanced data structures that provide better performance characteristics, such as balanced trees or hash tables.
Q2: What are the advantages of using a doubly linked list over a singly linked list?
The main advantage of using a doubly linked list over a singly linked list is the ability to traverse both forwards and backwards. This feature simplifies certain operations that might be cumbersome in singly linked lists, such as inserting elements at the end of the list or traversing in reverse order.
Q3: How do I insert an element at the beginning of a doubly linked list?
To insert an element at the beginning of a doubly linked list, you need to create a new node, adjust the pointers of the new node and the current first node, and then update the head pointer to the new node.
Q4: Can I insert an element after a specific node in a doubly linked list?
Yes, you can insert an element after a specific node in a doubly linked list. To do this, you’ll need to adjust the pointers of the current node, the new node, and the node that follows the current node.
Q5: Is it possible to insert an element at the end of the doubly linked list efficiently?
Yes, it is possible to insert an element at the end of the doubly linked list efficiently. By maintaining a tail pointer that always points to the last node, you can directly perform the insertion without having to traverse the entire list. This ensures constant time complexity for insertion at the end.