Deletion from the nth position in a Linked List in JAVA

JAVA Program for Deletion from the nth 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 nth position in a Linked List in JAVA Programming Language. To perform a deletion from the nth 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.

Deletion from nth position in a singly linked list

Implementation

  • For deletion from a Singly Linked List from nth 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
JAVA Program for Deletion from the nth node in a Singly Linked List

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