Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers. They include a series of connected nodes. Here, each node stores the data and the address of the next node.
To learn more about linked list refer to the article “Introduction to Linked LIst
Given a linked list, the task is to insert a new node after a given node of the linked list.
Insert new node after a given node in linked list
Example:
List = 1->2->4->5, Insert a node with value 3 after the node with value 2.
Consider the following representations of the linked list.
C++ class Node {
public:
int data;
Node* next;
};
C struct Node {
int data;
struct Node* next;
};
Java class LinkedList {
Node head;
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
}
Python3 class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
C# public class Node {
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
Javascript <script>
var head;
class Node {
constructor(d) {
this.data = d;
this.next = null;
}
}
</script>
Approach: Follow the below steps for inserting a node after a given node:
Firstly, check if the given previous node is NULL or not. Then, allocate a new node (say temp ) and Assign the data to temp . And then make the next of temp as the next of the previous node. Finally, move the next of the previous node to point to temp . Follow the below image for a better understanding.
How to insert a new node after given node in linked list
Below is the implementation of the approach.
C++ void insertAfter(Node* prev_node, int new_data)
{
if (prev_node == NULL) {
cout << "The given previous node cannot be NULL";
return;
}
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
}
C 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;
}
Java public void insertAfter(Node prev_node, int new_data)
{
if (prev_node == null) {
System.out.println(
"The given previous node cannot be null");
return;
}
Node new_node = new Node(new_data);
new_node.next = prev_node.next;
prev_node.next = new_node;
}
Python3 def insertAfter(self, prev_node, new_data):
if prev_node is None:
print("The given previous node must inLinkedList.")
return
new_node = Node(new_data)
new_node.next = prev_node.next
prev_node.next = new_node
C# public void insertAfter(Node prev_node, int new_data)
{
if (prev_node == null) {
Console.WriteLine("The given previous node"
+ " cannot be null");
return;
}
Node new_node = new Node(new_data);
new_node.next = prev_node.next;
prev_node.next = new_node;
}
Javascript <script>
function insertAfter(prev_node, new_data)
{
if (prev_node == null)
{
document.write("The given previous node cannot be null");
return;
}
var new_node = new Node(new_data);
new_node.next = prev_node.next;
prev_node.next = new_node;
}
</script>
Time Complexity: O(1)Auxiliary Space: O(1)
