Last Updated on May 12, 2023 by Prepbytes
A doubly linked list is a data structure that consists of a set of nodes, each containing a value and two pointers – one to the next node and one to the previous node in the list.
What is a Doubly Linked List?
A doubly linked list is a sequence of elements, called nodes, where each node contains a reference to the previous and next node in the sequence. In other words, each node is linked to both its previous and next node in the list, hence the name "doubly linked" list.
Each node in a doubly linked list typically contains two pointers, one pointing to the previous node and one pointing to the next node. The first node in the list is called the head, and it does not have a previous node. Similarly, the last node in the list is called the tail, and it does not have a next node.
Insertion in a Doubly Linked List
Three cases can be considered for insertion in the doubly linked list.
- Insertion at the beginning
- Insertion after nth node
- Insertion at the end
Insertion at the Beginning of a Doubly Linked List
The procedures listed below would be used to add a new node to the doubly linked list’s starting position.
- Step 1: Add a new node.
- Step 2: Give its data a value.
- Step 3: Give the current head reference to the next pointer of the newly generated node. Consequently, it directs attention to the linked list address’s earlier start node.
- Step 4: Set the address of the new node as the head reference.
- Step 5: Change the previous pointer for the next node to the new node’s address (head reference).
Code Implementation
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
struct Node *prev;
};
void insertStart (struct Node **head, int data)
{
struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
newNode->data = data;
newNode->next = *head;
newNode->prev = NULL;
if (*head != NULL)
(*head)->prev = newNode;
// *head->prev = newNode; would not work it has (*head) must be used
//changing the new head to this freshly entered node
*head = newNode;
}
// function to print the doubly linked list
void display (struct Node *node)
{
struct Node *end;
printf ("Doubly Linked list : ");
while (node != NULL)
{
printf (" %d ", node->data);
end = node;
node = node->next;
}
}
int main ()
{
struct Node *head = NULL;
insertStart (&head, 12);
insertStart (&head, 16);
insertStart (&head, 20);
display (head);
return 0;
}
Output
Doubly Linked list: 20 16 12 Insertion at the Nth Node in a Doubly Linked List
The procedures listed below would be used to add an nth node to the doubly linked lists.
- Step 1: Determine the node’s size.
- Step 2: Invalid position if the point you wish to enter is less than 1, but use the insertAtStart function if it is 0.
- Step 3: If the position you wish to input exceeds the size limit, the position is invalid, however, if the position is equal to the size limit, use the insertLast method.
- Step 4: Alternatively, construct a temporary node and give it the head’s address.
- Step 5: A new node should be created and given the data value.
- Step 6: Iterate to the location in the linked list that you wish to enter after.
- Step 7: Assign the next and previous nodes of this new node.
- Step 8: Next to this new node, place the preceding nodes.
- Step 9: Give this new node the previous node of the following node.
Code Implementation
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
struct Node *prev;
};
void insertLast (struct Node **head, int data);
void insertStart (struct Node **head, int data);
int calcSize (struct Node *node)
{
int size = 0;
while (node != NULL)
{
node = node->next;
size++;
}
return size;
}
void insertPosition (int pos, int data, struct Node **head)
{
int size = calcSize (*head);
if (pos < 0 || size < pos)
{
printf ("Can't insert, %d is not a valid position\n", pos);
return;
}
if (pos == 0)
insertStart (head, data);
else if (pos == size)
insertLast (head, data);
else
{
struct Node *temp = *head;
struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
newNode->data = data;
newNode->next = NULL;
while (--pos)
temp = temp->next;
struct Node *temp2 = temp->next;
newNode->next = temp->next;
newNode->prev = temp;
temp->next = newNode;
temp2->prev = newNode;
}
}
void insertLast (struct Node **head, int data)
{
struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
newNode->data = data;
newNode->next = NULL;
if (*head == NULL)
{
*head = newNode;
newNode->prev = NULL;
return;
}
struct Node *temp = *head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
void insertStart (struct Node **head, int data)
{
struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
newNode->data = data;
newNode->next = *head;
newNode->prev = NULL;
if (*head != NULL)
(*head)->prev = newNode;
*head = newNode;
}
void display (struct Node *node)
{
struct Node *end;
printf ("Doubly linked list: ");
while (node != NULL)
{
printf (" %d ", node->data);
end = node;
node = node->next;
}
}
int main ()
{
struct Node *head = NULL;
insertStart (&head, 12);
insertStart (&head, 16);
insertStart (&head, 20);
insertLast (&head, 10);
insertLast (&head, 14);
insertLast (&head, 18);
insertLast (&head, 11);
printf ("linked before insertion at specific position\n");
display (head);
printf ("\n\nlinked after insertion at specific position\n");
insertPosition (3, 25, &head);
display (head);
return 0;
} Output
linked before insertion at specific position
Doubly linked list: 20 16 12 10 14 18 11
linked after insertion at specific position
Doubly linked list: 20 16 12 25 10 14 18 11 Insertion at the End of a Doubly Linked List
The procedures listed below would be used to add a node at the end of the doubly linked lists.
- Step 1: Add a new node.
- Step 2: Give its data a value.
- Step 3: As this will be the last (tail) node, assign its following node to NULL.
- Step 4: Verify that the list is empty.
- The head node should be changed to this node.
- Simply assign the preceding node as NULL and return if it is empty.
- Step 5: If not, continue until you reach the final node.
- Step 6: Give this new node the next pointer from the previous node.
- Step 7: Adding this new node between the list’s last and previous nodes.
- Step 8: The new node is now the last node.
Code Implementation
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
struct Node *prev;
};
void insertLast (struct Node **head, int data)
{
struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
newNode->data = data;
newNode->next = NULL;
if (*head == NULL)
{
*head = newNode;
newNode->prev = NULL;
return;
}
struct Node *temp = *head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
void insertStart (struct Node **head, int data)
{
struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
newNode->data = data;
newNode->next = *head;
newNode->prev = NULL;
if (*head != NULL)
(*head)->prev = newNode;
*head = newNode;
}
void display (struct Node *node)
{
struct Node *end;
printf ("Doubly Linked list: ");
while (node != NULL)
{
printf (" %d ", node->data);
end = node;
node = node->next;
}
}
int main ()
{
struct Node *head = NULL;
insertStart (&head, 12);
insertStart (&head, 16);
insertStart (&head, 20);
insertLast (&head, 10);
insertLast (&head, 14);
insertLast (&head, 18);
insertLast (&head, 11);
display (head);
return 0;
} Output
Doubly Linked list: 20 16 12 10 14 18 11 Conclusion
Insertion in a doubly linked list is a fundamental operation that involves adding a new node to the list at a specified position. The process is more complex than insertion in a singly linked list because we need to update both the "next" and "prev" pointers of multiple nodes. However, the advantage of a doubly linked list is that we can traverse the list both forwards and backward, which can be useful in certain applications. Understanding the process of insertion in a doubly linked list is important for anyone who works with linked lists or data structures in general.
Frequently Asked Questions
Q1. What is the difference between insertion in a singly linked list and a doubly linked list?
Ans. In a singly linked list, insertion involves updating only the "next" pointer of the previous node and the new node. However, in a doubly linked list, insertion involves updating both the "next" and "prev" pointers of multiple nodes.
Q2. What are the advantages of using a doubly linked list?
Ans. One advantage of a doubly linked list is that we can traverse the list both forwards and backward, which can be useful in certain applications. Additionally, deleting a node in a doubly linked list is more efficient than deleting a node in a singly linked list because we don’t need to traverse the list from the beginning to find the previous node.
Q3. What is the time complexity of inserting a node into a doubly linked list?
Ans. The time complexity of inserting a node into a doubly linked list is O(1) for inserting at the beginning or end of the list, and O(n) for inserting in the middle of the list, where n is the number of nodes in the list.
Q4. What happens if we try to insert a node into a doubly linked list at an invalid position?
Ans. If we try to insert a node into a doubly linked list at an invalid position, we may end up with a broken list that cannot be traversed correctly. It’s important to check that the insertion position is valid before performing the insertion operation.
Q5. How can we ensure that the "prev" pointer of the first node and the "next" pointer of the last node in a doubly linked list always point to null?
Ans. We can set the "prev" pointer of the first node and the "next" pointer of the last node in a doubly linked list to null when we create the list, and make sure that these pointers are updated correctly when we insert or delete nodes from the list.