Select Page

Insert a Node after a given Node in Linked List

Animesh Dey
Published: October 19, 2022

View Discussion

Improve Article

Save Article

Like Article

View Discussion

Improve Article

Save Article

Like Article

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

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.
Output list will be: 1->2->3->4->5

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

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)

Source: www.geeksforgeeks.org