top of page

DSA Java - Circular Linked List

Circular Linked List is a variation of Linked list in which first element points to last element and last element points to first element. Both Singly Linked List and Doubly Linked List can be made into as circular linked list


Singly Linked List as Circular



Doubly Linked List as Circular



as per above shown illustrations, following are the important points to be considered.

  • Last Link'next points to first link of the list in both cases of singly as well as doubly linked list.

  • First Link's prev points to the last of the list in case of doubly linked list.


public class Node {
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class CircularLinkedList {
    private Node head;

    public CircularLinkedList() {
        this.head = null;
    }

    public boolean isEmpty() {
        return head == null;
    }

    public void insert(int data) {
        Node newNode = new Node(data);

        if (isEmpty()) {
            newNode.next = newNode;  // The new node points to itself
            head = newNode;  // Update the head
        } else {
            newNode.next = head.next;  // Make the new node point to the second node
            head.next = newNode;  // Make the head node point to the new node
            head = newNode;  // Update the head to the new node
        }
    }

    public void delete(int data) {
        if (isEmpty()) {
            System.out.println("The list is empty.");
            return;
        }

        Node current = head;

        // If the head node itself contains the data to be deleted
        if (current.data == data) {
            while (current.next != head) {
                current = current.next;
            }

            current.next = head.next;
            head = head.next;
            return;
        }

        // Search for the node to be deleted
        Node prev = current;
        current = current.next;

        while (current != head) {
            if (current.data == data) {
                prev.next = current.next;
                return;
            }

            prev = current;
            current = current.next;
        }

        System.out.println("The specified data was not found.");
    }

    public void display() {
        if (isEmpty()) {
            System.out.println("The list is empty.");
            return;
        }

        Node current = head;

        do {
            System.out.print(current.data + " ");
            current = current.next;
        } while (current != head);

        System.out.println();
    }

    public static void main(String[] args) {
        CircularLinkedList list = new CircularLinkedList();

        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);

        list.display();  // Output: 4 3 2 1

        list.delete(3);

        list.display();  // Output: 4 2 1
    }
}

In this example, the CircularLinkedList class represents the circular linked list. It has a Node class as an inner class to represent each node in the list. The Node class has a data field and a next field to point to the next node.

The circular linked list is initialized with a head node, which is initially set to null. The isEmpty() method checks if the list is empty. The insert() method inserts a new node at the beginning of the list. The delete() method deletes a node containing the specified data from the list. The display() method displays the elements of the list.

In the main() method, we create a circular linked list object, insert some elements, display the list, and then delete an element before displaying the updated list.

Related Posts

See All

DSA Java - Stack

In computer science, a stack is an abstract data type that represents a collection of elements with a last-in, first-out (LIFO) order of access. This means that the most recently added element is the

Java Algorithms

Java is a popular programming language that provides a wide range of tools and libraries for implementing various algorithms. Here are some commonly used algorithms in Java: Sorting Algorithms: Bubble

Java - Data Structures

When it comes to Data Structures and Algorithms (DSA) in Java, there are several commonly used data structures that can be implemented. Here are some of the main data structures and their correspondin

Comentários


bottom of page