Nodes and pointers

A chain of nodes

The first module contrasted contiguous data, where the address of each element is computed, with scattered data, where it is stored in a pointer. A linked list is the simplest scattered structure. Each element lives in its own node, a small object holding two things: the value, and the address of the next node, called next. The last node's next is null, which marks the end. The program keeps one more pointer, the head, which leads to the first node.

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
 
head = Node(1, Node(2, Node(3)))     # 1 → 2 → 3 → None

Each node is allocated separately, so the nodes can be anywhere in memory. The list's order lives entirely in the next pointers, not in where the nodes sit.

Walking the list

Almost every operation on a linked list starts by walking it:

node = head
while node is not None:
    print(node.val)
    node = node.next

That loop visits each node once, so traversal is O(n). The consequences are worth spelling out, because they are the opposite of an array's:

• Access by position is O(k). To read the 500th value, follow 499 pointers. There is no base + i × size.
• Search is O(n). Finding a value means checking nodes one by one, even if the list is sorted, because you can't jump to the middle to do a binary search.
• Length is O(n) unless the list keeps a counter, as most library implementations do.

What a linked list offers in return is cheap rewiring. Once you hold a pointer to a node, you can insert a new node after it or remove the node after it by changing one or two pointers, without moving any other element. The next lesson covers those operations.

Reversing by rewiring

Reversal shows the style of thinking linked lists need. An array is reversed by swapping values from both ends. A linked list is reversed without touching any value: every next pointer is turned around to point at the previous node instead of the next one.

The trace above does this with three variables. curr is the node being processed, prev is the node before it, and nxt saves the node after it. Each pass does four things in a fixed order: save curr.next in nxt, point curr.next back at prev, move prev forward to curr, and move curr forward to nxt. When curr runs off the end, prev is the old tail, which is the new head.

The order is not optional. If the loop overwrote curr.next before saving it, the rest of the list would become unreachable: no variable would hold its address, and in a garbage-collected language it would be quietly freed. Most linked-list bugs are some version of this mistake, so a useful habit is to ask, before every pointer write, "is anything only reachable through the pointer I'm about to change?"

Invariants make it obvious

The reversal loop is short, but it is easy to get subtly wrong. Stating its invariant makes it easy to check. Every time the loop reaches its top:

• prev is the head of a reversed list containing every node already processed;
• curr is the head of the original list's remaining nodes;
• together, the two lists contain every node exactly once.

At the start, prev is empty and curr is the whole list, so the invariant holds. Each pass moves exactly one node from the front of curr's list to the front of prev's list, so it still holds afterwards. When curr is empty, prev's list contains every node, reversed. This style of argument, true at the start, preserved by each step, useful at the end, is how every pointer manipulation in this module and the next ones can be checked.

A recursive reversal is also possible: reverse the rest of the list, then attach the current node at its end. It is elegant, but it uses one stack frame per node, so it needs O(n) stack space and fails on long lists in languages without unlimited recursion. The iterative version uses O(1).

Variations

Real lists come in a few shapes:

• Singly linked, as above: each node points to the next. Smallest, but you can only walk forward.
• Doubly linked: each node also points to the previous one. One more pointer per node, but a node can be removed given only a pointer to itself, and the list can be walked in both directions. Java's LinkedList and C++'s std::list are doubly linked.
• Circular: the last node points back to the first, so there is no null at the end. Combined with a sentinel node, this removes every special case from insertion and deletion.

Linked lists rarely appear as a general-purpose container in modern code, for reasons the last lesson of this module measures. They are everywhere as building blocks, though: the chains inside hash tables, the free lists inside memory allocators, the lists of processes and buffers inside the Linux kernel, and the history behind an editor's undo command.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Nodes and pointers from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

function reverse_and_find_mid(head):
    slow = head; fast = head
    while fast != null and fast.next != null:
        slow = slow.next
        fast = fast.next.next
    prev = null; curr = slow
    while curr != null:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};
 
ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *curr = head;
    while (curr != nullptr) {
        ListNode* nxt = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nxt;
    }
    return prev;
}

public class LinkedListSolver {
    public static class ListNode {
        int val; ListNode next;
        ListNode(int v) { this.val = v; }
    }
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode nxt = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nxt;
        }
        return prev;
    }
}

class ListNode:
    def __init__(self, val: int = 0, next: "ListNode | None" = None) -> None:
        self.val = val
        self.next = next
 
def reverse_list(head: ListNode | None) -> ListNode | None:
    prev, curr = None, head
    while curr is not None:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.