Circular Singly Linked List

A circular singly linked list is a linear data structure where the last node points back to the first node (head) instead of pointing to Null. Each node contains a single data field and a single next pointer, forming a continuous, closed loop.

Key Characteristics

No Null Pointers

Traversal does not terminate automatically; it cycles indefinitely unless explicitly stopped.

Tail Optimization

Keeping a pointer to the tail (last node) instead of the head allows \(O(1)\) constant time access to both the first node (tail->next) nad the last node (tail).

Memory Efficiency

It consumes less memory per node than a circular doubly linked list because it only stores one address pointer instead of two.

Advantages and Disadvantages

Advantages

Infinite Looping

Smooth continuous interation without hitting a null-pointer error.

Any-Node Traversal

You can start traversing from any arbitrary node and still access every element in the list.

Fast Edge Operations

\(O(1)\) insertions/deletions at both ends when using a tail pointer.

Disadvantages

Infinite Loop Risk

Code errors can easily cause infinite traversal loops if the termination logic is incorrectly handled.

Complex Management

Harder to reverse or implement safely compared to standard Singly Linked Lists.

No Backward Traversal

Unidirectional layout requires a full look traversal just to see the previous node.

Time Complexities of Operations

Insertion at Beginning: \(O(n)\); \(O(1)\) with Tail pointer

Point new node to head, update tail’s next to new node.

Insertion at End: \(O(n)\); \(O(1)\) with Tail pointer

Point tail’s next to new node, update tail pointer.

Deletion at Beginning: \(O(n)\); \(O(1)\) with Tail pointer

Update tail’s next to point to the second node.

Deletion at End: \(O(n)\)

Requires traversing to the second-to-last node.

Traversal/Search: \(O(n)\)

Loop sequentially until returning to the starting node.

Visualization

Source: Scaler Topics

Implementation

C++Python

#include <format>
#include <iostream>

struct Node {
  int data;
  Node *next;

  Node(int data) : data(data), next(nullptr) {}
};

class LinkedList {
  private:
    Node *head;

  public:
    LinkedList() : head(nullptr) {}

    void append(int data) {
      Node *node = new Node(data);
      if (head == nullptr) {
        head = node;
        node->next = head;
        return;
      }
      Node *current = head;
      while (current->next != head) {
        current = current->next;
      }
      current->next = node;
      node->next = head;
    }

    void deleteNode(int data) {
      if (head == nullptr) return;
      Node *current = head;
      Node *previous = nullptr;
      if (current->data == data) {
        if (current->next == head) {
          head = nullptr;
          delete current;
          return;
        }
        while (current->next != head) {
          current = current->next;
        }
        Node *node = current->next;
        current->next = head->next;
        head = head->next;
        delete node;
        return;
      }
      current = head;
      while (current->next != head) {
        previous = current;
        current = current->next;
        if (current->data == data) {
          previous->next = current->next;
          delete current;
          return;
        }
      }
    }

    void display() {
      if (head == nullptr) return;
      Node *current = head;
      while (true) {
        std::cout << current->data << " -> ";
        current = current->next;
        if (current == head) break;
      }
      std::cout << std::format("(Back to Head: {})", head->data) << std::endl;
    }

    void prepend(int data) {
      Node *node = new Node(data);
      if (head == nullptr) {
        head = node;
        node->next = head;
        return;
      }
      Node *current = head;
      while (current->next != head) {
        current = current->next;
      }
      node->next = head;
      current->next = node;
      head = node;
    }
};