Understanding Linked Lists: Storage, Structures, and Two-Pointer Techniques

Overview

The series begins by emphasizing why programmers should study algorithms and data structures despite most daily work relying on frameworks. Reasons include preparing for big‑company interview questions, avoiding a career limited to simple CRUD tasks, and keeping problem‑solving skills sharp.

Interview preparation: algorithms test a programmer's fundamentals.

Understanding underlying implementations of frameworks and middleware (e.g., why Redis uses skip lists for ordered sets).

Enhancing thinking ability and writing more robust code.

What Are Data Structures and Algorithms?

Data structures are ways to store collections of data; algorithms are methods that operate on those structures and require mathematical reasoning. Common structures include queues, stacks, heaps, binary search, and dynamic programming. Data structures serve algorithms, and most structures are built on either arrays (sequential storage) or linked lists (pointer‑based storage).

Arrays vs. Linked Lists

Array : contiguous memory, fast random access, space‑efficient, but resizing and middle insert/delete require O(N) copying and shifting.

Linked List : nodes stored in scattered memory blocks linked by pointers, no resizing issue, O(1) insertion/deletion given a node, but no random access and extra memory for pointers.

Linked List

Storage

Unlike arrays that need a large continuous block, a linked list can be built from many non‑contiguous memory chunks, so allocating a 100 MB list succeeds even when a 100 MB contiguous array would fail.

Structures

Common linked‑list variants:

Singly linked list : each node stores data and a next pointer to the following node.

Doubly linked list : nodes have both next and prev pointers, allowing traversal in two directions. The JDK’s AbstractQueuedSynchronizer uses a CLH queue implemented as a doubly linked list.

Circular linked list : like a singly list but the tail’s next points back to the head, making it easy to move from tail to head.

Operations

Insertion after node p:

new_node->next = p->next;
p->next = new_node;

If p is null (inserting into an empty list), the above code fails – a boundary case.

Deletion of the node following p: p->next = p->next->next; When the list has only one node left, this also hits a boundary case.

To unify handling of empty and non‑empty lists, a dummy (sentinel) node can be introduced so that head always points to this sentinel. The same insertion and deletion code then works for all cases.

Two‑Pointer Techniques

Fast‑Slow Pointer for Cycle Detection

Initialize fast and slow at the head. fast moves two steps, slow one step. If they meet, a cycle exists; if fast reaches null, the list is acyclic.

boolean hasCycle(ListNode head) {
    ListNode fast = head, slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) return true;
    }
    return false;
}

Finding the Start of a Cycle

After detecting a cycle, keep fast at the meeting point, reset slow to head, then move both one step at a time. Their next meeting point is the cycle’s entry node.

ListNode detectCycle(ListNode head) {
    ListNode fast = head, slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) break;
    }
    if (fast == null || fast.next == null) return null; // no cycle
    slow = head;
    while (slow != fast) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow; // start of cycle
}

The reasoning: at first meeting, fast has traveled 2k steps and slow k steps, where k equals the distance from head to the meeting point plus some whole number of loop lengths. Resetting one pointer to head makes the remaining distance to the entry equal for both.

Finding the Middle Node

Using the same fast‑slow idea, when fast reaches the end, slow points to the middle (left‑middle for even length, exact middle for odd).

while (fast != null && fast.next != null) {
    fast = fast.next.next;
    slow = slow.next;
}
return slow; // middle node

These techniques are frequently used in LeetCode linked‑list problems (e.g., https://leetcode.cn/problemset/algorithms/?topicSlugs=linked-list) and in algorithm tutorials such as https://labuladong.gitee.io/algo/di-ling-zh-bfe1b/shuang-zhi-0f7cc/.