Introduction to LinkedList

A linked list stores a sequence of values by giving each element a pointer to the next one, so the collection can grow or shrink by rewiring a couple of pointers rather than moving any existing data — the trade-off it makes for that flexibility is giving up direct index-based access, since the only way to reach the k-th node is to walk the chain from the head.

Anatomy

• Node — a small object holding data and next (a reference to the following node, or null).
• Head — the entry point; an empty list is represented by head == null.
• Tail — the last node; in a singly linked list its next is null. Caching a separate tail reference is a common optimization for O(1) appends, but the reference implementation below does not do this — it walks from head to find the last node on every insertEnd call, so append stays O(n) unless you add a cached tail pointer yourself.

Recognize the pattern

Reach for a linked list — or recognize one is in play — when you see: frequent insert/delete at the front or a known middle position without shifting elements; an unbounded/unknown final size; a need to splice two sequences together cheaply; or when the problem explicitly gives you ListNode/next and asks for reversal, cycle detection, merging, or k-th-from-end — these are the classic tells that array-index tricks won't apply and pointer manipulation is the intended tool.

Brute force vs. optimal, on the operations that matter

The array's weakness (shifting on insert/delete) is exactly the linked list's strength, and vice versa for access. There is no free win — you're trading random access for O(1) structural edits.

Complexity, derived

Time. Insertion/deletion at a node you already hold a reference to touches a constant number of pointer fields (1–3 reassignments depending on the operation, see table above) regardless of list length → O(1). Finding that node in the first place requires following next pointers one at a time starting at head; in the worst case (target at the tail, or absent) that's n dereferences → O(n). So "linked-list insert is O(1)" is only true for the splice itself, not including the search to locate the splice point.

Space. Per-node overhead is JVM/heap-config dependent, not a fixed number: on HotSpot with the default Compressed Oops (enabled automatically for heaps under ~32GB), an object reference is 4 bytes, not 8 — 8-byte references only apply once compressed oops is disabled or the heap exceeds that threshold. On top of the pointer field, every node also carries an object header (typically 12–16 bytes on HotSpot for mark word + class pointer), which usually outweighs the pointer field itself in real accounting. So total space is O(n) for payload data plus O(n) per-node overhead (header + one reference), versus an array's O(n) with no per-element pointer or header cost but potential unused pre-allocated capacity.

Traced example — building 10 → 20 → 30 and inserting 15

1. Start: head = null.
2. insertEnd(10): new node A(10,null); head = A. List: 10.
3. insertEnd(20): new node B(20,null); A.next = B. List: 10 → 20.
4. insertEnd(30): new node C(30,null); B.next = C. List: 10 → 20 → 30.
5. Insert 15 after value 20: walk head→A(10)→B(20), found B. Create new node D(15, null). Splice in pointer-safe order: first D.next = B.next (so D now points to C, preserving the rest of the chain), then B.next = D (so B now points to D). List: 10 → 20 → 15 → 30.

Steps 2–4 and the splice in step 5 are each O(1) pointer work; the walk in step 5 to find B costs O(n). The order in step 5 matters: setting D.next before overwriting B.next is what prevents the tail (C) from being orphaned — doing it in reverse would lose the rest of the list.

Reference implementation

class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; this.next = null; }
}

class LinkedList {
    Node head;

    void insertEnd(int value) {
        Node n = new Node(value);
        if (head == null) { head = n; return; }
        Node cur = head;
        while (cur.next != null) cur = cur.next; // O(n) walk (no cached tail)
        cur.next = n;                             // O(1) splice
    }

    void insertAfterValue(int target, int value) {
        Node cur = head;
        while (cur != null && cur.data != target) cur = cur.next; // O(n)
        if (cur == null) return; // target not found
        Node n = new Node(value);
        n.next = cur.next;       // capture the rest of the chain first
        cur.next = n;            // O(1) splice
    }
}

Pitfalls

• Losing the reference to the remainder of the list by overwriting cur.next before saving it — always set the new node's next to cur.next first, then repoint cur.next to the new node (classic reversal bug, and the exact order shown in the traced example above).
• Forgetting the head == null (empty list) case, causing a NullPointerException on the first insert/delete.
• Off-by-one when tracking the predecessor node for deletion — you need the node before the target, not the target itself, to unlink it in a singly linked list.
• Poor cache locality: because nodes are heap-scattered, sequential traversal is slower in practice than an array scan of the same size despite both being O(n).

When to use / when not

Use a linked list when insert/delete at the ends or at an already-located position dominates and list size is unpredictable (e.g., LRU cache eviction list, adjacency lists, undo stacks). Avoid it when you need random access by index, binary search, or cache-friendly iteration — an array / ArrayList wins there, trading O(n) worst-case resize for O(1) amortized append and O(1) index access. A dynamic array is almost always the better default in modern managed languages unless structural churn in the middle of the sequence is frequent and locatable in O(1).

The five transferable moves

Nearly every interview list problem is a combination of a few reusable moves, not a new algorithm each time:

• Reverse (iterative) — prev/curr/next, flip each edge, return prev: Θ(n) time, Θ(1) aux space. The recursive version walks Θ(n) stack frames, so it is not an O(1)-space reverse.
• Dummy head — a sentinel node before the real head unifies head edits with middle edits (head-delete, merges, results built from scratch): return dummy.next once, no special cases.
• Fast/slow (Floyd) — slow advances 1, fast advances 2; they meet iff there is a cycle, and slow sits at the middle when fast hits the end. Without a cycle, fast reaches null in at most n/2 double-steps; with one, the relative speed of 1 closes the gap within a cycle length.
• Merge — compare the heads of two sorted lists, advance the smaller, attach the remainder at the end.
• Null edges first — empty list, single node, head change, last node, unequal lengths: check these before the happy path (insert-after-a-missing-value should walk to null and no-op, not throw).

Takeaways

• Linked lists trade O(1) index access (array's strength) for O(1) splice-once-located (array's weakness).
• The O(1) claim for insert/delete only covers the pointer rewiring, not the O(n) search to find the splice point — and front-insert (2 touches) and front-delete (1 touch) aren't the same cost even though both are O(1).
• Always null-check the head and set the new node's next before overwriting the existing pointer during relinking.
• Per-node space overhead depends on JVM heap config (4-byte compressed vs. 8-byte uncompressed references) plus a ~12–16 byte object header — don't quote a single number as universal.

Recall: Why is inserting a new node after a known node O(1), but inserting "the value after 20" overall still O(n)?

Synthesized from the source lesson plus standard CS data-structures references (CLRS-style linked list analysis) and HotSpot JVM object layout documentation.