Singly Linked Lists

Topics Covered:
24. Singly Linked List Architecture & Heap Memory Layout • Core Node Operations (Insert, Delete, Search, Access) • In-Place 3-Pointer Reversal • Floyd's Cycle-Finding Algorithm & Cycle Start Derivation • Fast & Slow Pointer Patterns

Unlike contiguous arrays that rely on physical hardware adjacency for element ordering, linked lists build logical sequences through explicit directional pointers scattered across heap memory. This architectural decoupling enables true $O(1)$ dynamic insertions and deletions at the list boundary without memory reallocations or element shifts, but trades away constant-time indexing and hardware cache locality. This chapter details non-contiguous node topologies, memory alignment overheads, boundary-pointer manipulation invariants, the three-pointer in-place reversal state machine, and the mathematical proof underpinning Floyd's Tortoise and Hare cycle detection algorithm.

• Contrast the physical heap allocation and CPU cache-line miss rates of linked nodes against contiguous memory arrays.
• Calculate pointer memory overhead and 64-bit alignment padding for node-based data structures.
• Implement head, tail, and arbitrary position insertions and deletions with strict boundary-condition checks.
• Formulate the loop invariant for canonical three-pointer in-place list reversal and trace state transitions step-by-step.
• Formulate the mathematical proof of Floyd's Cycle-Finding Algorithm and derive why resetting one pointer to head guarantees collision at the cycle entrance.
• Apply fast-and-slow two-pointer patterns to find list midpoints and the $k$-th element from the end in a single pass.

A Singly Linked List is a linear data structure composed of self-contained Nodes, where each node encapsulates a data payload and a forward reference (pointer) to the next node in the sequence. The list begins with an external pointer called HEAD and terminates when a node's pointer references NULL.

Node Architecture in 64-Bit Memory

┌───────────────────────────────────────────────────────────────┐
│                      64-BIT NODE LAYOUT                       │
├───────────────────────────────┬───────────────────────────────┤
│       Data Payload (4 bytes)  │    Next Pointer (8 bytes)     │
│       + 4 bytes padding       │    Points to Heap Address     │
└───────────────────────────────┴───────────────────────────────┘

Physical Heap Allocation Reality

While an array requires an unbroken contiguous block of memory, linked list nodes are allocated dynamically at arbitrary, dispersed addresses across the heap.

⚠️ Memory Overhead & Cache Penalty:
Storing a 4-byte integer in a linked list node consumes $16\text{ bytes}$ in physical RAM due to pointer storage ($8\text{ bytes}$) and 64-bit alignment padding ($4\text{ bytes}$), representing a $300\%$ memory penalty over a flat array. Furthermore, because adjacent logical nodes reside at distant heap addresses, traversing links causes frequent CPU L1/L2 cache misses.

Interactive Simulation:
Step through pointer links, insertions, and traversals live in the Interactive Linked List Visualizer.

A. Head Insertion ($O(1)$)

Inserting a new node with value 10 before existing head node 20:

B. Insertion at Arbitrary Position $k$ ($O(n)$)

Inserting node 25 between node 20 (index 1) and node 30 (index 2):

C. The Tail Deletion Bottleneck in Singly Linked Lists

Even if an implementation maintains an explicit tail pointer to the final node, DeleteTail remains strictly $\Theta (n)$.

HEAD -> [10] -> [20] -> [30] -> NULL (tail points to [30])

To delete [30], the tail pointer must become [20], and [20].next must become NULL.
Because singly linked nodes lack backward (prev) pointers, there is no direct way
to inspect the predecessor of tail. The algorithm must traverse n - 1 nodes from HEAD
simply to discover that [20] precedes [30].

CLASS Node:
    field data: ValueType
    field next: Node Pointer <- NULL

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

CLASS SinglyLinkedList:
    field head: Node Pointer <- NULL
    field tail: Node Pointer <- NULL
    field size: Integer <- 0

    FUNCTION InsertAtHead(val: ValueType) -> Void:
        newNode <- new Node(val)
        newNode.next <- this.head
        this.head <- newNode
        if this.size == 0:
            this.tail <- newNode
        this.size <- this.size + 1

    FUNCTION InsertAtTail(val: ValueType) -> Void:
        newNode <- new Node(val)
        if this.size == 0:
            this.head <- newNode
            this.tail <- newNode
        else:
            this.tail.next <- newNode
            this.tail <- newNode
        this.size <- this.size + 1

    FUNCTION DeleteHead() -> ValueType:
        if this.head == NULL:
            raise UnderflowException("List is empty")
        temp <- this.head
        val <- temp.data
        this.head <- this.head.next
        if this.head == NULL:
            this.tail <- NULL
        this.size <- this.size - 1
        free(temp)
        return val

    FUNCTION DeleteTail() -> ValueType:
        if this.head == NULL:
            raise UnderflowException("List is empty")
        if this.head == this.tail:
            val <- this.head.data
            free(this.head)
            this.head <- NULL
            this.tail <- NULL
            this.size <- 0
            return val
        
        // Traverse to second-to-last node
        curr <- this.head
        while curr.next != this.tail:
            curr <- curr.next
        
        val <- this.tail.data
        free(this.tail)
        this.tail <- curr
        this.tail.next <- NULL
        this.size <- this.size - 1
        return val

Reversing a singly linked list in-place without allocating auxiliary nodes requires a sliding window of three pointers: prev, curr, and nextNode.

Invariant & Execution Loop

• Loop Invariant: At the start of each iteration, the sublist preceding curr is fully reversed with prev referencing its new head. curr references the head of the unreversed remaining sublist.

FUNCTION ReverseList(head: Node Pointer) -> Node Pointer:
    prev <- NULL
    curr <- head
    while curr != NULL:
        nextNode <- curr.next     // 1. Preserve forward link
        curr.next <- prev         // 2. Invert link to point backwards
        prev <- curr              // 3. Advance prev window
        curr <- nextNode          // 4. Advance curr window
    return prev                   // prev points to new reversed head

Step-by-Step State Trace: Reversing $[10\to 20\to 30\to \text{NULL}]$

Final Reconstructed State: $\text{HEAD}\to [30]\to [20]\to [10]\to \text{NULL}$.
Complexity: Strictly $\Theta (n)$ time, $O(1)$ auxiliary space.

Floyd's algorithm determines whether a linked list contains a cycle and identifies the exact entry node of that cycle using two pointers moving at different speeds, requiring only $O(1)$ auxiliary memory.

Mathematical Proof of Detection & Entry Derivation

List Topology:
HEAD -> [Node 1] -> [Node 2] -> [Cycle Entry: Node 3] -> [Node 4] -> [Node 5]
                                        ^                               |
                                        |                               v
                                  [Node 8] <-------- [Node 7] <------ [Node 6]

Let:

• $L$ = Distance from HEAD to the cycle entry node ($L=2$ in the diagram above: links $1\to 2$ and $2\to 3$).
• $C$ = Number of nodes in the cycle ($C=6$: nodes $3,4,5,6,7,8$).
• $d$ = Distance from the cycle entry node to the meeting point where slow and fast collide.

Step 1: Detection Proof

• slow advances $1$ node per step; fast advances $2$ nodes per step.
• The relative velocity is $2-1=1$ node per step.
• Once both pointers enter the cycle, fast reduces the gap by $1$ node on every iteration. Since the maximum possible gap is $C-1$, fast must collide with slow within at most $C$ iterations inside the cycle. An infinite loop is mathematically impossible.

Step 2: Cycle Entry Equation Derivation

Let $k$ be the total steps taken by slow when the collision occurs. Because fast travels at double speed, its total distance is $2k$:

Subtracting the first equation from the second:

The total steps $k$ is an exact integer multiple of the cycle length $C$.

Substituting $k=m\cdot C$ into the slow distance formula:

The Critical Identity:

The term $(C-d)$ is the exact distance remaining from the collision point to the cycle entry node.
Therefore, the distance from HEAD to the cycle entry ($L$) equals the distance from the collision point to the cycle entry ($(C-d)$), modulo full loops.

Algorithmic Resolution:

1. When slow and fast meet at the collision point, leave fast at the collision point.
2. Reset slow to HEAD.
3. Advance both slow and fast at a uniform speed of 1 step per iteration.
4. Both pointers will collide at the exact cycle entry node!

FUNCTION DetectAndFindCycleEntry(head: Node Pointer) -> Node Pointer:
    slow <- head
    fast <- head
    hasCycle <- False

    // Phase 1: Detect cycle
    while fast != NULL and fast.next != NULL:
        slow <- slow.next
        fast <- fast.next.next
        if slow == fast:
            hasCycle <- True
            break

    if not hasCycle:
        return NULL

    // Phase 2: Find cycle entry node
    slow <- head
    while slow != fast:
        slow <- slow.next
        fast <- fast.next
    return slow

1. Trade-offs vs. Arrays: Linked lists eliminate the need for large contiguous memory blocks and achieve true $O(1)$ head insertions, but forfeit $O(1)$ random indexing and suffer from poor CPU cache locality.
2. Pointer Overhead: 64-bit systems impose an 8-byte pointer cost and 4-byte padding per node, causing up to a $300\%$ memory footprint increase for 32-bit payloads.
3. Tail Deletion Vulnerability: Even with an explicit tail reference, DeleteTail on a singly linked list requires $\Theta (n)$ time to scan for the penultimate node.
4. Three-Pointer Reversal: Inverting link references requires holding nextNode before mutating curr.next, advancing prev and curr in lockstep.
5. Floyd's Mathematical Harmony: The distance from HEAD to the cycle entrance equals the distance from the collision point to the entrance, enabling $O(n)$ time, $O(1)$ space cycle entrance discovery.

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. Floyd, R. W. (1967). Non-deterministic Algorithms. Journal of the ACM, 14(4), 636-644.
3. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 1.3: Bags, Queues, and Stacks. Addison-Wesley.
4. Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.), Section 2.2: Linear Lists. Addison-Wesley.