Deletion from the nth position in a Linked List in JAVA

July 9, 2020

JAVA Program for Deletion from the n^th position in a Linked List in JAVA

Earlier we’ve already learned about how linked lists store data and operate on them. In this page we’ll take a look at how to perform Deletion from the n^th position in a Linked List in JAVA Programming Language. To perform a deletion from the n^th node, of a list we’ll have to delete the pointer stored in (n-1)^th node and store the address of the (n+1)^th node in the address space of (n-1)^th node.

Implementation

For deletion from a Singly Linked List from n^th position We first have to check if the list is not empty, if not then continue.
Let the number of nodes be N.
Then the index of the node to be deleted is equal to n.
To delete the node n, we’ll first have to store the address stored in the node n, for the node (n+ 1), in a temporary variable.
Then ths address stored in the temporary variable will be stored in the address space of the node (n – 1), where the existing address will be of node n.

Algorithm

delete ( n )
IF n = 0
HEAD -> t.next (Address of second node)
FOR i=0 to t!=null and i<n-1
t=t.next
EXIT
Node next = t->next->next
t.next=next

Example

Input : 10-->20-->30-->40-->50-->60
        n=3
Output: 40-->50-->60-->10-->20-->30

Complexity

As we are visiting a node atmost once so the time complexity is O(N).

Code In JAVA Programming Language

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.addItem(20);
        ll.addItem(10);
        ll.display();
        ll.delete(3);  
        System.out.println("List after deletion: ");  
        ll.display();
        ll.delete(2);  
        System.out.println("List after deletion: ");  
        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 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 beginning of 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++;
    }
    void delete(int n) 
    {
        Node t = head; 
        if (n == 0) 
        { 
            head = t.next; 
            return; 
        }
        
        if (head == null) 
            return;  
            
        
        for (int i=0; t!=null && i<n-1; i++) 
            t = t.next; 
        if (t == null || t.next == null)  //if n> length of linked list 
            return; 
  
        // Node temp->next is the node to be deleted 
        // Store pointer to the next of node to be deleted 
        Node next = t.next.next; 
  
        t.next = next;  // Unlink the deleted node from list 
        } 
     
}

10–>20–>30–>40–>50–>60–>END
List after deletion: 
10–>20–>30–>50–>60–>END
List after deletion: 
10–>20–>50–>60–>END