Circular Linked List Insertion and Deletion in Java

November 1, 2023

Java Program for Ciruclar Linked List Insertion and Deletion

We will look at different ways to do insertion or deletion in a circular linked list in Java at different possible positions.

What is a Circular Linked List

A circular Linked list is a connected series of nodes. Where each node has a data value and a next pointer.

The next reference for each node has the location of the next node.

The first node in the circular linked list is called the head node and the last node (sometimes referred to as the tail node) has the address of the first node.

Thus making whole connected nodes circular in nature.

Head – The first node in Circular Linked List
Next – Has the location for the next node in the circular linked list
Data – Part of the node that stores the actual data value
Node – Combination of Data value and next

Some variations of the Circular linked list may also require storing the tail along with the head. The tail tells us where the circular linked list is ending.

Deletion in Circular Linked List

Split a Circular Linked List in two halves

Count nodes in Circular Linked List

Sorted Insert In Circular Linked List

Insertion in the middle in Circular Linked List

Structure of a Linked Circular List in Java

Below is the structure –

// Node Class
class Node{
    int data;
    Node next;

    Node(int x) // parameterized constructor
    {
        data = x;
        next = null;
    }
}

Insertion in a Circular Linked List in Java

We can do insertion at the following –

At Start
At end
After a node

We will code for all three possibilities –

Method 1

Method 2

Method 1

Run

import java.lang.*;
public class Main {
    public static void main(String[] args) {
        Main Obj = new Main();
        Obj.insertBegin(11);
        Obj.insertBegin(22);
        Obj.insertEnd(33);
        Obj.insertEnd(44);
        Obj.insertAfter(2, 77);
        Obj.print();
        // Output formatting
        System.out.println("\nInsertion at Beginning :");
        Obj.print();
        System.out.println("\nInsertion at End :");
        Obj.print();
        System.out.println("\nInsertion after 2nd position");
        Obj.print();
    }
    public class Node {
        int element;
        Node next;
        public Node(int element) {
            this.element = element;
        }
    }
    public Node head = null;
    public Node tail = null;
    public void insertBegin(int element) {
        Node newEle = new Node(element);
        if (head == null) {
            head = newEle;
            tail = newEle;
            newEle.next = head;
        } else {
            newEle.next = head;
            head = newEle;
            tail.next = head;
        }
    }
    public void insertEnd(int element) {
        Node newEle = new Node(element);
        if (head == null) {
            head = newEle;
            tail = newEle;
            newEle.next = head;
        } else {
            tail.next = newEle;
            newEle.next = head;
            tail = newEle;
        }
    }
    public void insertAfter(int n, int data) {
        int size = calcSize();
        if (n < 1 || n > size) {
            System.out.println("Can't insert\n");
        } else {
            Node newNode = new Node(data);
            Node temp = head;
            while (--n > 0) {
                temp = temp.next;
            }
            newNode.next = temp.next;
            temp.next = newNode;
        }
    }
    public int calcSize() {
        int size = 0;
        Node current = head;
        if (head != null) {
            do {
                size++;
                current = current.next;
            } while (current != head);
        }
        return size;
    }
    public void print() {
        Node current = head;
        if (head != null) {
            do {
                System.out.print(" " + current.element);
                current = current.next;
            } while (current != head);
        }
        System.out.println();
    }
}

Output

Insertion at Beginning : 
 22 11
Insertion at End :
 22 11 33 44
Insertion after 2nd position
 44 22 77 11 33

Method 2

Run

import java.lang.*;
public class Main {
    public static void main(String[] args) {
        Main Obj = new Main();

        Obj.insertBegin(11);
        Obj.insertBegin(22);
        System.out.println("Insertion at Beginning : ");
        Obj.print();

        Obj.insertEnd(33);
        Obj.insertEnd(44);
        System.out.println("Insertion at End :" );
        Obj.print();

        Obj.insertAfterPosition(2,77);
        System.out.println("Insertion after 2nd position");
        Obj.print();
    }
    public class Node{
        int element;
        Node next;
        Node prev;
        public Node(int element) {
            this.element = element;
        }
    }

    public Node head = null;
    public Node tail = null;
    int size=0;

    public void insertBegin(int element){
        Node newEle = new Node(element);
        if(head == null) {
            head = newEle;
            tail = newEle;
            newEle.next = head;
            newEle.prev=head;
        }
        else {
            head.prev = newEle;
            newEle.prev=tail;
            newEle.next = head;
            tail.next = newEle;
            head=newEle;
        }
        size++;
    }

    public void insertEnd(int element){
        Node newEle=new Node(element);
        if(head == null) {
            head = newEle;
            tail = newEle;
            newEle.next = head;
            newEle.prev=head;
        }
        else{
            tail.next=newEle;
            newEle.next=head;
            newEle.prev=tail;
            head.prev=newEle;
            tail=newEle;
        }
    }

    public void insertAfterPosition(int n, int data) {
        int len = getLength();

        // if insertion position is 0 means entering at start
        if (n == 0) {
            insertBegin(data);
            return;
        }
        // means inserting after last item
        if (n == len) {
            insertEnd(data);
            return;
        }

        // else insertion will happen somewhere in the middle


        if (n < 1 || len < n) 
        System.out.println("Invalid position"); 
        else { Node freshNode = new Node(data); // can remove null assignments also (constructor takes care of these) // added just for explanation purpose
        freshNode.next = null; 
        freshNode.prev = null; // nthNode used to traverse the Linked List 
        Node nthNode = head; // traverse till the nth node
        while (--n > 0) {
            nthNode = nthNode.next;
        }

        Node nextNode = nthNode.next; // (n+1)th node

        // assigning (n+1)th node's previous to this new node
        nextNode.prev = freshNode;

        // new_node's next assigned to (n+1)th node
        freshNode.next = nextNode;
        // new_node's previous assigned to nth node
        freshNode.prev = nthNode;

        // assign nth node's next to new_node
        nthNode.next = freshNode;
    }
}

    public int getLength() {
        int size = 0;
        Node temp=head;
        // traverse to the last node each time incrementing the size
        while (temp != tail) {
            temp = temp.next;
            size++;
        }
        return size;
    }

    public void print() {  //print function
        Node current = head;
        if(head == null) {
            System.out.println("List is empty");
        }
        else {
            do{
                System.out.print(" "+ current.element);
                current = current.next;
            }while(current != head);
            System.out.println();
        }
    }
}

Output

Insertion at Beginning : 
 22 11
Insertion at End :
 22 11 33 44
Insertion after 2nd position
 22 11 77 33 44

Deletion in a Circular Linked List in Java

We can do deletion at the following –

At Start
At end
Deleting nth node

We will code for all three possibilities –

Method 1

Method 2

Method 1

Run

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Main Obj = new Main();
        Obj.add(10);
        Obj.add(20);
        Obj.add(30);
        Obj.add(40);
        Obj.add(50);
        Obj.add(60);

        System.out.println("List Before Deletion");
        Obj.print();

        System.out.println("List After Deleting first node");
        Obj.deleteFirst();
        Obj.print();

        System.out.println("List After Deleting last node");
        Obj.deleteLast();
        Obj.print();

        Obj.deleteNthNode(2);
        System.out.println("List After Deleting 2nd node");
        Obj.print();
    }
    public class Node{
        int element;
        Node next;

        public Node(int element) {
            this.element = element;
        }
    }
    public Node head = null;
    public Node tail = null;

    public void print() {
        Node temp = head;
        if(head == null) {
            System.out.println("null");
        }
        else {
            do{
                System.out.print(" "+ temp.element);
                temp = temp.next;
            }while(temp != head);
            System.out.println();
        }
    }

    public void add(int element){
        Node newNode = new Node(element);
        if(head == null) {
            head = newNode;
            tail = newNode;
            newNode.next = head;
        }
        else {
            tail.next = newNode;
            tail = newNode;
            tail.next = head;
        }
    }



    public void deleteFirst() {
        if(head == null) {
            return;
        }
        else {
            if(head != tail ) {
                head = head.next;
                tail.next = head;
            }
            else {
                head = tail = null;
            }
        }
    }


    public void deleteLast() {
        if(head == null) {
            return;
        }
        else {
            if(head != tail ) {
                Node current = head;
                while(current.next != tail) {
                    current = current.next;
                }
                tail = current;
                tail.next = head;
            }
            else {
                head = tail = null;
            }
        }
    }

    public int calcLen(){
        int len = 0;
        Node temp=head;

        while(temp!=tail){
            temp = temp.next;
            len++;
        }
        return len;
    }

    public void deleteNthNode(int n)
    {
        int len = calcLen();

        // Can only insert after 1st position
        // Can't insert if position to insert is greater than size of Linked List
        if(n < 1 || n > len)
        {
            System.out.println("Can't delete\n");

        }
        else
        {
            if(n == 1)
            {
                head = head.next;
                return;
            }
            // required to traverse
            Node temp = head;
            Node previous = null;

            // traverse to the nth node
            while(--n > 0) {
                previous = temp;
                temp = temp.next;
            }
            // assigned next node of the previous node to nth node's next
            previous.next = temp.next;
            System.out.println("Deleted: " + temp.element);
        }
    }
}

Output

List Before Deletion
 10 20 30 40 50 60
List After Deleting first node
 20 30 40 50 60
List After Deleting last node
 20 30 40 50
Deleted: 30
List After Deleting 2nd node
 20 40 50

Method 2

Run

import java.lang.*;
public class Main {
    public static void main(String[] args) {
        Main Obj = new Main();
        Obj.add(10);
        Obj.add(20);
        Obj.add(30);
        Obj.add(40);
        Obj.add(50);
        Obj.add(60);

        System.out.println("List Before Deletion");
        Obj.print();

        System.out.println("List After Deleting first node");
        Obj.deleteFirst();
        Obj.print();

        System.out.println("List After Deleting last node");
        Obj.deleteLast();
        Obj.print();

        Obj.deletenth(2);
        System.out.println("List After Deleting 2nd node");
        Obj.print();

    }
    public class Node{
        int element;
        Node next;
        Node prev;

        public Node(int element) {
            this.element = element;
        }
    }
    public Node head = null;
    public Node tail = null;
    public void print() {
        Node temp = head;
        if(head == null) {
            System.out.println("null");
        }
        else {
            do{
                System.out.print(" "+ temp.element);
                temp = temp.next;
            }while(temp != head);
            System.out.println();
        }
    }

    public void add(int element){
        Node newNode = new Node(element);
        if(head == null) {
            head = newNode;
            tail = newNode;
            newNode.next = head;
            newNode.prev=head;
        }
        else {
            tail.next = newNode;
            newNode.prev=tail;
            tail = newNode;
            tail.next = head;
        }
    }
    public 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;
    }

    public void deleteFirst() {
        if(head == null) {
            return;
        }
        else {
            if(head != tail ) {
                head = head.next;
                tail.next = head;
            }
            else {
                head = tail = null;
            }
        }
    }

    public void deleteLast() {
        if(head == null) {
            return;
        }
        else {
            if(head != tail ) {
                Node current = head;
                while(current.next != tail) {
                    current = current.next;
                }
                tail = current;
                tail.next = head;
                head.prev=tail;
            }
            else {
                head = tail = null;
            }
        }
    }


    public void deletenth (int n)
    {
        if (head == null)
        {
            return;
        }
        else
        {
            Node current = head;
            int pos = n;
            for (int i = 1; i < pos; i++)
            {
                current = current.next;
            }
            if (current == head)
            {
                head = current.next;
            }
            else if (current == null)
            {
                current = current.prev;
            }
            else
            {
                current.prev.next = current.next;
                current.next.prev = current.prev;
            }
            //Delete the middle node
            current = null;
        }
    }


    void printList ()
    {
        //Node current will point to head
        Node curr = head;
        if (head == null)
        {
            System.out.println ("List is empty");
            return;
        }
        while (curr != null)
        {
            //Prints each node by increasing order of the pointer
            System.out.print (curr.element + " ");
            curr = curr.next;
        }
        System.out.println ();
    }

}

Output

List Before Deletion
 10 20 30 40 50 60
List After Deleting first node
 20 30 40 50 60
List After Deleting last node
 20 30 40 50
List After Deleting 2nd node
 20 40 50

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription