Insertion at nth position in singly Linked List

Insertion at nth Position in JAVA

A single linked list is a collection of Data Elements which stores the address to the next element in the collection along with them. For Insertion at nth position in singly Linked List we’ll first have to change the address in the nth-1 position to the address of the inserted element and then we’ll have to store the address of the previous nth element in to the newly inserted element.

JAVA Program for insertion at nth position in a Linked List

Implementation

For Insertion at nth position in singly Linked List we’ll have to follow these steps:

  • First, Traverse the list from head to n-1 position
  • After traversing the list add the new node and allocate memory space to it.
  • Point the next pointer of the new node to the next of current node.
  • Point the next pointer of current node to the new node.

Algorithm for Insertion at nth position in singly Linked List

  • IF HEAD == NULL
    EXIT
  • ELSE
  • NEW_NODE = ADDNODE()
  • NEW_NODE -> DATA = ITEM
  • SET TEMP = HEAD
  • SET I = 0
  • REPEAT
  • TEMP = TEMP → NEXT
  • IF TEMP = NULL
  • EXIT
  • PTR → NEXT = TEMP → NEXT
  • TEMP → NEXT = PTR
  • SET PTR = NEW_NODE
  • EXIT
Insertion at the nth node in Linked List in Java

Code for Insertion in a Linked List at a Given Node

import java.util.*;

public class Main
{
public static void main(String[] args) throws Exception {
LinkedList ll = new LinkedList();
ll.addItem(60);
ll.addItem(50);
ll.addItem(40);
ll.addItem(30);
ll.addAt(90, 1);
ll.addAt(1000, 3);
ll.addAt(0, 3);
ll.addAt(0, 7);
ll.display();
}
}

class LinkedList {

private class Node {
int data;
Node next;
// Node constructor
// There are two fields in the node- data and address of next node
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
}

private Node head;
private Node tail;
private int size;
// Linked list constructor

public LinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}

// Function to find the size of linked list
public int size() {
return this.size;
}

// Function to check whether linked list is empty or not
public boolean isEmpty() {
return this.size() == 0;
}

// Function to traverse and print the linked list
public void display() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + "–>");
// Set temp to point to the next node
temp = temp.next;
}
System.out.println("END");
}

// Function to add a node in linked list
public void addItem(int item) {
// Create a temp node which points to head
Node temp = new Node(item, head);
// If linked list is empty, temp is the head and tail node both
if (this.size == 0) {
this.head = this.tail = temp;
}
// else set the head such that it now points to temp node
else {
this.head = temp;
}
this.size++;
}

// Function to add a node at any position in linked list
public void addAt(int item, int index) throws Exception {
// Invalid cases
if (index < 0 || index > this.size) {
throw new Exception("Index out of bound");
}
// Else find the node at (index-1) and change the next pointer
else {
// Create a node n pointing to null initially
Node n = new Node(item, null);
// Getting node at (index-1)
int i = 0;
Node nm1 = head;
while (i < (index-1)) {
nm1 = nm1.next;
i++;
}
// Now nm1 is the node at (index-1)
// Node np1 is the node at (index)
Node np1 = nm1.next;
nm1.next = n;
n.next = np1;
this.size++;
}
}
}