Circular Linked List Insertion and Deletion in Java

Introduction:

A circular linked list is a particular kind of linked list in which each node points to each other node in a full circle. In other words, the linked list in this variation does not contain a null element at the end.

We obtain a few advantages with these basic changes:

• The circular linked list's nodes can all be used as beginning points.
• As a result, any node can be used to begin a traversal of the entire list.
• Enqueue and dequeue actions are simple to carry out since the circular linked list's end node contains a pointer to the first node.

In the queue data structure's implementation, this is quite helpful.

The only difference in performance between circular linked list and other linked list implementations is that traversing from the head node to the last node can be completed in constant time. This is a linear procedure for classic linked lists.

Implementation and Operations of Circular Linked List:

1. Node Insertion at Beginning
2. Node Insertion at End
3. Node Insertion at a Position
4. Node Deletion at Beginning
5. Node Deletion at End
6. Node Deletion at a Position

1. Node Insertion at Beginning:

Steps to insert a node at first:

There are two instances that can be taken into consideration for Insertion at the Beginning of a Circular Linked List in Java.

If the circular linked list is empty:

• It's simple to add an element to an empty circular list.
• The head and tail of a circular linked list both point to the first member.

If the circular linked list is not empty:

• The head of a circular linked list is the first element. It keeps the data for the subsequent node in the circular relationship.
• To add an element to the linked list's starting position. The new node should be the new head of the circular linked list, pointing in the direction of the outgoing head.
• The linked list is circular since it may be traversed from beginning to end because the tail is the final node that points back to the first note.
• To update the node tail, referring to the newly inserted node, one must add a node at the beginning. The new node will now be at the beginning of the circular Linked list.

import java.lang.*;
class Main
{
 public static void main(String[] args) {
 Main Obj = new Main();
 Obj.insertion_Begin(23);
 Obj.insertion_Begin(21);
 Obj.insertion_Begin(17);
 Obj.insertion_Begin(15);
 Obj.insertion_Begin(10);
 Obj.display();
 }
public class Node
 {
 int ele;
 Node next;
 Node previous;
public Node(int ele)
 {
 this.ele = ele;
 }
 }
 public Node head = null;
 public Node tail = null;
 int size=0;
 public void insertion_Begin(int ele){
 Node newEle = new Node(ele);
 if(head == null)
 {
 head = newEle;
 tail = newEle;
 newEle.next = head;
 newEle.previous=head;
 }
 else
 {
 head.previous = newEle;
 newEle.previous=tail;
 newEle.next = head;
 tail.next = newEle;
 head=newEle;
 }
 size++;
 }
public void display()
 { //display function
 Node curr = head;
 if(head == null)
 {
 System.out.println("Circular Linked List is empty");
 }
 else
 {
 System.out.println("Nodes present in the circular Linked List :");
 do{
 System.out.print(" "+ curr.ele);
 curr = curr.next;
 }while(curr != head);
 System.out.println();
 }
 }
}

2. Node Insertion at Beginning:

Steps to insert a node at end:

There are two instances that can be taken into consideration for Insertion at the end of a Circular Linked List in Java.

If the circular linked list is empty:

• The new node will be added as the head if the circular link is empty, which indicates that the head is null.
• Since there is just one element, both the head and the tail will point in the direction of the head.

If the circular linked list is not empty:

• The head of a circular linked list is the first element. It can be thought of as the list's beginning and points to the following element.
• The circular linked list's final member, the tail, points in the direction of the head, giving the list its circular appearance.
• The final node will be the tail if the list contains elements and is not empty.
• A circular linked list's existing tail should be swapped out for the new node in order to insert an entry at the end.
• It has evolved into the new tail by switching the node that the current tail points to for the recently inserted node.
• The element is now added at the end of the circular linked list by making the new tail point in the direction of the head.

import java.lang.*;
class Main {
 public static void main(String[] args)
 {
 Main Obj = new Main();
Obj.insertion_End(1);
 Obj.insertion_End(5);
 Obj.insertion_End(7);
 Obj.insertion_End(11);
 Obj.insertion_End(13);
 Obj.display();
 }
 public class Node
 {
 int ele;
 Node next;
 Node previous;
 public Node(int ele)
 {
 this.ele = ele;
 }
 }
 public Node head = null;
 public Node tail = null;
 int size=0;
 public void insertion_End(int ele)
 {
 Node newEle=new Node(ele);
 if(head == null)
 {
 head = newEle;
 tail = newEle;
newEle.next = head;
 newEle.previous=head;
 }
 else
 {
 tail.next=newEle;
 newEle.next=head;
 newEle.previous=tail;
 head.previous=newEle;
 tail=newEle;
 }
 }
 public void display()
 { //display function
 Node curr = head;
 if(head == null)
 {
 System.out.println("Circular Linked List is empty");
 }
 else
 {
 System.out.println("Nodes present in circular Linked List ");
 do
 {
 System.out.print(" "+ curr.ele);
 curr = curr.next;
}while(curr != head);
 System.out.println();
 }
 }
}

3. Node Insertion at a Position:

Steps to insert a node at a position:

• The three nodes must be taken consideration when adding a new node anywhere between the head and the tails.
• Current nth node must point towards current (n+1)th node, and current nth node must point towards current (n-1)th node.
• The node (n-1)th address of the following node must first be copied into the address portion of the new node. We will count it as n+1 after the insertion is successful because it refers to the node.
• The (n-1)th node's address should be changed to the new node's address.
• A circular linked list node can be inserted into at any position in this manner.

Program:

import java.lang.*;
class Main {
 public static void main(String[] args)
 {
Main Obj = new Main();
 Obj.insertion_Begin(10);
 Obj.insertion_Begin(7);
 Obj.insertion_Begin(9);
 Obj.insertion_Position(2,14);
 Obj.insertion_Position(3,17);
 Obj.display();
 }
 public class Node
 {
 int ele;
 Node next;
 Node previous;
 public Node(int ele)
 {
 this.ele = ele;
 }
 }
 public Node head = null;
 public Node tail = null;
 int size=0;
 public void insertion_Begin(int ele)
 {
 Node newEle = new Node(ele);
else
 {
 head.previous = newEle;
 newEle.previous=tail;
 newEle.next = head;
 tail.next = newEle;
 head=newEle;
 }
 size++;
 }
 public void insertion_Position(int n, int data)
 {
 int len = getLength();
 if (n == 0)
 {
 insertion_Begin(data);
 return;
 }
 if (n < 1 || len < n)
 System.out.println("Invalid position entered");
 Else
{
 Node newNode = new Node(data);
 newNode.next = null;
 newNode.previous = null;
 Node nthNode = head;
while (--n > 1) {
 nthNode = nthNode.next;
 }
 Node nextNode = nthNode.next;
 nextNode.previous = newNode;
 newNode.next = nextNode;
 newNode.previous = nthNode;
 nthNode.next = newNode;
 }
}
 public int getLength()
 {
 int size = 0;
 Node temp=head;
 while (temp != tail)
 {
 temp = temp.next;
 size++;
 }
 return size;
 }
public void display()
 { //display function
 Node curr = head;
 if(head == null) {
 System.out.println("Circular Linked List is empty");
 }
else
 {
 System.out.println("Nodes present in circular Linked List ");
 do{
 System.out.print(" "+ curr.ele);
 curr = curr.next;
 }while(curr != head);
 System.out.println();
 }
 }
}

4. Node Deletion at Beginning:

Steps to delete a node at first:

• A reference variable called head in a circular linked list points to the very first node. In a circular link, the first node holds the data for the following node.
• The linked list is circular because it may be traversed from beginning to end because the tail is the final node that points back to the first node.
• To remove an element from the linked list's starting position. The first node should be removed, and the second node should now be the first entry of the circular linked list with the reference pointing to it.
• To modify the node tail, which refers to the second node, means to eliminate the node at the beginning.
• This will result in the deletion of the first node from the circular linked list and the second node becoming the first node.

Program:

import java.lang.*;
public class Main {
 public static void main(String[] args)
 {
 Main Obj = new Main();
 Obj.insert(9);
 Obj.insert(14);
 Obj.insert(21);
 Obj.insert(23);
System.out.println("Circular Linked List Before Deletion");
 Obj.display();
Obj.deletion_First();
 System.out.println("Circular Linked List After Deletion");
 Obj.display();
 }
 public class Node
 {
 int ele;
 Node next;
 Node previous;
 public Node(int ele)
 {
 this.ele = ele;
 }
 }
 public Node head = null;
 public Node tail = null;
 public void display()
 {
 Node temp = head;
 if(head == null)
 {
 System.out.println("NULL");
 }
else
 {
 do{
System.out.print(" "+ temp.ele);
 temp = temp.next;
 }while(temp != head);
 System.out.println();
 }
 }
 public void insert(int ele)
 {
 Node newNode = new Node(ele);
 if(head == null)
 {
 head = newNode;
 tail = newNode;
 newNode.next = head;
 newNode.previous=head;
 }
 else
 {
 tail.next = newNode;
 newNode.previous=tail;
 tail = newNode;
 tail.next = head;
 }
 }
 public void deletion_First()
 {
if(head == null)
 {
 return;
 }
 else
 {
 if(head != tail )
 {
 head = head.next;
 tail.next = head;
 }
 else
 {
 head = tail = null;
 }
 }
 }
}

5. Node Deletion at End:

Steps to delete a node at End:

• A head is a reference to the first node of a circular linked list, which is thought of as the list's beginning and points to the following element.
• The circular linked list's last entry, the tail, points in the direction of the first element, giving the list its circular appearance.
• The final node will be the tail if the list contains elements and is not empty.
• A circular linked list's current tail must be eliminated in order to remove an element at the end of the list.
• It has been transformed into the new tail by switching the node that the second-to-last node refers to to the first element.
• The element is removed from the circular linked list's end in this manner.

Program:

import java.lang.*;
public class Main {
 public static void main(String[] args)
 {
 Main Obj = new Main();
 Obj.insert(9);
 Obj.insert(14);
 Obj.insert(21);
 Obj.insert(23);
 System.out.println("Circular Linked List Before Deletion");
 Obj.display();
Obj.deletion_First();
 System.out.println("Circular Linked List After Deletion");
 Obj.display();
 }
public class Node
 {
 int ele;
 Node next;
 Node previous;
 public Node(int ele)
 {
 this.ele = ele;
 }
 }
 public Node head = null;
 public Node tail = null;
 public void display()
 {
 Node temp = head;
 if(head == null)
 {
 System.out.println("NULL");
 }
 else
 {
 do{
 System.out.print(" "+ temp.ele);
 temp = temp.next;
 }while(temp != head);
 System.out.println();
 }
 }
public void insert(int ele)
 {
 Node newNode = new Node(ele);
 if(head == null)
 {
 head = newNode;
 tail = newNode;
 newNode.next = head;
 newNode.previous=head;
 }
 else
 {
 tail.next = newNode;
 newNode.previous=tail;
 tail = newNode;
 tail.next = head;
 }
 }
 public void deletion_First()
 {
 if(head == null)
 {
 return;
 }
 else
 {
 if(head != tail )
 {
Node curr=head;
 while(curr.next!=tail)
 {
 curr=curr.next;
 }
 tail=curr;
 tail.next=head;
 head.previous=tail;
 }
 else
 {
 head = tail = null;
 }
 }
 }
}

6. Node Deletion at a Position:

Steps to delete a node at a Position:

• A return as deletion is not possible because the list cannot have any elements removed from it if it is empty.
• Traverse until you reach the precise location where you want to delete an element if there is data existing in the list's nodes.
• Make the next list's next pointer the next node over after that.
• At a certain location, release the node that is there.

Program:

import java.lang.*;
public class Main {
 public static void main(String[] args)
 {
 Main Obj = new Main();
 Obj.insert(9);
 Obj.insert(14);
 Obj.insert(21);
 Obj.insert(23);
 System.out.println("Circular Linked List Before Deletion");
 Obj.display();
 Obj.deletion_Position(2);
 System.out.println("Circular Linked List After Deletion");
 Obj.display();
 }
public class Node
 {
 int ele;
 Node next;
 Node previous;
 public Node(int ele)
 {
 this.ele = ele;
 }
 }
 public Node head = null;
 public Node tail = null;
 public void display()
 {
 Node temp = head;
 if(head == null)
 {
 System.out.println("NULL");
 }
else
 {
 do{
 System.out.print(" "+ temp.ele);
 temp = temp.next;
 }while(temp != head);
 System.out.println();
 }
public void insert(int ele)
 {
 Node newNode = new Node(ele);
 if(head == null)
 {
 head = newNode;
 tail = newNode;
 newNode.next = head;
 newNode.previous=head;
 }
 else
 {
 tail.next = newNode;
 newNode.previous=tail;
 tail = newNode;
 tail.next = head;
 }
 }
 public int Length(Node head)
 {
 Node curr = head;
 int count = 0;
 if (head == null)
 {
 return 0;
 }
 else
 {
do
 {
 curr = curr.next;
 count++;
 } while (curr != head);
 }
 return count;
 }
 public void deletion_Position (int n)
 {
 if (head == null)
 {
 return;
 }
 else
 {
 Node curr = head;
 int pos = n;
 for (int i = 1; i < pos; i++)
 {
 curr = curr.next;
 }
 if (curr == head)
 {
 head = curr.next;
 }
 else if (curr == null)
 {
curr = curr.previous;
 }
 else
 {
 curr.previous.next = curr.next;
 curr.next.previous = curr.previous;
 }
 curr = null;
 }
 }
 void printList ()
 {
 Node current = head;
 if (head == null)
 {
 System.out.println ("Circular Linked List is empty");
 return;
 }
 while (current != null)
 {
 System.out.print (current.ele + " ");
 current = current.next;
 }
 System.out.println ();
 }
}