Circular Linked List Data Structures

Hey, In this article we are going to learn all about Circular Linked List in detail and their unique structure, which allows for the last node to point back to the first node of the list, creating a continuous loop. Next we will see its types, operations, complexity, implementation, and more.

What is a circular linked list?

A circular linked list is another type of linked list where the last node points to the first node of the list, creating a circular structure. Unlike a normal linked list, a circular linked list does not have a NULL pointer at the end.

As with other linked lists, circular linked lists can also grow or shrink dynamically as elements are added or removed.

Types of Circular Linked Lists

A circular linked list can be created using the singly linked lists and doubly linked lists so there are basically two types of circular linked list:

A singly linked list's last node points to its first node, creating a circular structure. There will be no NULL reference, and it will traverse only in the forward direction.

In a doubly linked list, each node has two pointers (prev and next) and one data field. To create the Circular Doubly Linked List, we will store the first node address in the last node next pointer and the last node address in the first node prev pointer, forming a circle structure. The list will not include any NULL references and will traverse both forwards and backwards directions.

Operations on the Circular Linked List

We can perform the following operations on the Circular Linked List as given below.

Time and Space Complexity of Circular Linked List Operations

Example of Circular Linked List in Java

Now, let's understand the implementation of circular linked list program in Java.

Operations	Time Complexity	Space Complexity
Insertion	O(1) to O(n)	O(1)
Deletion	O(1) to O(n)	O(1)
Traversal	O(n)	O(1)
Search	O(n)	O(1)
Access	O(n)	O(1)

  class Node {
    int data;       // Store value
    Node next;      // Stroe address of next node
  
    // Initializing a node with data in the constructor
    public Node(int data) {
      this.data = data;
      this.next = null;
    }
  }

  class CircularLinkedList {
    private Node head;
    private Node tail;
  
    // Setting null in head and tail in the constructor
    public CircularLinkedList() {
      head = null;
      tail = null;
    }
  
    // Method to insert a new node into the circular linked list
    public void insertNode(int data) {
      Node newNode = new Node(data);
  
      // If the list is empty, make the new node the head and tail
      if (head == null) {
        head = newNode;
        tail = newNode;
  
        // Point to itself in a circular list
        newNode.next = head;
      } else {
        newNode.next = head;
        tail.next = newNode;
        tail = newNode;
      }
    }
  
    // Method to delete an existing node from the circular linked list
    public void deleteNode(int key) {
      // Returns from here if head is null
      if (head == null) {
        return;
      }
  
      Node curr = head;
      Node prev = null;
      boolean isKeyFound = false;
      while (curr.next != head) {
        if (curr.data == key) {
          isKeyFound = true;
          // If the node to be deleted is the head node
          if (prev == null) {
            Node last = head;
            while (last.next != head) {
              last = last.next;
            }
            head = curr.next;
            last.next = head;
          } else {
            prev.next = curr.next;
  
            // Update tail if the last node is deleted
            if (curr == tail) {
              tail = prev;
            }
          }
          System.out.println("Given key " + key + " deleted successfully.");
          return;
        }
        prev = curr;
        curr = curr.next;
      }
  
      // Check if the node to be deleted is the last node
      if (curr == head && curr.data == key) {
        prev.next = head;
  
        // Update tail if the last node is deleted
        tail = prev;
      }
  
      if (!isKeyFound)
        System.out.println("Key not found in the list");
    }
  
    // Method to print the elements of the circular linked list
    public void printList() {
      if (head == null) {
        System.out.println("List is empty");
        return;
      }
  
      System.out.print("Linked List Elements: ");
  
      Node itr = head;
      do {
        System.out.print(itr.data + " ");
        itr = itr.next;
      } while (itr != head);
      System.out.println();
    }
  }

  public class CircularLinkedListOutput {
    public static void main(String[] args) {
      // Create a circular linked list
      CircularLinkedList list = new CircularLinkedList();
  
      // Insert elements into the list
      list.insertNode(20);
      list.insertNode(40);
      list.insertNode(60);
      list.insertNode(80);
  
      // Print the list
      list.printList();
  
      // Delete an element from the list
      list.deleteNode(60);
  
      // Delete a non existing element from the list
      list.deleteNode(10);
  
      // Print the list
      list.printList();
    }
  }

Linked List Elements: 20 40 60 80
Given key 60 deleted successfully.
Key not found in the list
Linked List Elements: 20 40 80