Beyond the Single Direction

[!NOTE] This module explores the core principles of Doubly & Circular Lists, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Concept Definition

Singly Linked Lists are efficient but frustrating: you can’t look back. If you are at Node 5 and need something from Node 4, you have to start over from the Head.

Enter the Doubly Linked List (DLL).

Each node now carries two pointers:

1. Next: Points forward.
2. Prev: Points backward.

A Circular Linked List is a variation where the Tail points back to the Head instead of null, creating an infinite loop.

The “Music Playlist” Analogy

Think of a Singly Linked List as a cassette tape: you can only play forward, and if you skip past a song, you have to rewind to the beginning. A Doubly Linked List is like a modern music app playlist: you can easily skip forward to the next track or skip backward to the previous one in O(1) time. A Circular Linked List is simply putting that playlist on “Repeat All”—when the last track finishes, it loops seamlessly back to the first track without stopping.

Edge Cases & Clarifying Questions

Before writing code for any DLL problem, always clarify these edge cases:

• Single Node Lists: What happens when the Head and Tail are the same node?
• Empty Lists: How does the logic handle null inputs?
• Deleting the Head/Tail: Does your code properly update the global head or tail pointers when removing edge nodes?

---

2. Interactive Analysis

Experience bidirectional traversal. Toggle “Circular Mode” to connect Tail to Head.

Node: 0

Circular Mode

Start at Head.

---

3. Intuition

The Genesis: From Brute Force to Optimized

The Problem: In a standard Singly Linked List, if you want to delete a specific node B, you must update the next pointer of the node that precedes it (A). Since you cannot travel backward, you are forced to start at the Head and traverse the entire list until you find A. This is a brute-force O(N) operation.

The Optimization: If we trade space for time by storing an extra pointer (prev) at each node, we immediately know who precedes us. This extra 8 bytes of memory per node fundamentally shifts deletion and reverse traversal from O(N) to O(1) time.

Memory Trade-off

• Singly: 4 bytes (int) + 8 bytes (next) = 12 bytes per node.
• Doubly: 4 bytes (int) + 8 bytes (next) + 8 bytes (prev) = 20 bytes per node.
• Cost: ~66% more memory overhead per node.
• Benefit: O(1) deletion if you have the node (no need to search for the previous node).

The Superpower: O(1) Deletion

In a Singly Linked List, to delete Node B, you need a pointer to Node A (its predecessor). This requires scanning from the Head (O(N)).

In a Doubly Linked List, B knows about A via B.prev. We can delete B in O(1) if we have a reference to it.

// O(1) Deletion
node.prev.next = node.next;
node.next.prev = node.prev;

[!WARNING] Always check for null. If you delete the Head or Tail, prev or next might not exist.

Common Pitfalls

• Dangling Pointers: Forgetting to update the prev pointer of node.next when deleting node, leaving the next node pointing to a detached element.
• Circular Infinite Loops: When traversing a circular list, failing to set a strict termination condition (like checking if the current pointer equals the original Head) resulting in an infinite loop during search operations.

---

4. Implementation

Java

Go

class DoublyNode {
  int val;
  DoublyNode next;
  DoublyNode prev;

  public DoublyNode(int val) {
    this.val = val;
  }
}

class DoublyLinkedList {
    DoublyNode head;
    DoublyNode tail;

    // Add to Head
    public void addFirst(int val) {
        DoublyNode newNode = new DoublyNode(val);
        if (head == null) {
            head = tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }

    // Delete Node (O(1) given reference)
    public void remove(DoublyNode node) {
        if (node.prev != null) node.prev.next = node.next;
        else head = node.next; // Removing head

        if (node.next != null) node.next.prev = node.prev;
        else tail = node.prev; // Removing tail
    }
}

type DoublyNode struct {
  Val  int
  Next *DoublyNode
  Prev *DoublyNode
}

type DoublyLinkedList struct {
    Head *DoublyNode
    Tail *DoublyNode
}

// Add to Head
func (dll *DoublyLinkedList) AddFirst(val int) {
    newNode := &DoublyNode{Val: val}
    if dll.Head == nil {
        dll.Head = newNode
        dll.Tail = newNode
    } else {
        newNode.Next = dll.Head
        dll.Head.Prev = newNode
        dll.Head = newNode
    }
}

// Delete Node (O(1) given reference)
func (dll *DoublyLinkedList) Remove(node *DoublyNode) {
    if node.Prev != nil {
        node.Prev.Next = node.Next
    } else {
        dll.Head = node.Next
    }

    if node.Next != nil {
        node.Next.Prev = node.Prev
    } else {
        dll.Tail = node.Prev
    }
}

---

5. Complexity Analysis

Operation	Time	Space	Notes
Search	O(N)	O(1)	Must scan. Can search from Head or Tail.
Insert (Head/Tail)	O(1)	O(1)	Pointer swaps only.
Delete (Given Node)	O(1)	O(1)	No traversal needed.
Delete (By Value)	O(N)	O(1)	Must search first.