Insertion in between two nodes in Doubly Linked List
1. Add a node after a given node in a Doubly Linked List:
We are given a pointer to a node as prev_node, and the new node is inserted after the given node. This can be done using the following steps:
- Firstly create a new node (say new_node).
- Now insert the data in the new node.
- Point the next of new_node to the next of prev_node.
- Point the next of prev_node to new_node.
- Point the previous of new_node to prev_node.
- Point the previous of next of new_node to new_node.
Below is the implementation of the steps to insert a node after a given node in the linked list:
// Given a node as prev_node, insert a new node
// after the given node
void insertAfter(Node* prev_node, int new_data)
{
// Check if the given prev_node is NULL
if (prev_node == NULL) {
cout << "the given previous node cannot be NULL";
return;
}
// 1. allocate new node
Node* new_node = new Node();
// 2. put in the data
new_node->data = new_data;
// 3. Make next of new node as next of prev_node
new_node->next = prev_node->next;
// 4. Make the next of prev_node as new_node
prev_node->next = new_node;
// 5. Make prev_node as previous of new_node
new_node->prev = prev_node;
// 6. Change previous of new_node's next node
if (new_node->next != NULL)
new_node->next->prev = new_node;
}
// Given a node as prev_node, insert a new node
// after the given node
void insertAfter(struct Node* prev_node, int new_data)
{
// Check if the given prev_node is NULL
if (prev_node == NULL) {
printf("the given previous node cannot be NULL");
return;
}
// 1. allocate new node
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
// 2. put in the data
new_node->data = new_data;
// 3. Make next of new node as next of prev_node
new_node->next = prev_node->next;
// 4. Make the next of prev_node as new_node
prev_node->next = new_node;
// 5. Make prev_node as previous of new_node
new_node->prev = prev_node;
// 6. Change previous of new_node's next node
if (new_node->next != NULL)
new_node->next->prev = new_node;
}
// Given a node as prev_node, insert a new node
// after the given node
public void InsertAfter(Node prev_Node, int new_data)
{
// Check if the given prev_node is NULL
if (prev_Node == null) {
System.out.println(
"The given previous node cannot be NULL ");
return;
}
// 1. allocate node
// 2. put in the data
Node new_node = new Node(new_data);
// 3. Make next of new node as next of prev_node
new_node.next = prev_Node.next;
// 4. Make the next of prev_node as new_node
prev_Node.next = new_node;
// 5. Make prev_node as previous of new_node
new_node.prev = prev_Node;
// 6. Change previous of new_node's next node
if (new_node.next != null)
new_node.next.prev = new_node;
}
// Given a node as prev_node, insert a new node
// after the given node
public void InsertAfter(Node prev_Node, int new_data)
{
// Check if the given prev_node is NULL
if (prev_Node == null) {
Console.WriteLine(
"The given previous node cannot be NULL ");
return;
}
// 1. allocate node
// 2. put in the data
Node new_node = new Node(new_data);
// 3. Make next of new node as next of prev_node
new_node.next = prev_Node.next;
// 4. Make the next of prev_node as new_node
prev_Node.next = new_node;
// 5. Make prev_node as previous of new_node
new_node.prev = prev_Node;
// 6. Change previous of new_node's next node
if (new_node.next != null)
new_node.next.prev = new_node;
}
// This code is contributed by aashish1995
<script>
function InsertAfter(prev_Node,new_data)
{
// Check if the given prev_node is NULL
if (prev_Node == null) {
document.write("The given previous node cannot be NULL <br>");
return;
}
// 1. allocate node
// 2. put in the data
let new_node = new Node(new_data);
// 3. Make next of new node as next of prev_node
new_node.next = prev_Node.next;
// 4. Make the next of prev_node as new_node
prev_Node.next = new_node;
// 5. Make prev_node as previous of new_node
new_node.prev = prev_Node;
// 6. Change previous of new_node's next node
if (new_node.next != null)
new_node.next.prev = new_node;
}
// This code is contributed by unknown2108
</script>
# Given a node as prev_node, insert
# a new node after the given node
def insertAfter(self, prev_node, new_data):
# Check if the given prev_node is NULL
if prev_node is None:
print("This node doesn't exist in DLL")
return
# 1. allocate node &
# 2. put in the data
new_node = Node(data=new_data)
# 3. Make next of new node as next of prev_node
new_node.next = prev_node.next
# 4. Make the next of prev_node as new_node
prev_node.next = new_node
# 5. Make prev_node as previous of new_node
new_node.prev = prev_node
# 6. Change previous of new_node's next node
if new_node.next is not None:
new_node.next.prev = new_node
# This code is contributed by jatinreaper
Time Complexity: O(1)
Auxiliary Space: O(1)
2. Add a node before a given node in a Doubly Linked List:
Let the pointer to this given node be next_node. This can be done using the following steps.
- Allocate memory for the new node, let it be called new_node.
- Put the data in new_node.
- Set the previous pointer of this new_node as the previous node of the next_node.
- Set the previous pointer of the next_node as the new_node.
- Set the next pointer of this new_node as the next_node.
- Set the next pointer of the previous of new_node to new_node.
Below is the implementation of the above approach.
// Given a node as prev_node, insert a new node
// after the given node
void insertBefore(Node* next_node, int new_data)
{
// Check if the given next_node is NULL
if (next_node == NULL) {
printf("the given next node cannot be NULL");
return;
}
// 1. Allocate new node
Node* new_node = new Node();
// 2. Put in the data
new_node->data = new_data;
// 3. Make previous of new node as previous of next_node
new_node->prev = next_node->prev;
// 4. Make the previous of next_node as new_node
next_node->prev = new_node;
// 5. Make next_node as next of new_node
new_node->next = next_node;
// 6. Change next of new_node's previous node
if (new_node->prev != NULL)
new_node->prev->next = new_node;
else
head = new_node;
}
// Given a node as prev_node, insert a new node
// after the given node
void insertBefore(struct Node* next_node, int new_data)
{
// Check if the given next_node is NULL
if (next_node == NULL) {
printf("the given next node cannot be NULL");
return;
}
// 1. Allocate new node
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
// 2. Put in the data
new_node->data = new_data;
// 3. Make previous of new node as previous of next_node
new_node->prev = next_node->prev;
// 4. Make the previous of next_node as new_node
next_node->prev = new_node;
// 5. Make next_node as next of new_node
new_node->next = next_node;
// 6. Change next of new_node's previous node
if (new_node->prev != NULL)
new_node->prev->next = new_node;
else
head = new_node;
}
// Given a node as prev_node, insert a new node
// after the given node
public void InsertBefore(Node next_Node, int new_data)
{
// Check if the given next_node is NULL
if (next_Node == null) {
System.out.println(
"The given next node cannot be NULL ");
return;
}
// 1. Allocate node
// 2. Put in the data
Node new_node = new Node(new_data);
// 3. Make previous of new node as previous of prev_node
new_node.prev = next_Node.prev;
// 4. Make the prev of next_node as new_node
next_Node.prev = new_node;
// 5. Make next_node as next of new_node
new_node.next = next_Node;
// 6. Change next of new_node's previous node
if (new_node.prev != null)
new_node.prev.next = new_node;
else
head = new_node;
}
// Given a node as prev_node, insert a new node
// after the given node
public void InsertAfter(Node next_Node, int new_data)
{
// Check if the given next_node is NULL
if (next_Node == null) {
Console.WriteLine(
"The given next node cannot be NULL ");
return;
}
// 1. Allocate node
// 2. Put in the data
Node new_node = new Node(new_data);
// 3. Make previous of new node as previous of next_node
new_node.prev = next_Node.prev;
// 4. Make the previous of next_node as new_node
next_Node.prev = new_node;
// 5. Make next_node as next of new_node
new_node.next = next_Node;
// 6. Change next of new_node's previous node
if (new_node.prev != null)
new_node.prev.next = new_node;
else
head = new_node;
}
// This code is contributed by aashish1995
<script>
function InsertAfter(next_Node,new_data)
{
// Check if the given next_Node is NULL
if (next_Node == null) {
document.write("The given next node cannot be NULL <br>");
return;
}
// 1. Allocate node
// 2. Put in the data
let new_node = new Node(new_data);
// 3. Make previous of new node as previous of next_node
new_node.prev = next_Node.prev;
// 4. Make the previous of next_node as new_node
next_Node.prev = new_node;
// 5. Make next_node as next of new_node
new_node.next = next_Node;
// 6. Change next of new_node's previous node
if (new_node.prev != null)
new_node.prev.next = new_node;
else
head = new_node;
}
// This code is contributed by unknown2108
</script>
# Given a node as prev_node, insert
# a new node after the given node
def insertAfter(self, next_node, new_data):
# Check if the given next_node is NULL
if next_node is None:
print("This node doesn't exist in DLL")
return
# 1. Allocate node &
# 2. Put in the data
new_node = Node(data=new_data)
# 3. Make previous of new node as previous of prev_node
new_node.prev = next_node.prev
# 4. Make the previous of next_node as new_node
next_node.prev = new_node
# 5. Make next_node as next of new_node
new_node.next = next_node
# 6. Change next of new_node's previous node
if new_node.prev is not None:
new_node.prev.next = new_node
else:
head = new_node
# This code is contributed by jatinreaper
Time Complexity: O(1)
Auxiliary Space: O(1)
Insertion in a Doubly Linked List
Inserting a new node in a doubly linked list is very similar to inserting new node in linked list. There is a little extra work required to maintain the link of the previous node. A node can be inserted in a Doubly Linked List in four ways:
- At the front of the DLL.
- In between two nodes
- After a given node.
- Before a given node.
- At the end of the DLL.