Linked lists

Nodes and pointers

A linked list is a chain of nodes. Each node holds a value and a reference, or pointer, to the next node. The first node is the head. The last node's next is None, which marks the end. Unlike an array, the nodes do not sit side by side in memory; each node only knows where the next one is.

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

head = ListNode(1, ListNode(2, ListNode(3)))   # 1 -> 2 -> 3
node = head
while node:
    print(node.val, end=" ")
    node = node.next
# Output: 1 2 3

Singly and doubly linked

In a singly linked list each node points only to the next one, so you can walk forwards only. A doubly linked list also stores prev, a pointer to the node before, so you can walk both ways and unlink a node in O(1) once you hold a reference to it, at the cost of one extra pointer per node. LRU caches (a hash map plus a doubly linked list) and music playlists with "previous" use doubly linked lists. Java's LinkedList is doubly linked, and CPython's deque is a doubly linked list of blocks.

What each operation costs

There is no random access: you cannot jump to the fifth node, you must walk there. In practice linked lists are also slower to scan than arrays, because their nodes are scattered in memory and the processor's cache helps less.

Insert and delete

Insert at the head: make a new node whose next is the old head; it becomes the new head. Delete the head: head = head.next. To insert at position i, walk to the node just before it, prev, and splice: new.next = prev.next, then prev.next = new. The order of those two steps matters: set prev.next first and the rest of the list is lost.

head = ListNode(2, ListNode(3))       # 2 -> 3
head = ListNode(1, head)              # insert at the head: 1 -> 2 -> 3
prev = head.next                      # the node holding 2
prev.next = ListNode(9, prev.next)    # insert after it: 1 -> 2 -> 9 -> 3
head = head.next                      # delete the head: 2 -> 9 -> 3

The dummy node trick

Deleting is awkward when the head itself might be deleted, because then the head changes. A dummy (or sentinel) node placed before the head removes that special case: every real node now has a node before it. Do the work starting from the dummy and return dummy.next at the end.

Reversing a list iteratively

Reversing turns every arrow around. Walk with three pointers: prev (the part already reversed, starting as None), cur (the node being turned) and nxt (saved first so the rest of the list is not lost). O(n) time and O(1) extra space.

def reverse(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next      # 1. save the rest
        cur.next = prev     # 2. turn this arrow around
        prev = cur          # 3. move prev forward
        cur = nxt           # 4. move cur forward
    return prev             # the old tail is the new head

Reversing recursively

Recursively: reverse everything after the head, then hook the head on at the end. The recursion goes n calls deep, so it uses O(n) stack space, and CPython stops at about 1,000 nested calls by default with a RecursionError. Prefer the iterative version for long lists; recursion is covered in depth in Module 5.

def reverse_rec(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_rec(head.next)
    head.next.next = head    # the node after head now points back to it
    head.next = None         # cut the old forward link
    return new_head

Python has no built-in singly linked list, so the tasks define ListNode plus two helpers: build(values) turns a Python list into a linked list, and to_list(head) turns it back, which makes results easy to check.

Common mistakes

• Changing cur.next before saving it, which loses the rest of the list. Fix: nxt = cur.next first.
• Forgetting to return the new head after reversing or deleting the first node. Fix: always return the head, and use the returned value.
• Reading node.next.val when node.next is None (AttributeError: 'NoneType' object has no attribute 'val'). Fix: check node and node.next first.
• In recursive reversal, forgetting head.next = None, which leaves a two-node cycle at the end. Fix: cut the old link.
• Special-casing the head in every function. Fix: use a dummy node.