Lesson 2 · Linear structures

Linked Lists and Pointer Operations

A linked list stores order through references between nodes rather than contiguous positions. Its power comes from rewiring a few links; its difficulty comes from preserving reachability during every update.

The node model

A singly linked node stores a value and a reference to the next node. A doubly linked node also stores the previous node, enabling backward movement and O(1) removal when the node itself is known.

Unlike an array, the kth element cannot be addressed directly; traversal from a known node is required. Random access is O(n), while a local insertion can be O(1).

Singly linked: less memory, forward traversal
Doubly linked: easier local removal, more bookkeeping
Circular lists connect the tail back to an earlier node

Rewire without losing the suffix

During reversal, changing current.next destroys the only route to the unprocessed suffix unless it was saved first. The safe order is: save next, reverse the edge, advance previous, advance current.

Draw nodes and arrows when an update feels uncertain. The invariant is that previous heads a fully reversed prefix while current heads the untouched suffix.

Store next before mutation
Change exactly the intended edge
Advance both frontier pointers
Check empty and one-node lists

Key reference

Terms, operations, and practical uses

Node vocabulary

HeadThe first reachable node; losing it can make the entire list unreachable.
Next referenceThe link from one node to its successor.
TailThe final node, whose next reference is null in a non-circular singly linked list.
Dummy nodeA temporary predecessor that makes head insertion and deletion follow the same rule as middle updates.

Safe pointer operations

SaveKeep the old successor before overwriting a link.
RewireChange exactly one reference while the remaining nodes are still reachable.
AdvanceMove the working pointers only after the new link is correct.

Useful variants

Doubly linked listStores both next and previous references for two-way traversal and local removal.
Circular listConnects the tail back to an earlier node instead of null.
Fast and slow pointersEncode a distance difference to find a midpoint, cycle, or node measured from the end.

Code example

Reverse a singly linked list

def reverse(head):
    previous = None
    current = head
    while current:
        following = current.next
        current.next = previous
        previous = current
        current = following
    return previous
class Node:
    def __init__(self, value, next=None):
        self.value, self.next = value, next

head = Node(10, Node(20, Node(30)))
node = reverse(head)
parts = []
while node:
    parts.append(str(node.value))
    node = node.next
print(' → '.join(parts) + ' → null')

ListNode* reverseList(ListNode* head) {
    ListNode* previous = nullptr;
    ListNode* current = head;
    while (current != nullptr) {
        ListNode* following = current->next;
        current->next = previous;
        previous = current;
        current = following;
    }
    return previous;
}

ListNode reverseList(ListNode head) {
    ListNode previous = null;
    ListNode current = head;
    while (current != null) {
        ListNode following = current.next;
        current.next = previous;
        previous = current;
        current = following;
    }
    return previous;
}

Input10 → 20 → 30 → null

Output30 → 20 → 10 → null

Example

Run the example step by step

Output

Dummy nodes and boundary cases

A dummy node placed before the real head gives deletion and insertion a guaranteed predecessor. Operations at the original head then use the same code as operations in the middle.

The dummy is an implementation tool, not part of the returned data. Return dummy.next, and be explicit about which pointer owns the result.

Removes special handling for head deletion
Simplifies merging and partitioning
Helps express an empty result safely

Fast and slow pointers

Moving one pointer twice as fast as another finds a midpoint or detects a cycle without extra storage. If a cycle exists, the pointers eventually meet because their relative distance changes by one on each round.

The second phase of cycle-entry detection follows from distances traveled, not magic. Reset one pointer to the head and advance both one step; their next meeting is the cycle entrance.

Midpoint and list splitting
Cycle existence and entry
Nth node from the end using a fixed gap