Linked List: Program to insert a node after given node in the linked list


Write a program to insert a node after the given node in the linked list

Linked list is a series of nodes in which each node contains a data field and
reference (pointer) to the next node in the list.

 
Inserting a new node after a given node

For inserting a node after a given node, refer the following steps

  1. Create pointer current that points to head
  2. Create new node with variable name as ‘temp’
  3. We traverse the linked list till we find the given node using ‘current’ pointer
  4. We check whether the given node is in between other nodes or its the last node
  5. Accordingly insert the temp node
 
Complexity

Time Complexity : O(n) , where n is the size of linked list
Space Complexity : O(1)

 
Java Code
   import java.util.*;

    class InsertNodeAfterLL {
        class Node {
            // initialising data field and next pointer of node
            int data;
            Node next;
         
            Node(int d) {
                this.data = d;
            }
        }
    
        static Node head;
     
            // creating a linked list using array
        public void buildLinkedlist(int A[], int noOfNodes) {
            int i;
            Node temp, last;
            temp = new Node(A[0]);
            temp.next = null;
            head = temp;
            last = temp;
            for (i = 1; i < noOfNodes; i++) {
                temp = new Node(A[i]);
                temp.next = null;
                last.next = temp;
                last = temp;
            }
        }
     
        // printing of linkedList
        public void printLinkedlist() {
            List allNodesList = new ArrayList<>();
            Node temp = head;
            while (temp != null) {
                allNodesList.add(Integer.toString(temp.data));
                temp = temp.next;
            }
            System.out.println(String.join(" -> ", allNodesList));
     
        }
     
        // insertion of node after given node in linked list
        public void insertAtPosition(int new_data, int key) {
            
            Node temp = new Node(new_data);
            Node current = head;
            while (current != null) {
                if(current.data == key){
                    if(current.next == null){
                        current.next = temp;
                        return;
                    }else{
                        temp.next = current.next;
                        current.next = temp;
                        return;
                    }
                }else{
                    
                    current = current.next;
                }
            }
            
        }
     
        public static void main(String[] args) {
            int[] linkedlistElements = new int[] { 10, 30, 50, 40 };
            int numberOfNodes = 4;
            // initialising object of linkedlist class
            InsertNodeAfterLL ll = new InsertNodeAfterLL();
            ll.buildLinkedlist(linkedlistElements,numberOfNodes );
            System.out.println("Given Linked List ");
            ll.printLinkedlist();
            int givenNode = 50;
            System.out.println("Inserting node 80 after given node " + givenNode);
            ll.insertAtPosition(80, givenNode);
            ll.printLinkedlist();
        }
  }
Output

Given Linked List
10 -> 30 -> 50 -> 40
Inserting node 80 after given node 50
10 -> 30 -> 50 -> 80 -> 40



Thanks for feedback.



Read More....
Clone a Linked List
Find the middle of linked list with odd no of nodes
Check if linked list nodes form a palindrome
Delete a node at specific position from linked list
Delete a node from linked list
Detect if cycle is present in a linked list