Circular Linked List#

A circular linked list is a variation of a linked list where the last node points back to the first node, forming a closed loop. Unlike regular linked lists, it does not contain any Null pointers at the end.

Core Variations

Single Circular Linked List

Each node contains a single data field and one next pointer. The final node’s pointer connects to the starting node.

Doubly Circular Linked List

Each node contains to pointers (previous and next). The tail’s next points to the head, and the head’s previous points to the tail, enabling flawless two-way navigation.

Advantages/Disadvantages#

Advantages
Continuous Loop

Ideal for lists that need to cycle repeatedly without resetting a pointer back to the start.

Fast Insertions

Instantaenous front and back operations (\(O(1)\)) when maintaining a tail pointer.

No Null Pointer Errors

Reduces specific boundary-check bugs.

Disadvantages
Infinite Loop Risk

If the stopping condition (checking if you are back at the starting node) is written incorrectly, code will run forever.

Complex Code

Harder to reverse of split compared to a simple linear list.

Time Complexity of Operations#

By tracking a tail pointer (the last node) instead of a head pointer, you gain \(O(1)\) constant time access to both the front and back of the list.

Insertion at Beginning: \(O(1)\)

Update tail->next to the new node.

Insertion at End: \(O(1)\)

Attach after tail and update the tail pointer.

Deletion from Beginning: \(O(1)\)

Bypass the first node using tail->next = tail->next->next.

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

Requires traversing the entire list to find the second-to-last node (in singly circular).

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

Must track the starting node to avoid an infinite loop.

Implementation#

#include <format>
#include <iostream>

struct Node {
  int data;
  Node *next;

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

class LinkedList {
  private:
    Node *head;

  public:
    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;
          return;
        }
        while (current->next != head) {
          current = current->next;
        }
        current->next = head->next;
        head = head->next;
        return;
      }
      current = head;
      while (current->next != head) {
        previous = current;
        current = current->next;
        if (current->data == data) {
          previous->next = current->next;
          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;
    }
};