Linked Lists

Linked lists teach pointer thinking: how to rewire structure safely, how to reason about nodes instead of indices, and how to keep invariants stable while the shape of the data changes.

---

1. Definition

What is a linked list?

A linked list is a linear data structure made of nodes. Each node stores a value and a reference to another node. In a singly linked list, each node points to the next node; in a doubly linked list, each node points both forward and backward. Unlike an array, the elements are not stored by index in one contiguous block — the structure is held together by references.

Why does it exist?

A linked list exists to make local structural changes cheap. If you already know the node before the insertion or deletion point, rewiring pointers can be done in O(1). That is the main trade-off: you gain flexible structural updates but lose direct index access.

Where does it fit?

Linked lists matter when the problem is about pointer updates, node insertion or removal, reversing order, splitting or merging lists, detecting cycles, or building comfort with reference manipulation. In interviews, linked lists are less about production container choice and more about precision — they reveal whether you can change structure without losing information.

Intuition

Think of a linked list like train cars. Each car knows the next car. If you want to remove one car, you do not shift every later car left like in an array — you reconnect the previous car to the next car. That is why local edits are cheap. If someone asks for the car at position 17, however, you must walk through the chain. That is why random access is slow.

Java context

In Java, linked list interview problems usually use a custom ListNode class. The point is rarely the JDK LinkedList API — the point is to show that you understand references, null handling, and structural invariants. A minimal node looks like this:

class ListNode {
    int value;
    ListNode next;

    ListNode(int value) {
        this.value = value;
    }

    ListNode(int value, ListNode next) {
        this.value = value;
        this.next = next;
    }
}

Why this topic is hard for many people

Many candidates do not fail because linked lists are conceptually deep. They fail because one small pointer update is done in the wrong order. That means this topic is really about disciplined state handling.

---

2. Core Concepts

2.1 Node-based structure

A linked list is not one big object with indexed slots — it is a chain of node objects. Each node contains payload data, one or more links, and sometimes auxiliary metadata.

2.2 Singly vs doubly linked list

Variant	Node links	Strength	Cost
Singly linked list	next	Simple, lightweight	No direct backward movement
Doubly linked list	prev, next	Easier removal and reverse traversal	More memory, more pointer maintenance

For interview problems, singly linked lists are the most common.

2.3 Head and tail thinking

The head is the first node. Sometimes you also track a tail, which helps when appending matters. But tail references also increase the number of invariants you must maintain. Examples: empty list → head == null (maybe tail == null); one-element list → head == tail; multi-element list → tail.next == null.

2.4 Traversal is sequential

To reach the node at position k, you walk k steps. That means access by index is O(n), searching by value is O(n), and many solutions begin with a traversal phase. This is one reason linked lists are often worse than arrays for raw scanning workloads.

2.5 Insertion and deletion by rewiring

The real power is pointer rewiring.

If prev points to the node before current, then deleting current is conceptually:

prev.next = current.next;

If you want to insert newNode after prev, the safe pattern is:

newNode.next = prev.next;
prev.next = newNode;

The order matters.

If you overwrite prev.next too early, you can lose the rest of the list.

2.6 Dummy node pattern

A dummy node is a fake node placed before the real head.

It simplifies edge cases.

Why it helps:

• deleting the real head becomes a normal deletion,
• inserting before the first real node becomes ordinary,
• and your logic stops branching on “is this the first node?”.

This is one of the most useful linked list interview patterns.

2.7 Reversal thinking

Reversal is a classic exercise because it forces you to preserve information while rewiring links.

The standard iterative invariant is:

• previous holds the already reversed prefix,
• current holds the next node to process,
• nextNode temporarily preserves the remainder.

Without that saved nextNode, the rest of the list can disappear from reach.

2.8 Fast and slow pointers

Two-pointer linked-list problems often use:

• slow pointer moving one step,
• fast pointer moving two steps.

This pattern helps with:

• cycle detection,
• middle node finding,
• linked list splitting,
• and palindrome-related preparation.

2.9 Cycle detection

Floyd’s tortoise-and-hare algorithm is the standard cycle pattern.

If a cycle exists, a faster pointer eventually laps the slower pointer.

If the fast pointer reaches null, the list is acyclic.

The beauty is that it uses O(1) extra space.

2.10 Complexity profile

Operation	Complexity	Notes
Access by index	O(n)	Must walk node by node
Search by value	O(n)	Sequential scan
Insert at front	O(1)	Head update
Delete front	O(1)	Head update
Insert after known node	O(1)	Rewiring only
Delete after known previous node	O(1)	Rewiring only
Append without tail	O(n)	Must walk to end
Append with tail	O(1)	If tail invariant is maintained

2.11 Reference semantics matter

With arrays, “position” is often the main identity.

With linked lists, the node reference itself matters.

That changes the debugging mindset.

Instead of saying “I am at index i”, you often say:

• “current is the node being processed”,
• “previous is the end of the solved region”,
• “slow points to the candidate middle”.

2.12 Recognition signals

Linked-list reasoning should trigger when you see:

• custom node classes,
• next/prev references,
• reversal,
• remove the n-th node,
• detect a cycle,
• merge two sorted lists,
• reorder a chain,
• split a list,
• or constant-space structural edits.

---

3. Practical Usage

When to use linked-list thinking in interviews

Use linked-list thinking when the input is explicitly node-based.

Typical signals:

• “Given the head of a linked list...”
• “Reverse the list”
• “Remove duplicates from a sorted linked list”
• “Detect whether the list contains a cycle”
• “Merge two sorted linked lists”

In these problems, trying to force index-based thinking usually makes the solution worse.

Typical linked-list patterns

Common families include:

• dummy node for head-safe mutation,
• fast/slow pointer for middle and cycle tasks,
• iterative reversal,
• recursive reversal,
• merge with tail builder,
• partition with multiple temporary lists,
• and read-pointer/write-pointer style rewiring.

When linked lists are a poor production choice

In many real Java applications, arrays or ArrayList are better.

Why:

• better cache locality,
• lower object overhead,
• simpler APIs,
• and better constant factors.

So interview linked lists are often more about algorithmic discipline than container recommendation.

When NOT to use linked-list thinking

Do not prefer linked lists when the problem needs:

• random index access,
• binary search,
• cache-friendly scans on primitives,
• or frequent lookups by key.

In those cases, arrays, hash-based structures, or trees are usually better fits.

Java-specific advice

For stack-like behavior, prefer Deque over the legacy Stack class.

For queue behavior, prefer ArrayDeque when possible.

For interview linked-list problems, however, use an explicit ListNode class because that is what the problem models.

Pair-programming angle

A strong explanation sounds like this:

• “I’ll use a dummy node so deleting the head becomes an ordinary case.”
• “I’ll keep previous, current, and nextNode because reordering the updates can lose the tail.”
• “The invariant is that everything before previous is already correctly reversed.”

That is much stronger than just saying "I know the linked-list trick."

Related LeetCode problems

• LeetCode #206 — Reverse Linked List — three-pointer reversal with invariant discipline.
• LeetCode #21 — Merge Two Sorted Lists — dummy node + comparison walk.
• LeetCode #141 — Linked List Cycle — fast/slow pointer cycle detection.
• LeetCode #19 — Remove Nth Node From End of List — two-pointer gap technique.
• LeetCode #876 — Middle of the Linked List — fast/slow to find midpoint.

---

4. Code Examples

Basic Example

This example builds a small list and traverses it.

public class LinkedListTraversalExample {
    static class ListNode {
        int value;
        ListNode next;

        ListNode(int value) {
            this.value = value;
        }
    }

    public static void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.value + (current.next != null ? " -> " : ""));
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);

        printList(head);
    }
}

Why it matters:

• it shows sequential traversal,
• it shows node wiring,
• and it reinforces that linked lists are walked, not indexed.

Advanced Example

This example reverses a singly linked list iteratively.

public class ReverseLinkedListExample {
    static class ListNode {
        int value;
        ListNode next;

        ListNode(int value) {
            this.value = value;
        }
    }

    public static ListNode reverse(ListNode head) {
        ListNode previous = null;
        ListNode current = head;

        while (current != null) {
            ListNode nextNode = current.next;
            current.next = previous;
            previous = current;
            current = nextNode;
        }

        return previous;
    }
}

Key invariant:

• previous is the reversed prefix,
• current is the next unprocessed node,
• nextNode protects the remainder.

Common Pitfall

This is a classic bug.

public class BrokenReverseExample {
    static class ListNode {
        int value;
        ListNode next;

        ListNode(int value) {
            this.value = value;
        }
    }

    public static ListNode brokenReverse(ListNode head) {
        ListNode previous = null;
        ListNode current = head;

        while (current != null) {
            current.next = previous;
            previous = current;
            current = current.next;
        }

        return previous;
    }
}

Why it fails:

• after current.next = previous, the original next node is gone,
• current = current.next now walks backward,
• and the unreversed suffix is lost.

The fix is to save nextNode before overwriting current.next.

Another practical pattern: removing with a dummy node

public class RemoveValueExample {
    static class ListNode {
        int value;
        ListNode next;

        ListNode(int value) {
            this.value = value;
        }
    }

    public static ListNode removeAll(ListNode head, int target) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode current = dummy;
        while (current.next != null) {
            if (current.next.value == target) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }

        return dummy.next;
    }
}

This is a strong interview example because it removes special-case logic for deleting the head.

---

5. Trade-offs

Aspect	Details
⚡ Performance	Great for local rewiring once you already have the node or previous node; poor for indexing and cache-heavy scans
💾 Memory	Higher overhead than arrays because each node is a separate object and stores references
🔧 Maintainability	Clean when invariants are explicit; fragile when pointer updates are implicit or badly ordered
🔄 Flexibility	Excellent for structural edits such as splice, reverse, split, merge, and partition

Performance nuance

Big-O alone is not enough.

A linked list may offer O(1) insertion after a known node.

But if you first need an O(n) traversal to find that node, the full operation is still effectively linear.

Memory nuance

Each node creates object overhead.

That is one reason linked lists often underperform arrays in real Java systems even when the asymptotic story sounds attractive.

Readability nuance

Linked-list code becomes readable when variable names match the invariant.

Names like previous, current, nextNode, slow, fast, dummy, and tail are not cosmetic.

They are part of the safety mechanism.

---

6. Common Mistakes

1. Losing the rest of the list — The most common bug is overwriting current.next before saving the old next node. Save first, rewire second.
2. Ignoring head edge cases — Deleting or inserting at the front often breaks naive logic. Use a dummy node when mutation starts near the head.
3. Advancing the wrong pointer — In deletion loops, moving current after removal can skip nodes or cause inconsistent behavior.
4. Comparing the wrong thing — Sometimes the problem wants node identity, not just node value. Be clear about whether equality means same reference or same payload.
5. Forgetting null boundaries — fast.next.next is unsafe unless you first prove both fast and fast.next are non-null.
6. Mixing array intuition with list reality — There is no cheap index jump. If your reasoning keeps using “the middle index” without traversal, the model is wrong.
7. Breaking tail invariants — If you maintain a tail pointer, you must update it consistently after append, delete, and merge operations.

Debugging tip

When a linked-list bug appears, draw four things only:

• node values,
• arrows,
• variable names,
• and the next update.

That is usually enough.

---

7. Deep Dive

Why linked lists often lose to arrays in Java

This surprises many people.

Theoretical O(1) insertion sounds powerful.

But in practice:

• arrays are cache-friendly,
• primitive arrays avoid object overhead,
• and CPU-friendly contiguous scans are extremely fast.

A linked list creates many small heap objects.

Following references is much worse for locality.

So the “best asymptotic structure” can still be slower in production.

Why interviewers still love linked lists

Because linked lists expose three valuable skills:

• reference discipline,
• invariant-driven reasoning,
• and edge-case control.

If you can safely reverse, split, merge, and detect cycles, you usually understand state transitions much better.

Dummy nodes are more than a trick

A dummy node is a design pattern for removing special cases.

That is the deeper lesson.

Good engineering often means reshaping the problem so the main loop becomes uniform.

Fast/slow pointer insight

Fast/slow pointer solutions are elegant because they encode structure into motion.

Examples:

• if fast moves twice as quickly, meeting implies a cycle,
• if fast reaches the end, slow approximates the middle,
• if one pointer starts later, relative movement can align distances.

This is algorithmic reasoning, not memorization.

Recursive linked-list solutions

Some problems also have elegant recursive forms.

But recursion adds call-stack space.

That may be fine for clarity.

It may also violate the strongest extra-space target.

In interviews, say that explicitly.

Real-world scenario

Suppose you are pair-programming on a “remove duplicates from sorted list” problem.

A strong approach is not just code.

It is explanation:

• the list is sorted,
• duplicates are adjacent,
• one pass is enough,
• rewiring is local,
• and the main risk is skipping nodes after deletion.

That kind of narration is often what separates a solid candidate from a merely fast coder.

---

8. Interview Questions

Q: Why is a linked list bad for random access? — A: Because nodes are reached by following references sequentially. There is no direct index-to-address jump like in an array, so access by position is O(n).

Q: When is insertion in a linked list really O(1)? — A: When you already have the node before the insertion point, or the exact place to rewire. If you must first traverse to find that position, the overall operation includes that traversal cost.

Q: Why is a dummy node so useful? — A: It removes special handling for the real head. Deleting or inserting at the front becomes structurally identical to the general case.

Q: How does Floyd’s cycle detection work? — A: A slow pointer moves one step and a fast pointer moves two. In a cycle, the fast pointer eventually catches the slow pointer. Without a cycle, the fast pointer reaches null.

Q: Why might ArrayList outperform a linked list in Java even when linked-list insertion looks cheaper on paper? — A: Because arrays and dynamic arrays have much better locality and lower object overhead. Real performance depends on constant factors and memory behavior, not only asymptotic complexity.

---

9. Glossary

Term	Definition
ListNode	A node type used in linked-list problems, typically holding a value and a next reference
dummy node	A synthetic node placed before the head to simplify mutation logic
rewiring	Reassigning references so the structure changes without copying all elements
fast/slow pointers	Two references moving at different speeds to infer structural properties
cycle	A linked-list condition where following next eventually revisits an earlier node
sentinel	A special helper node used to simplify boundaries or represent structure edges

---

10. Cheatsheet

• Use linked-list thinking when the problem is about nodes, not indices.
• Save nextNode before overwriting current.next.
• Use a dummy node when the head may be deleted or replaced.
• slow/fast pointers are the standard tools for middle and cycle problems.
• Access by index is O(n), not O(1).
• Local rewiring can be O(1) when the right node is already known.
• Arrays often beat linked lists in real Java performance because of locality.
• Good linked-list code names variables after invariants.
• If mutation feels branch-heavy, a dummy or tail builder may simplify it.
• In interviews, explain pointer order before you code it.