Insert a Node after a given Node in Linked List
Given a linked list, the task is to insert a new node after a given node of the linked list.
Example:
Input: LinkedList = 2->3->4->5, NewNode = 1, InsertAfter = 2
Output: LinkedList = 2->1->3->4->5Input: LinkedList = , NewNode = 1, InsertAfter = 2
Output: No such node found
Approach:
To insert a node after a given node in a Linked List, we need to:
- Check if the given node exists or not.
- If it do not exists,
- terminate the process.
- If the given node exists,
- Make the element to be inserted as a new node
- Change the next pointer of given node to the new node
- Now shift the original next pointer of given node to the next pointer of new node
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.
Below is the implementation of the approach.
C++
// C++ program to show inserting a node // after a given node in given Linked List #include <bits/stdc++.h> using namespace std; // A linked list node class Node { public : int data; Node* next; }; // Given a node prev_node, insert a new // node after the given prev_node void insertAfter(Node* prev_node, int new_data) { // 1. check if the given prev_node // is NULL if (prev_node == NULL) { cout << "The given previous node cannot be NULL" ; return ; } // 2. allocate new node Node* new_node = new Node(); // 3. put in the data new_node->data = new_data; // 4. Make next of new node // as next of prev_node new_node->next = prev_node->next; // 5. move the next of prev_node // as new_node prev_node->next = new_node; } // Function to insert element in LL void push(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } // This function prints contents of // linked list starting from head void printList(Node* node) { while (node != NULL) { cout << " " << node->data; node = node->next; } cout << "\n" ; } // Driver code int main() { // Start with the empty list Node* head = NULL; push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); cout << "Created Linked list is: " ; printList(head); // Insert 1 at the beginning. insertAfter(head, 1); cout << "After inserting 1 after 2: " ; printList(head); return 0; } |
C
// C program to show inserting a node // after a given node in given Linked List #include <stdio.h> #include <stdlib.h> // A linked list node struct Node { int data; struct Node* next; }; // Given a node prev_node, insert a new // node after the given prev_node void insertAfter( struct Node* prev_node, int new_data) { // 1. check if the given prev_node // is NULL if (prev_node == NULL) { printf ( "The given previous node cannot be NULL" ); return ; } // 2. allocate new node struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); // 3. put in the data new_node->data = new_data; // 4. Make next of new node // as next of prev_node new_node->next = prev_node->next; // 5. move the next of prev_node // as new_node prev_node->next = new_node; } // Function to insert element in LL 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); (*head_ref) = new_node; } // This function prints contents of // linked list starting from head void printList( struct Node* node) { while (node != NULL) { printf ( " %d" , node->data); node = node->next; } printf ( "\n" ); } // Driver code int main() { // Start with the empty list struct Node* head = NULL; push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); printf ( "Created Linked list is: " ); printList(head); // Insert 1 at the beginning. insertAfter(head, 1); printf ( "After inserting 1 after 2: " ); printList(head); return 0; } |
Java
// Java program to show inserting a node // after a given node in given Linked List import java.io.*; // A linked list node class Node { int data; Node next; } // Class to insert elements in LL class LinkedList { Node head; // head of list // Given a node prev_node, insert a new // node after the given prev_node void insertAfter(Node prev_node, int new_data) { // 1. check if the given prev_node // is NULL if (prev_node == null ) { System.out.println( "The given previous node cannot be NULL" ); return ; } // 2. allocate new node Node new_node = new Node(); // 3. put in the data new_node.data = new_data; // 4. Make next of new node // as next of prev_node new_node.next = prev_node.next; // 5. move the next of prev_node // as new_node prev_node.next = new_node; } // Function to insert element in LL void push( int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head; head = new_node; } // This function prints contents of // linked list starting from head void printList() { Node node = head; while (node != null ) { System.out.print( " " + node.data); node = node.next; } System.out.println(); } // Driver code public static void main(String[] args) { // Start with the empty list LinkedList llist = new LinkedList(); llist.push( 6 ); llist.push( 5 ); llist.push( 4 ); llist.push( 3 ); llist.push( 2 ); System.out.print( "Created Linked list is: " ); llist.printList(); // Insert 1 at the beginning. llist.insertAfter(llist.head, 1 ); System.out.print( "After inserting 1 after 2: " ); llist.printList(); } } |
Python3
# Python3 program to show inserting a node # after a given node in given Linked List # Node class class Node: # Function to initialise the node object def __init__( self , data): self .data = data # Assign data self . next = None # Initialize next as null # Linked List class contains a Node object class LinkedList: # Function to initialize head def __init__( self ): self .head = None # Function to insert a new node at the beginning def push( self , new_data): new_node = Node(new_data) new_node. next = self .head self .head = new_node # This function is in LinkedList class. Inserts a # new node after the given prev_node. This method is # defined inside LinkedList class shown above */ def insertAfter( self , prev_node, new_data): # 1. check if the given prev_node exists if prev_node is None : print ( "The given previous node must inLinkedList." ) return # 2. create new node & # Put in the data new_node = Node(new_data) # 4. Make next of new Node as next of prev_node new_node. next = prev_node. next # 5. make next of prev_node as new_node prev_node. next = new_node # Utility function to print the linked list def printList( self ): temp = self .head while temp: print (temp.data, end = " " ) temp = temp. next # Code execution starts here if __name__ = = "__main__" : # Start with the empty list llist = LinkedList() llist.push( 6 ) llist.push( 5 ) llist.push( 4 ) llist.push( 3 ) llist.push( 2 ) print ( "Created linked list is: " ) llist.printList() # Insert 1, after 2. llist.insertAfter(llist.head, 1 ) print ( "\nAfter inserting 1 after 2: " ) llist.printList() |
C#
// C# program to show inserting a node // after a given node in given Linked List using System; class GFG { public Node head; // head of list /* Linked list Node*/ public class Node { public int data; public Node next; public Node( int d) { data = d; next = null ; } } /* Inserts a new Node at front of the list. */ public void push( int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } /* Inserts a new node after the given prev_node. */ public void insertAfter(Node prev_node, int new_data) { /* 1. Check if the given Node is null */ if (prev_node == null ) { Console.WriteLine( "The given previous" + " node cannot be null" ); return ; } /* 2 & 3: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 4. Make next of new Node as next of prev_node */ new_node.next = prev_node.next; /* 5. make next of prev_node as new_node */ prev_node.next = new_node; } /* This function prints contents of linked list starting from the given node */ public void printList() { Node tnode = head; while (tnode != null ) { Console.Write(tnode.data + " " ); tnode = tnode.next; } } // Driver Code public static void Main(String[] args) { /* Start with the empty list */ GFG llist = new GFG(); llist.push(6); llist.push(5); llist.push(4); llist.push(3); llist.push(2); Console.Write( "Created Linked list is: " ); llist.printList(); // Insert 1 after 2 llist.insertAfter(llist.head, 1); Console.Write( "\nAfter inserting 1 after 2: " ); llist.printList(); } } // This code is contributed by Rajput-Ji |
Javascript
// Javascript program to show inserting a node // after a given node in given Linked List // A linked list node class Node { constructor(data) { this .data = data; this .next = null ; } } // Class to insert elements in LL class LinkedList { constructor() { this .head = null ; } // Given a node prev_node, insert a new // node after the given prev_node insertAfter(prev_node, new_data) { // 1. check if the given prev_node // is NULL if (!prev_node) { console.log( "The given previous node cannot be NULL" ); return ; } // 2. allocate new node // 3. pass the data through constructor const new_node = new Node(new_data); // 4. Make next of new node // as next of prev_node new_node.next = prev_node.next; // 5. move the next of prev_node // as new_node prev_node.next = new_node; } // Function to insert element in LL push(new_data) { const new_node = new Node(new_data); new_node.next = this .head; this .head = new_node; } // This function prints contents of // linked list starting from head printList() { let node = this .head; const result = []; while (node !== null ) { result.push(node.data); node = node.next; } console.log(result.join( " " )); } } // Driver code const llist = new LinkedList(); llist.push(6); llist.push(5); llist.push(4); llist.push(3); llist.push(2); console.log( "Created Linked list is:" ); llist.printList(); // Insert 1 at the beginning. llist.insertAfter(llist.head, 1); console.log( "After inserting 1 after 2:" ); llist.printList(); // puligokulakishorereddy |
Output
Created Linked list is: 2 3 4 5 6 After inserting 1 after 2: 2 1 3 4 5 6
Time Complexity: O(1)
Auxiliary Space: O(1)