Linked lists

No. 02 · SVG · Tags on a stringsingly linked · doubly linked · queue (FIFO)

Drag along the chain.

A linked list has no row of slots. It is a bundle of luggage tags tied together with string. Each tag (a node) sits wherever memory was free and carries a value plus the address of the next tag. The list is just its head: to reach anything else you follow the strings, one hop at a time. In exchange, adding or removing a node only reties a string or two.

FIG. 2 · Five tags at scattered memory addresses. Each tag has a value and a small pocket holding the next pointer; the string from that pocket arcs over to the tag it points at, and an empty pocket (∅) means None. In a doubly linked list a second pocket holds the prev pointer, drawn as a teal string running backwards. The red marks what the code is touching right now. Callouts: A value, B next pointer, C address, D head.

Redrawn in order · no node moved in memory, addresses unchanged
node: a value, with its memory address under it pointer pocket; ∅ means None next pointer prev pointer (doubly) head: where the list starts cur: the node the code is on
Length n
Hops
Pointer writes
Memory

Examples

Linked list · LeetCode 206

Walk once with three pointers. At each node, save nxt, point cur.next back at prev, then step both forward. No tag moves; every string is retied the other way.

O(n) timeO(1) spaceone walk through the list; only prev, cur and nxt
def reverse(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next      # save the next node
        cur.next = prev     # flip the pointer
        prev, cur = cur, nxt
    return prev             # new head
Linked list · LeetCode 21

A dummy node starts the answer. tail links whichever list has the smaller front node, then moves on. Nodes are relinked, never copied.

O(n + m) timeO(1) spaceeach node of both lists is linked once; only dummy and tail extra
dummy = tail = ListNode(0)
while list1 and list2:
    if list1.val <= list2.val:
        tail.next, list1 = list1, list1.next
    else:
        tail.next, list2 = list2, list2.next
    tail = tail.next
tail.next = list1 or list2
return dummy.next

Time: what each operation costs

The last column fills in as you run operations on the bench. A hop is one step along a pointer (cur = cur.next).

OperationCostWhyLast run on the bench
Access by indexO(n)Nodes are scattered, so there is no address formula. You start at head and hop node by node.not run yet
Insert or remove at the headO(1)One or two pointer writes. Nothing else changes.not run yet
Insert or remove at a node you holdO(1)Only the neighbours' pointers change. To remove from a singly linked list you also need the node before it, and finding that is O(n) unless the list is doubly linked.not run yet
Enqueue or dequeue (deque)O(1)Head and tail pointers keep both ends one step away.not run yet

Compared with an array

The trade is exact. An array finds any index in O(1) because its slots sit side by side, but inserting in the middle shifts everything after it, O(n). A linked list inserts in O(1) once you hold the node, because nothing shifts, but reaching that node from head is O(n). Each new node also gets its own memory, so a linked list never resizes or copies.

Space: what the nodes cost

Singly linked

O(n) total. Each node stores its value plus one pointer (next), about 16 bytes here, against 8 bytes per element in an array.

Doubly linked

O(n) total, with a second pointer (prev) per node. The extra 8 bytes buy O(1) removal of a node you hold, and walking backwards.

Queue (FIFO)

O(n) for n waiting items. Enqueue and dequeue are O(1). Python's deque is a doubly linked list of small blocks.

Pointer tricks

Reverse and merge only move pointers, so they need O(1) extra space: a few variables like prev, cur and tail.

Trigger words: which one the problem wants

Pointer manipulation

  • linked list
  • reverse
  • merge two lists
  • remove the nth node

You are rewiring next pointers, usually with prev, cur and a dummy node.

Queue (FIFO)

  • first come, first served
  • in order of arrival
  • process level by level

First in, first out: the item that waited longest goes next.

Template

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

def reverse(head):                 # the most common pattern
    prev, cur = None, head
    while cur:
        nxt = cur.next             # save the next node
        cur.next = prev            # flip the pointer
        prev, cur = cur, nxt       # move both forward
    return prev                    # new head

def merge_lists(list1, list2):     # dummy node avoids head special cases
    dummy = tail = ListNode(0)
    while list1 and list2:
        if list1.val <= list2.val:
            tail.next, list1 = list1, list1.next
        else:
            tail.next, list2 = list2, list2.next
        tail = tail.next
    tail.next = list1 or list2
    return dummy.next

from collections import deque
# Queue (FIFO)
q = deque()
q.append(x)      # add to the back (enqueue)
q.popleft()      # remove from the front (dequeue)
q[0]             # peek at the front
if q: ...        # not empty?

# Stack (LIFO)
s = deque()      # or s = []
s.append(x)      # push onto the top
s.pop()          # remove from the top
s[-1]            # peek at the top
if s: ...        # not empty?