Insert before the node with Value X of the Linked List
Problem Statement: Given a linked list, an element el, and a value val, your task is to insert a new node with data el before the node with value val in the list.
Examples
Example 1:
Input Format: 0->1->2 , el = 5, val = 2
Result: 0->1->5->2
Explanation: We need to insert element 5 before the node with value 2.
Example 2:
Input Format:12->5->8->7, el = 100, val = 5
Result: 12->100->5->8->7
Explanation: Again, we need to insert the value 100 before the node with value 5 in the linked list.
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Approach:
The intuition to approach this problem is to find the node with the value val in the linked list and then insert the newly created node with data el before this node.
There is one edge case to consider:
If the value matches with the head’s data, then the insertion will happen before the head of the linked list. The new node, therefore, will be the new head of the linked list, and the insertion will be the same as inserting before the head of the linked list. You may refer to this article for more understanding.
Algorithm:
Initialize a temp pointer that will be used to traverse the list.
Now, since insertion will happen before the node with value val, stop the traversal once the data of the nodenext to the node temp is pointing toequals val.
Having reached the desired node, create a new node with data el. There are two crucial steps to follow to successfully insert this newly created node:
First, point the newly created node to the next node (temp->next)
Then point the previous node to the newly created node to complete the insertion
If the traversal is complete, this means there was no node with value val in the list. Therefore, no node will get inserted in the linked list.
Code:
C++ Code
// Node class representing a node in a linked list
class Node {
public:
int data;
Node* next;
// Constructors
Node(int data1, Node* next1) {
data = data1;
next = next1;
}
Node(int data1) {
data = data1;
next = nullptr;
}
};
// Function to print the linked list
void printLL(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
// Function to insert a new node with data 'el' after the node with data 'val'
Node* insertAtK(Node* head, int el, int val) {
if (head == NULL) {
return NULL;
}
// Insert at the beginning if the value matches the head's data
if (head->data == val)
return new Node(el, head);
Node* temp = head;
while (temp->next != NULL) {
// Insert at the current position if the next node has the desired value
if (temp->next->data == val) {
Node* newNode = new Node(el, temp->next);
temp->next = newNode;
break;
}
temp = temp->next;
}
return head;
}
int main() {
// Initialize vector with values
vector<int> arr = {0, 1, 2};
int el = 5;
int val = 2;
// Create a linked list with the given vector
Node* head = new Node(arr[0]);
head->next = new Node(arr[1]);
head->next->next = new Node(arr[2]);
// Insert a new node with data 'el' after the node with data 'val'
head = insertAtK(head, el, val);
// Print the modified linked list
printLL(head);
return 0;
}
Output: 0 1 5 2
Time Complexity: O(N) worst case, when insertion happens at the tail and O(1) best case, when insertion happens at the head.
Space Complexity: O(1), as we have not used any extra space.
Java Code
class Node {
public int data;
public Node next;
// Constructors
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
public Node(int data) {
this.data = data;
this.next = null;
}
}
public class Main {
// Function to print the linked list
public static void printLL(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
}
// Function to insert a new node with data 'el' after the node with data 'val'
public static Node insertAtK(Node head, int el, int val) {
if (head == null) {
return null;
}
// Insert at the beginning if the value matches the head's data
if (head.data == val) {
return new Node(el, head);
}
Node temp = head;
while (temp.next != null) {
// Insert at the current position if the next node has the desired value
if (temp.next.data == val) {
Node newNode = new Node(el, temp.next);
temp.next = newNode;
break;
}
temp = temp.next;
}
return head;
}
public static void main(String[] args) {
// Initialize list with values
ArrayList<Integer> arr = new ArrayList<Integer>() {{ add(0); add(1); add(2); }};
int el = 5;
int val = 2;
// Create a linked list with the given array list
Node head = new Node(arr.get(0));
head.next = new Node(arr.get(1));
head.next.next = new Node(arr.get(2));
// Insert a new node with data 'el' after the node with data 'val'
head = insertAtK(head, el, val);
// Print the modified linked list
printLL(head);
}
}
Output: 0 1 5 2
Time Complexity: O(N) worst case, when insertion happens at the tail and O(1) best case, when insertion happens at the head.
Space Complexity: O(1), as we have not used any extra space.
Python Code
class Node:
def __init__(self, data, next_node=None):
self.data = data
self.next = next_node
# Function to print the linked list
def print_ll(head):
while head is not None:
print(head.data, end=" ")
head = head.next
# Function to insert a new node with data 'el' after the node with data 'val'
def insert_at_k(head, el, val):
if head is None:
return None
# Insert at the beginning if the value matches the head's data
if head.data == val:
return Node(el, head)
temp = head
while temp.next is not None:
# Insert at the current position if the next node has the desired value
if temp.next.data == val:
new_node = Node(el, temp.next)
temp.next = new_node
break
temp = temp.next
return head
if __name__ == "__main__":
# Initialize list with values
arr = [0, 1, 2]
el = 5
val = 2
# Create a linked list with the given array
head = Node(arr[0])
head.next = Node(arr[1])
head.next.next = Node(arr[2])
# Insert a new node with data 'el' after the node with data 'val'
head = insert_at_k(head, el, val)
# Print the modified linked list
print_ll(head)
Output: 0 1 5 2
Time Complexity: O(N) worst case, when insertion happens at the tail and O(1) best case, when insertion happens at the head.
Space Complexity: O(1), as we have not used any extra space.
JavaScript Code
class Node {
constructor(data, nextNode = null) {
this.data = data;
this.next = nextNode;
}
}
// Function to print the linked list
function printLL(head) {
while (head !== null) {
console.log(head.data + " ");
head = head.next;
}
}
// Function to insert a new node with data 'el' after the node with data 'val'
function insertAtK(head, el, val) {
if (head === null) {
return null;
}
// Insert at the beginning if the value matches the head's data
if (head.data === val) {
return new Node(el, head);
}
let temp = head;
while (temp.next !== null) {
// Insert at the current position if the next node has the desired value
if (temp.next.data === val) {
const newNode = new Node(el, temp.next);
temp.next = newNode;
break;
}
temp = temp.next;
}
return head;
}
// Main function
function main() {
// Initialize list with values
const arr = [0, 1, 2];
const el = 5;
const val = 2;
// Create a linked list with the given array
let head = new Node(arr[0]);
head.next = new Node(arr[1]);
head.next.next = new Node(arr[2]);
// Insert a new node with data 'el' after the node with data 'val'
head = insertAtK(head, el, val);
// Print the modified linked list
printLL(head);
}
// Call the main function
main();
Output: 0 1 5 2
Time Complexity: O(N) worst case, when insertion happens at the tail and O(1) best case, when insertion happens at the head.
Space Complexity: O(1), as we have not used any extra space.
In case you are learning DSA, you should definitely check out our free A2Z DSA Course with videos and blogs.
Special thanks to Neerav Sethi for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article
