Linked Lists

Linked Lists

Each node holds a value + pointer(s) to next/previous node. No random access — must traverse.

Why Linked Lists?

• O(1) insert/delete if you already have a reference to the node — arrays must shift elements
• Grow and shrink dynamically with no resizing overhead
• Used to implement: stacks, queues, hash map buckets, LRU caches

LRU Cache (classic linked list application)

Combine a hash map (O(1) lookup) + doubly linked list (O(1) move-to-front):

• Most recently used (MRU) lives at the head
• Least recently used (LRU) lives at the tail — evicted when cache is full
• On access: O(1) lookup via hash map, then O(1) move node to head via prev/next pointers

Complexity

| Operation | Singly | Doubly | |------------------|---------|---------| | Access by index | O(n) | O(n) | | Insert at head | O(1) | O(1) | | Insert at tail | O(1)* | O(1)* | | Delete (known node) | O(1) | O(1) | | Search | O(n) | O(n) |

*With a tail pointer maintained.

Node Reference vs Value Comparison

# Reference comparison — same object in memory (identity)
node_a is node_b       # True only if they ARE the same node

# Value comparison — same data
node_a.value == node_b.value   # True if data matches, even different nodes

For intersection problems, use is (reference) — two lists intersect when their nodes are the same object, not just equal values.

Python Node Template

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None      # singly

class DNode:
    def __init__(self, val):
        self.val = val
        self.next = None      # doubly
        self.prev = None

Fast & Slow Pointer (Floyd's Algorithm)

Time: O(n), Space: O(1) — no extra space needed.

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

def find_cycle_start(head):
    slow = fast = head
    # Phase 1: detect meeting point
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None  # no cycle
    # Phase 2: reset slow to head, both advance at speed 1
    slow = head
    while slow is not fast:
        slow = slow.next
        fast = fast.next
    return slow  # cycle start node

Reverse a Linked List

def reverse(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev   # new head

Find Middle Node

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow  # middle (or right-of-middle for even length)

Remove Duplicates (with buffer)

def remove_dups(head):
    seen = set()
    prev, curr = None, head
    while curr:
        if curr.val in seen:
            prev.next = curr.next  # skip duplicate
        else:
            seen.add(curr.val)
            prev = curr
        curr = curr.next

k-th From End (two-pointer)

def kth_from_end(head, k):
    fast = slow = head
    for _ in range(k):        # advance fast k steps
        fast = fast.next
    while fast:               # move both until fast reaches end
        slow = slow.next
        fast = fast.next
    return slow

Key Interview Tips

• Always handle null/empty list and single node as first cases
• Draw pointer reassignments before coding — it's easy to lose a node
• Fast+slow pointer finds: midpoint, cycle start, nth-from-end — all O(n) time O(1) space
• Use a dummy head node to simplify edge cases at the front of the list
• For intersection: align lengths first, then walk together until node_a is node_b