Deletion at the nth node of a Circular Linked List in Java

June 21, 2022

how to prepare for tcs itp interview

JAVA Program to delete a Node at the nth node of a Circular Linked List

In the process of deletion at the nth node of a circular linked list we first check if there is some data present in the list or not as deletion is not possible form an empty list. If the list is not empty we traverse till the specific position and delete the specific node using the algorithm mentioned in this article below. We can also perform deletion from:-

  • Beginning of the circular linked list.
  • End of the circular linked list.

 

Given below is the description of deletion from the nth Node of a Circular Linked List 

Deletion from nth position in a circular linked list –

  • If the list is empty we cannot delete element from it hence return as deletion is not possible.
  • If there is data present in the nodes of the list, then
  • Traverse till the specific position from where you want to delete an element.
  • Then make next pointer of previous list as next of next node.
  • Free the node that is present at specific position.
Run 
import java.util.*; 
import java.lang.*; 
import java.io.*; 
class Main 
{ 
// structure for a node 
static class Node 
{ 
    int data; 
    Node next; 
}; 
// Function to insert a node at the end of a Circular linked list 
static Node Insert(Node head, int data) 
{ 
    Node current = head; 
    
    // Create a new node 
    Node newNode = new Node(); 

    // check node is created or not 
    if (newNode == null) 
    { 
        System.out.printf("\nMemory Error\n"); 
        return null; 
    } 

    // insert data into newly created node 
    newNode.data = data; 

    // check list is empty 
    // if not have any node then 
    // make first node it 
    if (head == null) 
    { 
        newNode.next = newNode; 
        head = newNode; 
        return head; 
    } 

    // if list have already some node 
    else
    {
        // move first node to last node 
        while (current.next != head) 
        { 
            current = current.next; 
        } 
        // put first or head node address 
        // in new node link 
        newNode.next = head; 
        // put new node address into last 
        // node link(next) 
        current.next = newNode; 
    } 
    return head; 
}
// Function print data of list 
static void Display( Node head) 
{ 
    Node current = head; 
    // if list is empty, simply show message 
    if (head == null) 
    { 
        System.out.printf("\nDisplay List is empty\n"); 
        return; 
    } 
    // traverse first to last node 
    else
    { 
        do
        { 
            System.out.printf("%d ", current.data); 
            current = current.next; 
        } while (current != head); 
    } 
} 
// Function return number of nodes present in list 
static int Length(Node head) 
{ 
    Node current = head; 
    int count = 0; 
    // if list is empty 
    // simply return length zero 
    if (head == null) 
    { 
        return 0; 
    } 
    // traverse forst to last node 
    else
    { 
        do
        { 
            current = current.next; 
            count++; 
        } while (current != head); 
    } 
    return count; 
} 
static Node DeleteAtPosition( Node head, int index) 
{ 
    // Find length of list 
    int len = Length(head); 
    int count = 0; 
    Node previous = head, next = head; 
    // check list have any node 
    // if not then return 
    if (head == null) 
    { 
        System.out.printf("\nDelete Last List is empty\n"); 
        return null; 
    } 
    // given index is in list or not 
    if (index >= len || index < 0) 
    { 
        System.out.printf("\nIndex is not Found\n"); 
        return null; 
    } 
    while (len > 0) 
    { 
     // if index found delete that node 
        if (index == count) 
        { 
            previous.next = next.next; 
            
            return head; 
        } 
        previous = previous.next; 
        next = previous.next; 
        len--; 
        count++; 
    } 
    return head; 
} 
// Driver Code 
public static void main(String args[]) 
{ 
    Node head = null; 
    Scanner sc= new Scanner(System.in);
    int n,data;
    System.out.println("Enter the number of nodes you want to insert\n");
    n=sc.nextInt();
    System.out.println("Enter the data for the nodes\n");
    for(int i=0;i<n;i++)
    {
        data=sc.nextInt();
        head = Insert(head , data);
    }
    // Deleting Node at position 
    System.out.printf("Initial List: "); 
    Display(head); 
    System.out.printf("\nEnter the index of node which you want to delete ");
    int del;
    del=sc.nextInt();
    head = DeleteAtPosition(head, del); 
    Display(head); 
} 
}
Output:
Enter the number of nodes you want to insert

5
Enter the data for the nodes

11
12
13
14
15
Initial List: 11 12 13 14 15 
Enter the index of node which you want to delete 3
11 12 13 14