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.
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.
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
A dummy node starts the answer. tail links whichever list has the smaller front node, then moves on. Nodes are relinked, never copied.
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
The last column fills in as you run operations on the bench. A hop is one step along a pointer (cur = cur.next).
| Operation | Cost | Why | Last run on the bench |
|---|---|---|---|
| Access by index | O(n) | Nodes are scattered, so there is no address formula. You start at head and hop node by node. | not run yet |
| Search | O(n) | The same walk from head, comparing each value. | not run yet |
| Insert or remove at the head | O(1) | One or two pointer writes. Nothing else changes. | not run yet |
| Insert or remove at a node you hold | O(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 |
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.
O(n) total. Each node stores its value plus one pointer (next), about 16 bytes here, against 8 bytes per element in an array.
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.
O(n) for n waiting items. Enqueue and dequeue are O(1). Python's deque is a doubly linked list of small blocks.
Reverse and merge only move pointers, so they need O(1) extra space: a few variables like prev, cur and tail.
You are rewiring next pointers, usually with prev, cur and a dummy node.
First in, first out: the item that waited longest goes next.
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?