0
40

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)`

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:

###### 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){

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

Demonstration:

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

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`

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;`

###### 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){

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

}```

demonstration:

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

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;`

###### 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){

//Check if Linked List is empty then add node at the first.
if (temp == null){
}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;
}
}
}```

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.

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;`

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;`

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

```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){

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

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

//Check if Linked List is empty then add node at the first.
if (temp == null){
}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;
}
}
}

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

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

}

//Display method to perform display operation

if (temp == null){
}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();
}

}
```
```import java.util.Scanner;

public static void main(String[] args) {

Scanner scanner  = new Scanner(System.in);

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

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

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

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

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

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

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

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

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();

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

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

Output 1:

```=================================
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.

You may also learn these to build the Knowledge: