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 the needed node references, you can splice a node in or out in O(1) by rewiring pointers. In a singly linked list, deletion also needs the previous node; a doubly linked node stores that reference itself. Neither case shifts the remaining elements.

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 a least recently used (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. A dummy or sentinel head is a temporary node placed before the first real element. It lets deletion of the first real node use the same previous-node update as any other deletion.

3. Implementation

The example shows front insertion, deletion of the first matching value, reversal, and cycle detection. reverse changes links in place and returns the new head; assign that return value back to the list's head. has_cycle checks whether following next references can revisit a node.

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.