Doubly & Circular Linked Lists

Topics Covered:
25. Doubly Linked List (DLL) Architecture & Bi-Directional Traversal • $O(1)$ Arbitrary Deletion Mechanics • The Sentinel / Dummy Node Pattern • 26. Circular Singly Linked List (CSLL) • Circular Doubly Linked List (CDLL) • The Josephus Elimination Problem & Simulation

While singly linked lists provide unidirectional linear chains, systems programming and high-performance caching require bi-directional navigation and true $O(1)$ arbitrary node removals. Doubly linked lists achieve this by embedding both predecessor (prev) and successor (next) references within each node, while circular variants loop terminal pointers back to the entry node to form endless ring buffers. This chapter details bidirectional heap node topologies, sentinel-based elimination of boundary pointer edge cases, the mechanics of constant-time arbitrary deletion, and cyclic simulations including the classic Josephus elimination problem.

• Differentiate the memory layouts, pointer alignment overheads, and traversal capabilities of singly, doubly, and circular linked structures.
• Prove why holding a direct node reference enables true $O(1)$ deletion in doubly linked lists versus $O(n)$ in singly linked lists.
• Implement the Sentinel (Dummy Head & Tail) architectural pattern to eliminate null-pointer branch penalties and edge-case exceptions.
• Construct Circular Singly Linked Lists (CSLL) using a single tail pointer to guarantee $O(1)$ insertions at both ends without tracking head.
• Formulate the Josephus elimination problem using circular pointer chains and verify the simulation against the closed-form recurrence $J(n,2)=2(n-2^{\lfloor {\log }_{2}n\rfloor })+1$.

A Doubly Linked List (DLL) is a sequence of dynamically allocated nodes where each node contains two pointers:

1. next: Stores the virtual heap address of the succeeding node.
2. prev: Stores the virtual heap address of the preceding node.

┌─────────────────────────────────────────────────────────────────────────┐
│                        64-BIT DOUBLY NODE LAYOUT                        │
├───────────────────┬───────────────────┬─────────────────────────────────┤
│    prev pointer   │   data payload    │          next pointer           │
│     (8 bytes)     │     (4 bytes)     │           (8 bytes)             │
│   Offset: +0      │    Offset: +8     │          Offset: +16            │
└───────────────────┴───────────────────┴─────────────────────────────────┘

Total node size is $24\text{ bytes}$. Compared to a flat array storing a 4-byte integer, a DLL node incurs a $500\%$ memory overhead.

Virtual Memory Layout Example

In cache eviction systems (e.g., Least Recently Used / LRU Cache) and OS process scheduling queues, an algorithm frequently needs to evict an item given a direct reference to that node (for instance, retrieved from an auxiliary hash map).

• In a Singly Linked List, deleting node $X$ requires starting at HEAD and walking forward until finding node $P$ whose next == X ($\Theta (n)$ time).
• In a Doubly Linked List, node $X$ already knows its predecessor ($X.\text{prev}$) and its successor ($X.\text{next}$). Deletion requires only rewiring two pointers!

State Transition Table: Deleting Node $20$ from $[10\leftrightarrow 20\leftrightarrow 30]$

Managing boundary conditions in raw linked lists leads to conditional branches for empty lists, single-element lists, head mutations, and tail mutations.

The Sentinel Solution

Introduce two permanent invariant nodes that hold no client data:

• headSentinel: Always sits before the first true data node.
• tailSentinel: Always sits after the last true data node.

Empty List with Sentinels:
[ headSentinel ] <===================> [ tailSentinel ]
(prev = NULL, next = tailSentinel)     (prev = headSentinel, next = NULL)

Populated List with Sentinels:
[ headSentinel ] <===> [ Node 10 ] <===> [ Node 20 ] <===> [ Node 30 ] <===> [ tailSentinel ]

Why Sentinels Eliminate Edge Cases:

Every user node—regardless of whether it is at the front, middle, or back—always has a non-null predecessor and a non-null successor. Special if (head == NULL) checks completely disappear from the codebase.

CLASS DoublyNode:
    field data: ValueType
    field prev: DoublyNode Pointer <- NULL
    field next: DoublyNode Pointer <- NULL

    CONSTRUCTOR(val: ValueType):
        this.data <- val

CLASS SentinelDoublyLinkedList:
    field headSentinel: DoublyNode Pointer
    field tailSentinel: DoublyNode Pointer
    field size: Integer <- 0

    CONSTRUCTOR():
        this.headSentinel <- new DoublyNode(DEFAULT)
        this.tailSentinel <- new DoublyNode(DEFAULT)
        this.headSentinel.next <- this.tailSentinel
        this.tailSentinel.prev <- this.headSentinel
        this.size <- 0

    FUNCTION InsertAfterNode(targetNode: DoublyNode, val: ValueType) -> DoublyNode:
        newNode <- new DoublyNode(val)
        successor <- targetNode.next

        newNode.prev <- targetNode
        newNode.next <- successor
        targetNode.next <- newNode
        successor.prev <- newNode

        this.size <- this.size + 1
        return newNode

    FUNCTION InsertAtHead(val: ValueType) -> DoublyNode:
        return this.InsertAfterNode(this.headSentinel, val)

    FUNCTION InsertAtTail(val: ValueType) -> DoublyNode:
        return this.InsertAfterNode(this.tailSentinel.prev, val)

    FUNCTION DeleteNode(targetNode: DoublyNode) -> ValueType:
        if targetNode == this.headSentinel or targetNode == this.tailSentinel:
            raise BoundaryException("Cannot delete sentinel nodes")

        predecessor <- targetNode.prev
        successor <- targetNode.next

        predecessor.next <- successor
        successor.prev <- predecessor

        val <- targetNode.data
        free(targetNode)
        this.size <- this.size - 1
        return val

    FUNCTION DeleteHead() -> ValueType:
        if this.size == 0:
            raise UnderflowException("List is empty")
        return this.DeleteNode(this.headSentinel.next)

    FUNCTION DeleteTail() -> ValueType:
        if this.size == 0:
            raise UnderflowException("List is empty")
        return this.DeleteNode(this.tailSentinel.prev)

A Circular Linked List eliminates terminal NULL pointers by connecting the final node back to the initial node, forming an unbroken ring buffer.

Comparison of Circular Topologies

Circular Singly Linked List:
HEAD -> [ 10 ] -> [ 20 ] -> [ 30 ] (TAIL)
  ^                            |
  |----------------------------|

Circular Doubly Linked List:
  |---------------------------------------------------------|
  v                                                         |
[ 10 (HEAD) ] <==========> [ 20 ] <==========> [ 30 (TAIL) ]
  |                                                         ^
  |---------------------------------------------------------|

In a standard singly linked list, maintaining a pointer to HEAD requires an $O(n)$ traversal to append at the tail. In a Circular Singly Linked List, maintaining only a pointer to TAIL provides instant $O(1)$ access to both ends:

• Tail Access: Direct via tail.
• Head Access: Direct via tail.next!
• Insert At Head: Insert a new node between tail and tail.next.
• Insert At Tail: Insert between tail and tail.next, then advance tail = newNode.

FUNCTION InsertAtHeadCSLL(tail: Node Pointer, val: ValueType) -> Node Pointer:
    newNode <- new Node(val)
    if tail == NULL:
        newNode.next <- newNode
        return newNode
    newNode.next <- tail.next
    tail.next <- newNode
    return tail

FUNCTION InsertAtTailCSLL(tail: Node Pointer, val: ValueType) -> Node Pointer:
    newNode <- new Node(val)
    if tail == NULL:
        newNode.next <- newNode
        return newNode
    newNode.next <- tail.next
    tail.next <- newNode
    return newNode    // newNode is the new tail

Problem Formulation

$n$ people stand in a circle labeled $1$ through $n$. Beginning at person $1$, counting proceeds clockwise. Every $k$-th person is eliminated. The circle closes and counting resumes from the person immediately following the eliminated individual. The goal is to determine the safe starting position $J(n,k)$ that guarantees survival.

Analytical Formula for $k=2$

When $k=2$ (every second person is eliminated), the problem admits an elegant closed-form solution based on powers of 2:

For $n=5$:

• $\lfloor {\log }_{2}5\rfloor =2⟹2^2=4$
• $J(5,2)=2(5-4)+1=2(1)+1=3$

Simulation via Circular Linked List ($n=5,k=2$)

The simulation confirms the theoretical derivation: Person 3 survives.

FUNCTION JosephusSurvivor(n: Integer, k: Integer) -> Integer:
    head <- new Node(1)
    prev <- head
    for i from 2 to n:
        curr <- new Node(i)
        prev.next <- curr
        prev <- curr
    prev.next <- head    // Close the circular ring

    curr <- head
    while curr.next != curr:
        for step from 1 to k - 2:
            curr <- curr.next
        // Delete the k-th node
        eliminated <- curr.next
        curr.next <- eliminated.next
        free(eliminated)
        curr <- curr.next
    survivor <- curr.data
    free(curr)
    return survivor

Simulation Complexity: $O(n\cdot k)$ time, $O(n)$ auxiliary space.

1. Bidirectional Navigation: Doubly linked lists trade $16$ bytes of pointer overhead per node for true $O(1)$ deletion of arbitrary nodes and bidirectional traversal.
2. Sentinel Pattern: Invariant dummy head and tail nodes eliminate null pointer dereferences and special boundary checks.
3. Single Tail Optimization: Storing only a tail reference in a Circular Singly Linked List grants $O(1)$ operations at both head (tail.next) and tail (tail).
4. Natural Ring Topologies: Circular lists are the natural data structure for round-robin CPU schedulers, periodic ring buffers, and cyclic elimination simulations.

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Chapter 10: Elementary Data Structures. MIT Press.
2. Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.), Section 2.2: Linear Lists. Addison-Wesley.
3. Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete Mathematics: A Foundation for Computer Science (2nd ed.), Section 1.3: The Josephus Problem. Addison-Wesley.
4. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 1.3: Bags, Queues, and Stacks. Addison-Wesley.