Linked Lists

What a linked list actually is

A linked list is a chain of nodes, each holding a value and a pointer to the next node. Unlike an array, the nodes are scattered across memory — a doubly-linked list also points back to the previous node.

• Insert/delete at the front: O(1) — just rewire two pointers.
• Insert/delete at the end: O(1) if you keep a tail pointer, otherwise O(n).
• Lookup by index: O(n) — you have to walk the chain.
• Memory: more than an array (every element costs an extra pointer).

In practice, linked lists are rare in everyday code — dynamic arrays (Python list, JS Array, C++ vector) are faster for almost everything because of cache locality. But linked lists show up in interviews because they exercise pointer manipulation, which has no shortcut.

A simple node and traversal

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

# Build: 1 -> 2 -> 3 -> 4
head = Node(1, Node(2, Node(3, Node(4))))

# Walk the list
node = head
while node:
    print(node.val)
    node = node.next

Reversal — the rite of passage

Reversing a linked list in place is the most-asked linked list problem. The idea: walk the list, and at each step, point the current node back at the previous one. You need three pointers: prev, current, next.

def reverse(head):
    prev = None
    while head:
        nxt = head.next   # remember next
        head.next = prev  # rewire
        prev = head       # advance prev
        head = nxt        # advance head
    return prev

# Or, more idiomatically, with parallel assignment:
def reverse_short(head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev

Fast and slow pointers (Floyd's cycle detection)

Maintain two pointers, slow advancing one node per step and fast advancing two. If there's a cycle, fast will eventually lap slow and they'll meet. If not, fast hits the end. This detects cycles in O(n) time and O(1) memory.

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

The same trick with a different setup finds the middle of a list (slow ends in the middle when fast reaches the end), the start of the cycle, and the kth-from-last element.

Dummy nodes

A dummy node is a fake head you put before the real list. It eliminates special cases for inserts/deletes at the front, because the real head is now just "the node after dummy". It's a small habit that prevents bugs.

def remove_value(head, target):
    dummy = Node(0, head)
    prev, curr = dummy, head
    while curr:
        if curr.val == target:
            prev.next = curr.next      # skip
        else:
            prev = curr
        curr = curr.next
    return dummy.next