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:
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.
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){
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.
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){
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.
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.
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:
- Array in Java
- Array length in Java
- Linear Search in Java
- Christmas Tree Pattern Program
- Memory Management in Java
- Pattern Programs in Java
- Check number is Even or Odd without using modulus operator?
