Circular Linked List Data Structures

Hey, In this article we are going to explore all about Circular Linked List and its 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:

1. Circular Singly 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.

2. Circular Doubly Linked List

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.

• Insertion
  • Insert node at the beginning
  • Insert node at the end
  • Insert node at the specific position
• Deletion
  • Delete the first node
  • Delete the last node
  • Delete node from the specific position
• Searching
  • Search a specific node

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.

Class: Node

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

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();
  }
}

Class: CircularLinkedListOutput

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

When to Use a Circular Linked List?

There are the following schenaries where circular linked list can be used.

• When we need cyclic behavior, such as in round-robin scheduling or managing a circular buffer.
• When we want to avoid NULL pointers and simplify certain operations like insertion and deletion at the ends.
• In applications where continuous looping is required, such as in a music playlist or a slideshow.

Advantages of Circular Linked List

• Does not contains NULL reference at the end, such types data structure useful for applications where continuous looping is required (e.g., round-robin scheduling).
• Simple and easy implementation in any programming language.
• We can traver the list continuous as last node of the circular linked list contains the address or reference of the first node.
• No memory wastage as last node points back to the first node of the list.
• A circular linked list can be used to implement a queue efficiently.
• A circular linked list is a dynamic data structure, which means any number of nodes can be added or removed from the list based the requirement that good for the application where size of the list is not fixed.

Disadvantages of Circular Linked List

• Circular linked lists are not ideal for applications where linear traversal or a clear start and end are required.
• Traversing a circular linked list can lead to infinite loops if not handled properly.
• Mighty be a chance of memory leak happen if the pointers are not managed properly in the list.

Use Cases of Circular Linked List

• A circular linked list can be used for round-robin scheduling.
• A circular linked list can be used to implement a playlist that loops back to the first song after the last song ends.
• In games where players take turns in a circular order, a circular linked list can manage the player sequence.
• Used in scenarios like streaming data, where the buffer overwrites old data in a circular manner.

A circular linked list is a powerful data structure for specific use cases that require circular behavior in an application, but it comes with added complexity and potential pitfalls. Use it when the problem demands its unique properties, and avoid it when simpler structures like arrays or standard linked lists suffice.