Linked List — Singly, Doubly & Circular Linked Lists

Module 6 — Linked List: Singly, Doubly & Circular Linked Lists Structured as Topic → Plain-English Explanation → Real Code → Visual Diagram → Complexity → Common Pitfalls.

1. Singly Linked List

A linked list is a chain of nodes, where each node stores a value plus a pointer to the next node. Unlike an array, the nodes don't need to sit next to each other in memory — they can be scattered anywhere, connected only by these pointers. This means insertion and deletion at the front are $O(1)$ — no shifting required — but reaching the $k$-th element requires walking the chain one node at a time from the head, making random access $O(n)$.

struct Node {
    int data;
    Node* next;
};
Node* head = new Node{10, nullptr};
head->next = new Node{20, nullptr};

• Complexity: Insert/delete at head — $O(1)$. Access by index / search — $O(n)$.

2. Doubly Linked List

A doubly linked list gives every node two pointers — one to the next node and one to the previous node. This extra pointer costs a little more memory per node, but it lets you traverse the list backward as easily as forward, and lets you delete a node in $O(1)$ once you have a pointer to it, since you no longer need to walk from the head to find its predecessor.

struct Node {
    int data;
    Node* next;
    Node* prev;
};

3. Circular Linked List

A circular linked list is simply a singly (or doubly) linked list where the last node's next pointer points back to the first node instead of to NULL, forming a loop. There is no true "end," which makes it well suited for scenarios that naturally cycle, such as round-robin CPU scheduling or a circular playlist that loops back to the first song after the last.

4. Reversal & Cycle Detection

Iterative In-Place Reversal ($O(n)$ Time, $O(1)$ Space)

ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *curr = head;
    while (curr != nullptr) {
        ListNode *nextNode = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextNode;
    }
    return prev;
}

Floyd's Cycle Detection (Tortoise and Hare)

Using two pointers (slow moving 1 step, fast moving 2 steps) detects loops in $O(n)$ time and $O(1)$ space without hash sets.