Linked List Mental Model

A linked list is not a slower array. It is a different storage model: each node owns a value and a reference to the next node. That makes insertion and deletion cheap only when you already have the right node reference. Finding that reference still requires traversal.

The Node Reference Model

Arrays give indexed access. Linked lists give reference-based movement. A list starts at a head node. From there, you can only move through next references until the list ends. This is why random access is O(n), not O(1).

Scenario: LRU Cache Order

An LRU cache must move accessed items to the front and evict the least recently used item from the back. A hash map finds the node by key. A doubly linked list rewires that node in O(1). The linked list alone is not enough; the map supplies the missing lookup.

Same Pattern in Java, Python, and JavaScript

Traversal is the first skill. You start at head, visit current, then move to current.next until the pointer is null.

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

class LinkedListTraversal {
    static int sum(ListNode head) {
        int total = 0;
        for (ListNode current = head; current != null; current = current.next) {
            total += current.value;
        }
        return total;
    }
}

Insertion and Deletion Are Local Only After Lookup

The phrase insertion is O(1) is incomplete. Inserting after a known node is O(1). Finding that node by position or value is O(n). Assessment-grade answers always separate lookup cost from rewiring cost.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Merge two sorted linked lists into one sorted linked list.
• Delete the first node whose value equals target.
• Describe the data structures needed for an LRU cache.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

class ListNode { int value; ListNode next; ListNode(int v) { value = v; } }

class MergeSortedLists {
    static ListNode merge(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (a != null && b != null) {
            if (a.value <= b.value) { tail.next = a; a = a.next; }
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = a != null ? a : b;
        return dummy.next;
    }
}

class ListNode { int value; ListNode next; ListNode(int v) { value = v; } }
class DeleteValue { static ListNode delete(ListNode head, int target) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; while (prev.next != null) { if (prev.next.value == target) { prev.next = prev.next.next; break; } prev = prev.next; } return dummy.next; } }

import java.util.*;

class LruCache<K, V> {
    static class Node<K, V> { K key; V value; Node<K, V> prev, next; }
    private final Map<K, Node<K, V>> byKey = new HashMap<>();
    private Node<K, V> head, tail;

    // get: find byKey.get(key), detach node, move to head.
    // put: update existing or add new head; if over capacity, remove tail.
}

Solved modelWorked Interview Answer

Merge two sorted linked lists into one sorted list. Use a dummy node and a tail pointer. Reuse the smaller current node from either list, then append the remainder.

class ListNode { int value; ListNode next; ListNode(int v) { value = v; } }

class MergeSortedLists {
    static ListNode merge(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (a != null && b != null) {
            if (a.value <= b.value) { tail.next = a; a = a.next; }
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = a != null ? a : b;
        return dummy.next;
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Saying insertion is O(1) without including lookup cost.
• Losing the rest of the list by overwriting next too early.
• Forgetting that head can change.
• Ignoring ownership when mutating shared nodes.
• Using linked lists where indexed access dominates.

Execution guardrailQuick-Start Checklist

• Identify head and tail behavior.
• Separate traversal cost from rewiring cost.
• Save references before mutation.
• Handle empty and single-node lists.
• State pointer overhead and locality trade-offs.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice merge two sorted lists and remove nth node from end.
• Study LRU cache after linked-list mutation is comfortable.
• Compare linked lists with dynamic arrays in language runtimes.