DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Time & Space Complexity Common Mistakes Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Circular Linked List

What Is a Circular Linked List?

A circular linked list is a linked list where the last node's next pointer points back to the head instead of null. The list forms a continuous loop — there is no natural end. Every node is reachable from every other node by following next pointers.

Singly Linked List (linear):
  head → 10 → 20 → 30 → null

Circular Linked List (loop):
  head → 10 → 20 → 30 → (back to 10)
           ↑___________________________|

  No null terminator.
  The tail's next points back to head.

Circular linked lists appear in round-robin CPU scheduling, circular buffers, media players with repeat mode, and anywhere a cyclic sequence is needed.

How Circular Differs from Linear

Property            Singly Linked         Circular Linked
────────────────────────────────────────────────────────
Tail's next         null                  head (or any node)
Traversal stop      temp == null          temp == head (after first step)
Empty list check    head == null          head == null
Endless loop risk   None                  High — loop condition critical
Insert at beginning Must update only head Must update tail's next too
Delete last node    Set prev.next = null  Set prev.next = head
Real-world use      General sequences     Cyclic scheduling, buffers

The most important difference: there is no null to stop at during traversal. You must track when you return to the starting node.

Node and LinkedList Structure

The node structure is identical to a singly linked list — only one next pointer. The circular property is enforced by how nodes are linked, not by the node structure itself.

Java

class Node {
    int  data;
    Node next;   // Points to next node; tail's next points to head

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

class CircularLinkedList {
    Node head;

    CircularLinkedList() {
        head = null;   // Empty list
    }
}

Operation 1: Traverse — Visit Every Node

Traversal must stop when it returns to head, not when it hits null. The loop starts by moving past head and ends when it reaches head again.

Java

public void traverse() {
    if (head == null) {
        System.out.println("List is empty.");
        return;
    }

    Node temp = head;
    do {
        System.out.print(temp.data + " → ");
        temp = temp.next;
    } while (temp != head);   // Stop when we return to head

    System.out.println("(back to " + head.data + ")");
}

Dry Run: Traverse [10 → 20 → 30 → (back to 10)]

head = Node(10)
tail = Node(30),  Node(30).next = Node(10)

Use do-while so head is visited BEFORE the condition is checked:

  temp=Node(10): print 10, temp=Node(20)  → temp ≠ head(10)? YES → continue
  temp=Node(20): print 20, temp=Node(30)  → temp ≠ head(10)? YES → continue
  temp=Node(30): print 30, temp=Node(10)  → temp ≠ head(10)? NO  → STOP

Output: 10 → 20 → 30 → (back to 10)

Why do-while and not while?
  A while loop checks the condition BEFORE the body.
  If we use while (temp != head), the condition is false immediately
  (temp starts at head) and the loop never runs.
  do-while executes the body FIRST, then checks — guaranteeing
  head is printed before the stop condition is evaluated.

Operation 2: Length — Count All Nodes

Java

public int length() {
    if (head == null) return 0;

    int  count = 1;
    Node temp  = head.next;

    while (temp != head) {   // Count until we return to head
        count++;
        temp = temp.next;
    }

    return count;
}

Output (list: 10 → 20 → 30):
3

Operation 3: Search — Find an Element

Java

public boolean search(int key) {
    if (head == null) return false;

    Node temp = head;
    do {
        if (temp.data == key) return true;
        temp = temp.next;
    } while (temp != head);

    return false;
}

search(20) → true
search(99) → false

Operation 4: Insert at Beginning — O(n)

Insert a new node as the new head. The old head is still reachable via the new node's next. The critical step: find the tail (the node whose next currently points to the old head) and update it to point to the new head.

Before: head → 20 → 30 → (back to 20)
Insert 10 at beginning:

Step 1: Create newNode(10)
Step 2: newNode.next = head (new node points to old head, Node 20)
Step 3: Find tail — Node 30 (whose next was head Node 20)
Step 4: tail.next = newNode (tail now points to new head, Node 10)
Step 5: head = newNode

After: head → 10 → 20 → 30 → (back to 10)

Java

public void insertAtBeg(int data) {
    Node newNode = new Node(data);

    if (head == null) {
        // First node — points to itself
        head          = newNode;
        newNode.next  = head;
        return;
    }

    // Find the tail — the node whose next is head
    Node tail = head;
    while (tail.next != head) {
        tail = tail.next;
    }

    newNode.next = head;    // New node points to old head
    tail.next    = newNode; // Tail points to new node
    head         = newNode; // New node becomes head
}

Dry Run: insertAtBeg(10) into [20 → 30 → (back to 20)]

newNode = Node(10)
head    = Node(20)

Find tail (node whose next == head):
  tail=Node(20): tail.next=Node(30) ≠ head → tail=Node(30)
  tail=Node(30): tail.next=Node(20) = head → STOP
  tail = Node(30)

Update pointers:
  newNode.next = head   → Node(10).next = Node(20)
  tail.next    = newNode → Node(30).next = Node(10)
  head         = newNode → head = Node(10)

Result: head → 10 → 20 → 30 → (back to 10) ✓

Why O(n)? We must traverse to find the tail.
Optimization: maintain a tail pointer → O(1) insert at beginning.

Operation 5: Insert at End — O(n)

Find the current tail, attach the new node after it, and make the new node's next point to head.

Java

public void insertAtEnd(int data) {
    Node newNode = new Node(data);

    if (head == null) {
        head         = newNode;
        newNode.next = head;    // Single node points to itself
        return;
    }

    // Find the tail
    Node tail = head;
    while (tail.next != head) {
        tail = tail.next;
    }

    tail.next    = newNode; // Old tail points to new node
    newNode.next = head;    // New node points back to head
}

Dry Run: insertAtEnd(40) into [10 → 20 → 30 → (back to 10)]

newNode = Node(40)

Find tail:
  tail=Node(10): next=Node(20) ≠ head → tail=Node(20)
  tail=Node(20): next=Node(30) ≠ head → tail=Node(30)
  tail=Node(30): next=Node(10) = head → STOP

Attach:
  tail.next    = newNode → Node(30).next = Node(40)
  newNode.next = head    → Node(40).next = Node(10)

Result: head → 10 → 20 → 30 → 40 → (back to 10) ✓

Operation 6: Insert at Middle — After a Given Value

Find the node with value aft, insert the new node after it. The new node inherits the successor's circular link.

Java

public void insertAtMid(int aft, int data) {
    if (head == null) {
        System.out.println("List is empty.");
        return;
    }

    Node newNode = new Node(data);
    Node temp    = head;

    // Find the node with value `aft`
    do {
        if (temp.data == aft) {
            // Insert after temp
            newNode.next = temp.next; // new node points to temp's successor
            temp.next    = newNode;   // temp now points to new node
            return;
        }
        temp = temp.next;
    } while (temp != head);

    System.out.println("Value " + aft + " not found.");
}

Dry Run: Insert 25 After 20 in [10 → 20 → 30 → (back to 10)]

Find node with data=20:
  temp=Node(10): 10 ≠ 20 → temp=Node(20)
  temp=Node(20): 20 = 20 → FOUND

Insert after Node(20):
  newNode.next = temp.next   → Node(25).next = Node(30)
  temp.next    = newNode     → Node(20).next = Node(25)

Result: head → 10 → 20 → 25 → 30 → (back to 10) ✓

The circular link (30 → back to 10) is automatically preserved
because newNode.next = temp.next carries it forward.

Operation 7: Delete from Beginning — O(n)

Make head point to head.next. Then find the tail and update its next to the new head.

Java

public void deleteAtBeg() {
    if (head == null) {
        System.out.println("List is empty.");
        return;
    }

    // Only one node
    if (head.next == head) {
        head = null;
        return;
    }

    // Find the tail (its next is currently head)
    Node tail = head;
    while (tail.next != head) {
        tail = tail.next;
    }

    head      = head.next; // Move head forward
    tail.next = head;      // Tail now points to new head
}

Dry Run: deleteAtBeg from [10 → 20 → 30 → (back to 10)]

head = Node(10)

Not a single-node list (head.next ≠ head).

Find tail:
  tail=Node(10): next=Node(20) ≠ head → tail=Node(20)
  tail=Node(20): next=Node(30) ≠ head → tail=Node(30)
  tail=Node(30): next=Node(10) = head → STOP

Update:
  head      = head.next → head = Node(20)
  tail.next = head      → Node(30).next = Node(20)

Result: head → 20 → 30 → (back to 20) ✓

Node(10) is now unreferenced — garbage collected in Java/Python/JS,
must be explicitly deleted in C++.

Operation 8: Delete from End — O(n)

Traverse to the second-to-last node (the one whose next.next equals head). Set its next to head.

Java

public void deleteAtEnd() {
    if (head == null) {
        System.out.println("List is empty.");
        return;
    }

    // Only one node
    if (head.next == head) {
        head = null;
        return;
    }

    Node temp = head;

    // Walk to the second-to-last node (temp.next.next == head)
    while (temp.next.next != head) {
        temp = temp.next;
    }

    temp.next = head; // Second-to-last now points directly to head
}

Dry Run: deleteAtEnd from [10 → 20 → 30 → (back to 10)]

head = Node(10)

Walk to second-to-last (where temp.next.next == head):
  temp=Node(10): temp.next=Node(20), temp.next.next=Node(30) ≠ head → temp=Node(20)
  temp=Node(20): temp.next=Node(30), temp.next.next=Node(10) = head → STOP

Detach: temp.next = head
  Node(20).next = Node(10)   (was Node(30), now jumps to head)

Result: head → 10 → 20 → (back to 10) ✓  (Node(30) removed)

Why temp.next.next != head (not temp.next != head)?
  temp.next != head would stop at the second-to-last's predecessor,
  one step too early. We need temp to be the second-to-last node
  so we can reassign temp.next to head.

Operation 9: Delete from Middle — Remove by Value

Use two pointers — temp (current) and prev (one step behind). When temp.data == key, bypass it using prev.next = temp.next.

Java

public void deleteAtMid(int key) {
    if (head == null) {
        System.out.println("List is empty.");
        return;
    }

    // Special case: deleting the head
    if (head.data == key) {
        deleteAtBeg();
        return;
    }

    Node prev = head;
    Node temp = head.next;

    do {
        if (temp.data == key) {
            prev.next = temp.next;  // Bypass temp
            return;
        }
        prev = temp;
        temp = temp.next;
    } while (temp != head);

    System.out.println("Value " + key + " not found.");
}

Dry Run: Delete 20 from [10 → 20 → 30 → (back to 10)]

key = 20, head.data = 10 ≠ 20 → not a head deletion

prev = Node(10)
temp = Node(20)

Iteration 1:
  temp.data = 20 = key → FOUND
  prev.next = temp.next → Node(10).next = Node(30)
  return ✓

Result: head → 10 → 30 → (back to 10)

The circular link is preserved:
  Node(30).next was already pointing to Node(10) (the head).
  Bypassing Node(20) connects Node(10) directly to Node(30),
  keeping the circle intact.

Complete Working Example

Java

public class Main {
    public static void main(String[] args) {
        CircularLinkedList cll = new CircularLinkedList();

        // Build list
        cll.insertAtEnd(10);
        cll.insertAtEnd(20);
        cll.insertAtEnd(30);
        cll.insertAtEnd(40);

        System.out.println("After insertAtEnd (10,20,30,40):");
        cll.traverse();                        // 10 → 20 → 30 → 40 → (back to 10)
        System.out.println("Length: " + cll.length()); // 4

        cll.insertAtBeg(5);
        System.out.println("After insertAtBeg(5):");
        cll.traverse();                        // 5 → 10 → 20 → 30 → 40 → (back to 5)

        cll.insertAtMid(20, 25);
        System.out.println("After insertAtMid(after 20, 25):");
        cll.traverse();                        // 5 → 10 → 20 → 25 → 30 → 40 → (back to 5)

        cll.deleteAtBeg();
        System.out.println("After deleteAtBeg:");
        cll.traverse();                        // 10 → 20 → 25 → 30 → 40 → (back to 10)

        cll.deleteAtMid(25);
        System.out.println("After deleteAtMid(25):");
        cll.traverse();                        // 10 → 20 → 30 → 40 → (back to 10)

        cll.deleteAtEnd();
        System.out.println("After deleteAtEnd:");
        cll.traverse();                        // 10 → 20 → 30 → (back to 10)

        System.out.println("Search 20: " + cll.search(20)); // true
        System.out.println("Search 99: " + cll.search(99)); // false
        System.out.println("Final length: " + cll.length()); // 3
    }
}

Output:
After insertAtEnd (10,20,30,40):
10 → 20 → 30 → 40 → (back to 10)
Length: 4
After insertAtBeg(5):
5 → 10 → 20 → 30 → 40 → (back to 5)
After insertAtMid(after 20, 25):
5 → 10 → 20 → 25 → 30 → 40 → (back to 5)
After deleteAtBeg:
10 → 20 → 25 → 30 → 40 → (back to 10)
After deleteAtMid(25):
10 → 20 → 30 → 40 → (back to 10)
After deleteAtEnd:
10 → 20 → 30 → (back to 10)
Search 20: true
Search 99: false
Final length: 3

Time & Space Complexity

Operation	Time	Space	Notes
Traverse	O(n)	O(1)	Visit every node once
Length	O(n)	O(1)	Count during traversal
Search	O(n)	O(1)	Best O(1) if key is head
Insert at beginning	O(n)	O(1)	Must find tail to update its next
Insert at end	O(n)	O(1)	Must find tail
Insert at middle	O(n)	O(1)	Traverse to target position
Delete from beginning	O(n)	O(1)	Must find tail to redirect its next
Delete from end	O(n)	O(1)	Traverse to second-to-last node
Delete from middle	O(n)	O(1)	Two-pointer traversal

Optimization with tail pointer: If you maintain a tail reference alongside head, insert at beginning and end become O(1) — no traversal needed to find the tail. Most production circular list implementations keep both head and tail.

Common Mistakes Beginners Make

Using while (temp != null) instead of while (temp != head) in traversal. There is no null in a circular list — temp never becomes null. Using null as the stop condition creates an infinite loop. Always stop when you return to head.

Using while instead of do-while for traversal. A while (temp != head) loop starting at head immediately evaluates to false and does nothing. Use do-while or start temp at head.next so head is visited before the condition is checked.

Forgetting to update tail's next when inserting at the beginning. In a linear list, inserting at the beginning only changes head. In a circular list, the old tail's next still points to the old head — you must update it to point to the new head, or the circle is broken.

Not handling the single-node case in delete operations. If the list has only one node, head.next == head. Setting head = head.next would set head = head — no change. Always check for head.next == head and set head = null to empty the list.

Using temp.next != head instead of temp.next.next != head in deleteAtEnd. The condition temp.next != head stops when temp is the second-to-last node — but that is one step too early. You need temp itself to be the second-to-last, so the condition should be temp.next.next != head.

Interview Questions

Q: What is the key difference in traversal between a circular and a singly linked list?

A singly linked list traversal stops when temp == null. A circular list has no null — the tail points back to head. The stop condition must be temp == head (after starting), typically implemented with a do-while loop to ensure head is visited before the condition is checked. Forgetting this causes an infinite loop.

Q: Why does insert at beginning require O(n) in a circular linked list but O(1) in a singly linked list?

In a singly linked list, inserting at the beginning only updates head and newNode.next. In a circular linked list, the tail must also be updated — its next must point to the new head instead of the old one. Without a maintained tail pointer, finding the tail requires traversing the entire list — O(n). With a tail pointer, this drops to O(1).

Q: How do you detect whether a linked list is circular?

Three approaches: (1) HashSet — store visited nodes, return true if any node is seen twice. O(n) time, O(n) space. (2) Floyd's cycle detection — slow pointer moves one step, fast pointer moves two. If they meet, the list is circular. O(n) time, O(1) space. (3) Tail check — traverse to the last node; if tail.next == head, it is circular. O(n) time, O(1) space, but only works if you know what head is.

FAQs

What is the difference between a circular singly and circular doubly linked list?

A circular singly linked list has one pointer per node (next), with tail.next = head. Traversal is forward only. A circular doubly linked list has two pointers (prev and next), with tail.next = head AND head.prev = tail. It supports bidirectional traversal in a closed loop. The doubly variant is used in the classic LRU cache implementation.

Can a circular linked list ever be empty?

Yes — when head == null. An empty circular linked list has no nodes at all. The first node inserted points to itself (node.next = node), making it both head and tail. This single-node state (head.next == head) must be handled as a special case in delete operations.

Where are circular linked lists used in practice?

Round-robin CPU scheduling — the scheduler cycles through processes using the circular structure. Music/video players on repeat — the playlist is a circular list, so reaching the end returns to the beginning. Token ring networks — frames circulate around a ring of nodes. Circular buffers — fixed-size buffers where the write pointer wraps around to the start. Multiplayer board games — players are stored in a circular list so turns cycle through them indefinitely.

Quick Quiz

Question 1: What traversal loop correctly visits every node in a circular linked list starting at head?

›A) while (temp != null) — same as singly linked list
›B) while (temp.next != head) — misses the last node before returning to head
›C) do { visit(temp); temp = temp.next; } while (temp != head)
›D) for (int i = 0; i < n; i++)

Answer: C) do-while stopping at head. A while (temp != head) starting at head would never execute — the condition is false immediately. do-while visits head first, then checks. Option B visits one too few nodes (misses the node just before head). Option D requires knowing n in advance.

Question 2: In deleteAtEnd, the loop condition temp.next.next != head is used instead of temp.next != head. Why?

›A) Both conditions produce the same result
›B) temp.next != head would stop one node too late
›C) temp.next.next != head positions temp at the second-to-last node, so temp.next = head correctly detaches the last node
›D) The extra .next handles the circular reference

Answer: C. We need temp to end up as the second-to-last node, so that setting temp.next = head removes the last node. The condition temp.next != head would stop when temp is the third-to-last node — one step too early.

Question 3: You insert a node as the only node into an empty circular linked list. What should newNode.next be set to?

›A) null — no next node yet
›B) head — which is the same as newNode itself
›C) A new empty node
›D) It does not matter for a single node

Answer: B) head / itself. A circular linked list has no null terminator. Even a single node must point to something — it points to itself: newNode.next = newNode. After setting head = newNode, this is equivalent to newNode.next = head. The self-loop maintains the circular invariant.

Question 4: What must be updated in a circular linked list when inserting a new node at the beginning, that is NOT needed in a singly linked list?

›A) The new node's next pointer
›B) The head reference
›C) The tail's next pointer — must point to the new head
›D) The new node's prev pointer

Answer: C) The tail's next pointer. In a singly linked list, inserting at the beginning updates newNode.next = head and head = newNode — two changes. In a circular list, the tail's next still points to the old head. It must be redirected to newNode so the circle remains complete. This is why the operation requires O(n) to find the tail (unless a tail pointer is maintained).

Summary

A circular linked list forms a closed loop — the tail's next points back to head. There is no null terminator. Every node is reachable from every other node.

The nine core operations and their critical differences from singly linked:

›Traverse — O(n) — use do-while (temp != head), NOT while (temp != null)
›Length — O(n) — start count at 1, begin loop at head.next
›Search — O(n) — do-while loop to handle the circular stop condition
›Insert at beginning — O(n) — must find and update tail's next to new head
›Insert at end — O(n) — find tail, attach new node, set newNode.next = head
›Insert at middle — O(n) — same two-pointer update as singly linked
›Delete from beginning — O(n) — find tail, move head, set tail.next = new head
›Delete from end — O(n) — stop at second-to-last using temp.next.next != head
›Delete from middle — O(n) — two-pointer bypass; handle head deletion as special case

Always handle two special cases: empty list (head == null) and single-node list (head.next == head). Maintain a tail pointer for O(1) insert/delete at both ends.

In the next topic, you will explore Traversal and Searching — all traversal patterns, search algorithms, and the techniques used in interview problems across singly, doubly, and circular linked lists.

←

PreviousDoubly Linked List

NextLinked List Collection frameworks

→