Java Data Structures and Algorithms for Beginners

Circular Linked List Data Structure

Definition and Concepts

A circular linked list is a linear data structure where nodes are arranged in a sequence, and the last node points back to the first node, forming a loop. In a singly circular linked list, each node contains data and a reference to the next node, with the last node’s next pointer linking to the head node instead of null. Unlike a standard singly linked list, which has a definite end, a circular linked list allows continuous traversal. You can visualize a circular linked list as a ring of boxes, where each box holds a value and an arrow points to the next box, with the last box pointing back to the first. This structure is ideal for applications requiring cyclic or round-robin processing.

Why Use It?

A circular linked list is used when you need a data structure that supports continuous looping through elements, such as in round-robin scheduling or cyclic data processing. It eliminates the need to reset traversal to the beginning after reaching the end, making it efficient for repetitive tasks. The circular nature simplifies certain operations, like rotating the list, and it can be used as a foundation for structures like circular buffers.

Where to Use? (Real-Life Examples)

• Round-Robin Scheduling: Operating systems use circular linked lists to manage processes in a round-robin fashion, cycling through tasks to allocate CPU time.
• Music Playlist Looping: Music players use circular linked lists to implement a looping playlist, where playback restarts from the first song after the last one.
• Circular Buffers: Network applications use circular linked lists to implement buffers for streaming data, reusing space in a fixed-size structure.
• Multiplayer Game Turns: Board games or turn-based applications use circular linked lists to cycle through players’ turns indefinitely.

Explain Operations

• Insert at Head: This operation adds a new node at the beginning of the list, updating the last node’s pointer to the new head. It has a time complexity of O(1) if a tail pointer is maintained.
• Insert at Tail: This operation adds a new node at the end of the list, updating the last node’s pointer to the new node and linking it to the head. It has a time complexity of O(1) if a tail pointer is maintained.
• Delete at Head: This operation removes the first node, updating the last node’s pointer to the new head. It has a time complexity of O(1) if a tail pointer is maintained.
• Delete by Value: This operation removes the first node with a given value. It has a time complexity of O(n) due to traversal.
• Search: This operation finds a node with a given value. It has a time complexity of O(n).
• isEmpty: This operation checks whether the circular linked list is empty. It has a time complexity of O(1).
• Size: This operation returns the number of nodes in the circular linked list. It has a time complexity of O(1) if maintained.

Java Implementation

The following Java code implements a singly circular linked list with basic operations, maintaining a tail pointer for efficiency.

public class CircularLinkedList {
    private class Node {
        int value; // Value stored in the node
        Node next; // Reference to the next node

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

    private Node tail; // Tail of the circular linked list
    private int size; // Number of nodes in the circular linked list

    // Constructor to initialize an empty circular linked list
    public CircularLinkedList() {
        tail = null;
        size = 0;
    }

    // Insert at Head: Adds a new node at the beginning
    public void insertAtHead(int value) {
        Node newNode = new Node(value); // Creates a new node
        if (isEmpty()) { // If list is empty, sets tail to new node and links to itself
            tail = newNode;
            newNode.next = newNode;
        } else {
            newNode.next = tail.next; // Points new node to current head
            tail.next = newNode; // Points tail to new node (new head)
        }
        size++; // Increments size
    }

    // Insert at Tail: Adds a new node at the end
    public void insertAtTail(int value) {
        Node newNode = new Node(value); // Creates a new node
        if (isEmpty()) { // If list is empty, sets tail to new node and links to itself
            tail = newNode;
            newNode.next = newNode;
        } else {
            newNode.next = tail.next; // Points new node to current head
            tail.next = newNode; // Points current tail to new node
            tail = newNode; // Updates tail to new node
        }
        size++; // Increments size
    }

    // Delete at Head: Removes the first node
    public void deleteAtHead() {
        if (isEmpty()) { // Checks if the list is empty
            throw new IllegalStateException("The circular linked list is empty.");
        }
        if (size == 1) { // If only one node, clears the list
            tail = null;
        } else {
            tail.next = tail.next.next; // Points tail to the second node (new head)
        }
        size--; // Decrements size
    }

    // Delete by Value: Removes the first node with the given value
    public void deleteByValue(int value) {
        if (isEmpty()) { // Checks if the list is empty
            throw new IllegalStateException("The circular linked list is empty.");
        }
        Node current = tail.next; // Starts at head
        Node prev = tail; // Previous node for deletion
        do {
            if (current.value == value) { // If value is found
                if (size == 1) { // If only one node, clears the list
                    tail = null;
                } else if (current == tail.next) { // If head node
                    tail.next = current.next;
                } else if (current == tail) { // If tail node
                    prev.next = tail.next;
                    tail = prev;
                } else { // If middle node
                    prev.next = current.next;
                }
                size--; // Decrements size
                return;
            }
            prev = current;
            current = current.next;
        } while (current != tail.next); // Loops until back to head
        throw new IllegalArgumentException("Value not found in the circular linked list.");
    }

    // Search: Checks if a value exists in the circular linked list
    public boolean search(int value) {
        if (isEmpty()) { // Checks if the list is empty
            return false;
        }
        Node current = tail.next; // Starts at head
        do {
            if (current.value == value) { // Returns true if value is found
                return true;
            }
            current = current.next;
        } while (current != tail.next); // Loops until back to head
        return false; // Returns false if value is not found
    }

    // isEmpty: Checks if the circular linked list is empty
    public boolean isEmpty() {
        return size == 0;
    }

    // Size: Returns the number of nodes in the circular linked list
    public int size() {
        return size;
    }
}

How It Works

1. Initialization: The constructor initializes tail as null and size as 0, indicating an empty circular linked list.
2. Insert at Head:
   • The method creates a new node with the given value.
   • If the list is empty, it sets tail to the new node and links it to itself.
   • Otherwise, it sets the new node’s next to the current head (tail.next), updates tail.next to the new node, and increments size.
3. Insert at Tail:
   • The method creates a new node.
   • If the list is empty, it sets tail to the new node and links it to itself.
   • Otherwise, it sets the new node’s next to the current head, updates tail.next to the new node, sets tail to the new node, and increments size.
4. Delete at Head:
   • The method checks if the list is empty. If not, it updates tail.next to the second node (new head) if multiple nodes exist, or sets tail to null if only one node, then decrements size. If empty, it throws an exception.
5. Delete by Value:
   • The method traverses from the head (tail.next) to find the value, keeping track of the previous node.
   • If found, it handles three cases: single node (clears the list), head node (updates tail.next), tail node (updates tail and prev.next), or middle node (updates prev.next). It decrements size.
   • If the value is not found after a full loop, it throws an exception.
6. Search Operation: The method traverses from the head, returning true if the value is found, or false after a full loop to the head.
7. isEmpty Operation: The method returns true if size equals 0, indicating an empty list, and false otherwise.
8. Size Operation: The method returns size, which tracks the number of nodes.

Complexity Analysis Table

Note: n is the number of nodes in the circular linked list. O(1) operations assume a tail pointer is maintained.

Key Differences / Notes

• Circular vs. Singly Linked List:
  • The implementation above is a singly circular linked list, where the last node points to the head, enabling continuous traversal. A singly linked list ends with a null pointer, requiring traversal to restart from the head.
  • Circular linked lists are more complex to manage due to the loop, but they simplify cyclic operations.
• Circular vs. Doubly Circular Linked List:
  • A doubly circular linked list includes previous pointers, allowing bidirectional traversal, but uses more memory.
  • The singly circular linked list is simpler and more memory-efficient but only supports forward traversal.
• Thread Safety: The implementation is not thread-safe. For concurrent applications, use Java’s ConcurrentLinkedDeque or synchronize access.
• Java’s Built-in Support: Java’s LinkedList can be adapted for circular behavior, but no direct circular linked list class is provided. Libraries like Apache Commons Collections offer circular list implementations.

✅ Tip: Use a circular linked list when your application requires continuous cycling through elements, such as in scheduling or looping playlists. Maintaining a tail pointer simplifies head and tail operations to O(1).

⚠ Warning: Be cautious when traversing a circular linked list to avoid infinite loops. Always use a condition (e.g., checking for the head node) to terminate traversal.

Exercises

1. Rotate the List: Write a Java program that rotates the circular linked list by k positions (e.g., move the head k nodes forward). Test with different values of k and list sizes.
2. Split Circular List: Implement a method to split a circular linked list into two circular linked lists of roughly equal size. Test with even and odd-sized lists.
3. Josephus Problem: Solve the Josephus problem using the circular linked list, where every k-th person in a circle is eliminated until one remains. Test with different k values.
4. Insert After Value: Add a method to insert a new node after the first occurrence of a given value in the circular linked list. Test with cases where the value exists and does not exist.
5. Round-Robin Scheduler: Create a program that simulates a round-robin scheduler using the circular linked list. Allow users to add tasks (nodes), cycle through them, and remove completed tasks.