Linked Lists

1. What It Is and Why It Exists

A linked list stores each element in its own node, and each node holds a pointer to the next node (singly linked) or to both neighbors (doubly linked). Nodes are not contiguous in memory, so there is no address arithmetic — to reach element i you must walk i pointers, making access O(n). In exchange you get the one thing arrays are bad at: given a reference to a node, you can splice a node in or out in O(1) by rewiring two pointers, with no shifting of the rest of the structure.

That trade-off is the entire reason linked lists exist and the entire reason interviewers use them. They are the backing structure when you need cheap insert/delete at arbitrary positions you already hold a handle to: the doubly linked list inside an LRU cache, the chains in a hash table, queue implementations. The "why it works" intuition: a linked list buys O(1) structural edits by giving up O(1) random access — the opposite of an array. Interview problems are mostly pointer manipulation (reverse, detect cycle, find middle, merge) where the skill is not losing a reference and handling the head/tail/empty edges.

2. Operations and Complexity

Space is O(n) plus a pointer per node (more overhead than an array). The operations interviewers probe: deleting a node in a singly linked list requires the previous node (or the copy-next trick), and O(1) tail insertion only holds if you maintain a tail pointer. The dummy/sentinel head node is the expected technique for clean edge handling.

3. Implementation

Singly linked list with the interview-critical operations and the dummy-head pattern:

Copy
class ListNode:
    def __init__(self, val=0, nxt=None):
        self.val = val
        self.next = nxt

class LinkedList:
    def __init__(self):
        self.head = None

    def push_front(self, val):           # O(1): new node points to old head
        self.head = ListNode(val, self.head)

    def delete_value(self, target):      # O(n) to find, O(1) to unlink
        dummy = ListNode(0, self.head)   # sentinel: removes the "delete head" special case
        prev, cur = dummy, self.head
        while cur:
            if cur.val == target:
                prev.next = cur.next     # O(1) splice-out; needs prev (singly linked)
                break
            prev, cur = cur, cur.next
        self.head = dummy.next

# The two canonical interview routines:

def reverse(head):                       # O(n) time, O(1) space
    prev = None
    while head:
        nxt = head.next                  # save next BEFORE rewiring (or you lose the list)
        head.next = prev                 # flip the pointer
        prev, head = head, nxt
    return prev                          # new head

def has_cycle(head):                     # Floyd: O(n) time, O(1) space
    slow = fast = head
    while fast and fast.next:
        slow = slow.next                 # +1
        fast = fast.next.next            # +2; if there's a loop they meet
        if slow is fast:
            return True
    return False

In a real interview you implement the node class yourself — there is no idiomatic stdlib singly linked list, and that is the point of these problems. When you actually need a doubly linked, O(1)-both-ends sequence (e.g. a deque), reach for collections.deque.

4. When to Reach for It

• The problem hands you a linked list (ListNode) — reverse, merge, reorder, detect/remove cycle, find middle, partition.
• You need O(1) insert/delete at positions you already hold a pointer to and do not need random access (e.g., the recency list inside an LRU cache → doubly linked list + hash map).
• You need O(1) splicing of sublists without shifting elements.
• Reach for collections.deque instead when you just need a fast double-ended queue — don't hand-roll one.

5. Common Pitfalls

• Losing the rest of the list: rewiring head.next before saving head.next orphans everything downstream. Always save nxt first.
• Null/empty edges: empty list (head is None), single node, operating on the head — use a dummy/sentinel head to kill the special cases.
• Fast-pointer cycle bug: loop condition must be while fast and fast.next or fast.next.next raises on even-length lists.
• Singly-linked delete without prev: you cannot unlink a node knowing only itself unless you copy the next node's value over it (and that fails for the tail).
• Forgetting to update the tail pointer after inserting/deleting at the end → later O(1) tail inserts corrupt the list.
• Off-by-one finding the middle: slow/fast start position determines whether you get the left-middle or right-middle on even length — confirm which the problem wants.

6. Interview Cheat Sheet

• "Linked list trades O(n) random access for O(1) insert/delete at a known node — the inverse of an array."
• "I use a dummy/sentinel head so deleting the head isn't a special case."
• "Reverse is iterative pointer flipping in O(n) time, O(1) space; cycle detection is Floyd's fast/slow in O(n)/O(1)."
• "Deleting a node in a singly linked list needs the previous node, so I track prev while traversing."

Follow-ups:

• "Singly vs doubly linked?" — Doubly adds a prev pointer: O(1) delete given only the node and O(1) backward traversal, at the cost of an extra pointer per node. LRU cache needs doubly linked.
• "Find the middle in one pass?" — Fast/slow pointers: when fast reaches the end, slow is at the middle. O(n) time, O(1) space.
• "Reverse in groups of k?" — Reverse k nodes at a time, reconnect the group's tail to the next reversed group; use a dummy head to anchor the result.