In this Linked List tutorial, we will see all about the insert operation in a singly linked list. In the insert operation, we add a new node to the linked list at any position.
In a Singly Linked List, we can insert a node at the following positions:
- At the beginning of the linked list.
- At a specific position of the linked list.
- After a given node of the linked list.
- At the end of the linked list.
1. Insert a node at the beginning of the linked list
To insert a new node at the beginning or front position in the linked list, follow these steps:
Create a newNode with the given value.
Check whether the list is Empty (head == NULL).
If the list is Empty, set newNode → next = NULL and head = newNode.
If the list is Not Empty, set newNode → next = head and head = newNode.
In the example below, we will see how to insert a new node at the beginning of the linked list.
// Java Program to insert a new node at the beginning of Linked List
public class InsertNodeAtBeginningInSLL {
// method to insert a new node at the beginning of the linked list
static Node insertAtFront(Node head, int data) {
// Create a node with the given parameter data
Node node = new Node(data);
// Assigning next node reference from the head
node.next = head;
// Return the new node as the new head of the list
return node;
}
// method to print linked list
public static void printLinkedList(Node head) {
Node tempNode = head;
while (tempNode != null) {
System.out.print(" " + tempNode.data);
tempNode = tempNode.next;
}
System.out.println(); // Line break
}
public static void main(String[] args) {
// create a head node
Node head = new Node(40);
head.next = new Node(60);
head.next.next = new Node(80);
head.next.next.next = new Node(100);
// Print the current linked list data
System.out.println("Linked List values: ");
printLinkedList(head);
// Insert a new node at the beginning of the linked list
System.out.println("After inserting a Node at the beginning:");
head = insertAtFront(head, 20); // Inserting 20 at the beginning
// Print the linked list after inserting a new node at the beginning
printLinkedList(head);
}
}Linked List values: 40 60 80 100 After inserting a Node at the beginning: 20 40 60 80 100
2. Insert a node at a specific position of the linked list
To insert a new node at a specific position of the linked list, follow these steps:
Create a newNode with the given value.
If the position is 1, set newNode → next = head and head = newNode.
Otherwise, define a node pointer current, initialize it with head and move it forward until it reaches the node just before the given position.
If current becomes NULL, the position is out of bounds and insertion is not possible.
Finally, set newNode → next = current → next and current → next = newNode.
In the example below, we will see how to insert a new node at a specific position in the linked list.
// Java Program to Insert a Node At a Specific Position in Linked List
public class InsertNodeAtSpecificPositionInSLL {
// Method to insert a new node at the specific position in
// the linked list
static Node insertAtSpecPosition(Node head, int position, int data) {
// Create a node
Node node = new Node(data);
// If the position is at the beginning means 1
if (position == 1) {
node.next = head;
head = node;
return head;
}
// If the position is other than 1
Node current = head;
for (int i = 1; i < position - 1 && current != null; ++i) {
current = current.next;
}
// If the position is out of bounds
if (current == null) {
System.out.println("ERROR: Position is out of bounds.");
return head;
}
node.next = current.next;
current.next = node;
return head;
}
// Print a linked list
static void printLinkedList(Node head) {
while (head != null) {
System.out.print(" " + head.data);
head = head.next;
}
System.out.println(); // New Line
}
public static void main(String[] args) {
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(40);
head.next.next.next = new Node(50);
System.out.print("Linked list before inserting a new node:\n");
printLinkedList(head);
// Insert a new node with data 30 at position 3
int data = 30, position = 3;
head = insertAtSpecPosition(head, position, data);
System.out.print("\nLinked list after inserting 30 at the position " + position + ":\n");
printLinkedList(head);
}
}Linked list before inserting a new node: 10 20 40 50 Linked list after inserting 30 at the position 3: 10 20 30 40 50
3. Insert a node after a given node of the linked list
To insert a new node after a given node in the linked list, follow these steps:
Create a newNode with the given value.
Check whether the list is Empty (head == NULL).
If the list is Empty, set newNode → next = NULL and head = newNode.
If the list is Not Empty, define a node pointer temp and initialize it with head.
Keep moving temp to its next node until it reaches the node after which we want to insert the newNode (until temp → data is equal to the key, the value of the node after which we want to insert the newNode).
Every time, check whether temp has reached the last node. If it has and the key was not found, display 'Given node is not found in the list! Insertion not possible!' and stop. Otherwise move temp to the next node.
Finally, set newNode → next = temp → next and temp → next = newNode.
In the example below, we will see how to insert a new node after a given node in the linked list.
// Java Program to Insert a Node after a Given Node in Linked List
public class InsertNodeAtAfterGivenNodeInSLL {
// Method to insert a new Node after a given Node
static Node insertAfter(Node head, int key, int newData) {
Node node = head;
// Iterate a list and find out the key
while (node != null) {
if (node.data == key)
break;
node = node.next;
}
// if node becomes null means, given key is not
// found in linked list
if (node == null)
return head;
// Create a new node with the given data and point
// the next of newNode to node's next &
// point current next to newNode
Node newNode = new Node(newData);
newNode.next = node.next;
node.next = newNode;
return head;
}
static void printLinkedList(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
System.out.println(); // New Line
}
public static void main(String[] args) {
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(40);
head.next.next.next = new Node(50);
System.out.println("Linked List data: ");
printLinkedList(head);
int key = 20, newData = 30;
// Insert a new node 30, after the node 20
head = insertAfter(head, key, newData);
System.out.println("After insertion, Linked List data: ");
printLinkedList(head);
}
}Linked List data: 10 20 40 50 After insertion, Linked List data: 10 20 30 40 50
4. Insert a node at the end of the linked list
To insert a new node at the end or last position in the linked list, follow these steps:
Create a newNode with the given value and newNode → next as NULL.
Check whether the list is Empty (head == NULL).
If the list is Empty, set head = newNode.
If the list is Not Empty, define a node pointer temp and initialize it with head.
Keep moving temp to its next node until it reaches the last node in the list (until temp → next is equal to NULL).
Set temp → next = newNode.
In the example below, we will see how to insert a new node at the end of the linked list.
// Java Program to Insert a Node at the End of Linked List
public class InsertNodeAtEndInSLL {
// Method to insert a new node at the end of the linked list
static Node insertAtEnd(Node head, int data) {
// Create a new node
Node node = new Node(data);
// If the Linked List is empty, make the new
// node as the head and return
if (head == null) {
return node;
}
// Store the head reference in a temporary variable
Node last = head;
// Traverse till the last node of the linked list
while (last.next != null) {
last = last.next;
}
// Change the next pointer of the last node to point to the new node
last.next = node;
// Return the head of the list
return head;
}
// Method to print linked list
static void printLinkedList(Node node) {
while (node != null) {
System.out.print(" " + node.data);
node = node.next;
}
}
public static void main(String[] args) {
// Create a linked list
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
head.next.next.next = new Node(40);
System.out.print("Linked list values: ");
printLinkedList(head);
// Inserting a node at the end of the linked list
head = insertAtEnd(head, 50);
System.out.print("\nLinked List values, after inserting at the end: ");
printLinkedList(head);
}
}Linked list values: 10 20 30 40 Linked List values, after inserting at the end: 10 20 30 40 50