Linked List Insertion Operation

0
62
Advertisement

 

Linked List is a Linear Data Structure. In this post, we will discuss Linked List Insertion operation. As we already discussed Linked List in the previous post. You can learn about Linked List, here.

Time Complexities of Different Operations in Linked List:

Access:             O(n)

Insertion:          O(1)

Deletion:           O(1)

Search:             O(n)

Insertion in Linked List:

Linked List elements are not stored in contiguous memory, and each element(node) points to the next node using a pointer variable so it’s easy to insert elements in between the Linked List. We just only need to manipulate the pointer to point the newly created Node and that’s it. The Insertion operation is complete.

There are 3 positions where we can insert the newly created Node into the Linked List:

In all the 3 methods we first check if the inserted Node is the first Node then we insert that node as same in all the 3 methods. otherwise, we follow the respective method.

The below images shows the insertion of the 4 elements into the Linked List. this is the Starting stage of linked List:

Insertion Operation in Linked list

Insert Node at the Beginning of the Linked List:
//insert Node at the start of the Linked List
public Node insertStart(Node head, int ele){

    Node temp = head;

    //Check if Linked List is empty then add node at the first.
    if (temp == null){
        head = new Node(ele);
    }else{
        Node new_node = new Node(ele);
        new_node.next = temp;
        head = new_node;
    }
    return head;
}

Demonstration:

if we want to add the element into the Linked List we need to create the Linked List.

New node created to insert the element at beginning

now, we manipulate the pointers and add that newly created element into the existing Linked List.

first, we link the newly created node with the node that connected with the head,  new_node.next = head

new node connected with the first node

now, we remove the link between head and the first node has value 1 and connect the head node with the newly created node has value 6.

here,  head = new_node;

New Node Added into the List

 

Insert Node at the End of the Linked List:
//Insert Node at the end of the Linked List
    public Node insertEnd(Node head, int ele){
        Node temp = head;

        //Check if Linked List is empty then add node at the first.
        if (temp == null){
            head = new Node(ele);
        }else{
            while(temp.next!=null){
                temp = temp.next;
            }
            temp.next = new Node(ele);
        }

        return head;
    }

demonstration:

Here we first created a node to add at the end of the List.

New node created to insert the element at end

The last node pointing to a NULL value, so first we traverse till the last element in the linked list while checking temp.next!=null

and when we reach at the end of the Linked list then we set the pointer of the last node towards the newly created node. using code

temp.next = new_node;

 

Node added at the end

Insert the new Node after the Specified Node:
//if you want to insert element after any specified element
   public Node insertMiddle(Node head, int ele, int specifiedEle){

       Node temp = head;

       //Check if Linked List is empty then add node at the first.
       if (temp == null){
           head = new Node(ele);
       }else{
           while(temp.next!=null){
               if (temp.data == specifiedEle){
                   Node new_Node = new Node(ele);
                   new_Node.next = temp.next;
                   temp.next = new_Node;
               }
               temp = temp.next;
           }
       }
       return head;
   }

Demonstration:

First, we have to create the New Node and user also insert the node value, so a new node could be inserted after that node.

add the node after specified element

User Input: specified Element : 2

Here, first, we travel over the Linked list and search for the element that the user entered, so we can enter the element after that node.

If we found the element then we perform some pointer manipulation to add the new element after the specified element.

first, we connect the new node to the Node after the specified element new_node.next = temp.next;

link the new node withe the next of temp

Now, we remove the link between the temp node and next of temp node and link the temp node with the newly created node.

temp.next = new_node;

element added after the specified element

 

Find the below the Whole java code to insert the new Node into the Linked List.

Linked List Insertion Operation:
LinkedList.java
public class LinkedList {

    // Node class creates The Linked List Node
    static class Node{
        int data;
        Node next;

        //Constructor creates New Node and store value into data part and
        // set pointer as Null in starting.
        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    //insert Node at the start of the Linked List
    public Node insertStart(Node head, int ele){

        Node temp = head;

        //Check if Linked List is empty then add node at the first.
        if (temp == null){
            head = new Node(ele);
        }else{
            Node new_node = new Node(ele);
            new_node.next = temp;
            head = new_node;
        }
        return head;
    }

    //if you want to insert element after any specified element
    public Node insertMiddle(Node head, int ele, int specifiedEle){

        Node temp = head;

        //Check if Linked List is empty then add node at the first.
        if (temp == null){
            head = new Node(ele);
        }else{
            while(temp.next!=null){
                if (temp.data == specifiedEle){
                    Node new_Node = new Node(ele);
                    new_Node.next = temp.next;
                    temp.next = new_Node;
                }
                temp = temp.next;
            }
        }
        return head;
    }

    //Insert Node at the end of the Linked List
    public Node insertEnd(Node head, int ele){
        Node temp = head;

        //Check if Linked List is empty then add node at the first.
        if (temp == null){
            head = new Node(ele);
        }else{
            while(temp.next!=null){
                temp = temp.next;
            }
            temp.next = new Node(ele);
        }

        return head;
    }


    //Display method to perform display operation
    public void display(Node head){
        Node temp = head;

        if (temp == null){
            System.out.println("Linked List is Empty.");
        }else{
            while(temp.next!=null){
                System.out.print(String.format("%d--->",temp.data));
                temp = temp.next;
            }
            System.out.print(String.format("%d--->NULL",temp.data));
        }
        System.out.println();
    }

}
LinkedListimplementation.java
import java.util.Scanner;

public class LinkedListImplementation {

    public static void main(String[] args) {

        Scanner scanner  = new Scanner(System.in);

        System.out.println("=================================");

        LinkedList list = new LinkedList();
        LinkedList.Node head = null;

        head = list.insertEnd(head,10);
        head = list.insertEnd(head,20);
        head = list.insertEnd(head,30);
        head = list.insertEnd(head,40);
        head = list.insertEnd(head,50);
        head = list.insertEnd(head,60);

        System.out.println("Dummy Linked List : ");

        list.display(head);

        System.out.println("=================================");

        System.out.println("Enter the element to Insert at The start : ");
        int eleStart = scanner.nextInt();

        head = list.insertStart(head,eleStart);

        System.out.println("=================================");

        System.out.println("Linked list after Insertion at the Start : ");

        list.display(head);
        System.out.println("=================================");

        System.out.println("Enter the element to Insert at The End : ");
        int eleEnd = scanner.nextInt();

        head = list.insertEnd(head,eleEnd);

        System.out.println("=================================");
        System.out.println("Linked list after Insertion at the end : ");

        list.display(head);
        System.out.println("=================================");

        System.out.println("Enter the element to Insert at The End : ");
        int eleMiddle = scanner.nextInt();

        System.out.println("Enter the Specified element to insert element after specified element : ");
        int specifiedEle = scanner.nextInt();

        head = list.insertMiddle(head,eleEnd,specifiedEle);

        System.out.println("=================================");
        System.out.println("Linked list after Insertion at the Specified Position: ");

        list.display(head);
        System.out.println("=================================");
    }
}


Output 1:

=================================
Dummy Linked List : 
10--->20--->30--->40--->50--->60--->NULL
=================================
Enter the element to Insert at The start : 
5
=================================
Linked list after Insertion at the Start : 
5--->10--->20--->30--->40--->50--->60--->NULL
=================================
Enter the element to Insert at The End : 
3
=================================
Linked list after Insertion at the end : 
5--->10--->20--->30--->40--->50--->60--->3--->NULL
=================================
Enter the element to Insert at The End : 
3
Enter the Specified element to insert element after specified element : 
30
=================================
Linked list after Insertion at the Specified Position: 
5--->10--->20--->30--->3--->40--->50--->60--->3--->NULL
=================================

 

Hope you like this post.

If you have any doubt please feel free to comment below.

Learn Linked List Implementation using Java

Learn Stack Implementation using LinkedList

Learn Stack implementation using Array

 

You may also learn these to build the Knowledge:

LEAVE A REPLY

Please enter your comment!
Please enter your name here