Linked Lists, Stacks, and Queues Questions
Pointer-based linear structures and the classic problems built on them: singly, doubly and circular linked lists (reversal whole, partial and in groups of k, cycle detection and cycle start with fast/slow pointers, intersection, middle and nth-from-end, merging two or k sorted lists, sorting a list, reordering, palindrome check, rotation, partitioning, duplicate removal, deep copy with random pointers, flattening child lists, sentinel nodes), implementing lists in C, C++ and Rust with attention to pointer handling, ownership and cleanup, array versus linked-list trade-offs including cache locality, stacks, queues and deques (array, linked and circular-buffer implementations, ring-buffer full versus empty, queue from two stacks, min stack, round-robin scheduling), monotonic stacks and queues (next greater element, largest rectangle in a histogram, sliding-window maximum), stack-based expression and bracket evaluation (balanced brackets, Reverse Polish Notation, infix to postfix, calculators), and structure-level builds such as an LRU cache from a hash map plus doubly linked list, undo/redo history, and variants like persistent or unrolled lists. Foundational for coding interviews and for understanding how higher-level structures are built. Concurrent and lock-free queues, memory allocators, general graph traversal, heaps and cache-eviction system design are covered elsewhere.
A ring buffer holds a fixed-capacity queue. How do you tell a full buffer from an empty one when head equals tail? Describe at least two ways to resolve this and the trade-offs, and sketch enqueue and dequeue.
Sample Answer
The idea in plain words
A ring buffer (circular buffer) is a fixed-size array used as a queue. Two indices move around it: head is the slot of the next item to read, tail is the slot of the next item to write. Both wrap from the last slot back to slot 0 using % capacity.
The trap: fix head at some slot and add items one by one. With 0 items tail sits on the same slot as head; each item moves tail one slot on; after N items tail has gone all the way round and sits on that same slot again. So the fill levels 0 and N put head and tail in identical positions: empty and full both have head == tail. With head fixed, tail can take only N positions around the ring but the buffer has N + 1 possible fill levels (0 to N), and the listing below prints the 4-slot case. Any ring buffer needs one extra piece of information to separate them.
The bug, run
This version treats head == tail as empty and never checks for full. With capacity 4, after four writes the tail has wrapped back to slot 0 and equals head:
import random
from collections import deque
class BrokenRing:
"""Empty is 'head == tail', and nothing stops a write when the ring is full."""
def __init__(self, capacity):
self.buf = [None] * capacity
self.head = self.tail = 0 # head: next read, tail: next write
def is_empty(self):
return self.head == self.tail
def enqueue(self, x):
self.buf[self.tail] = x
self.tail = (self.tail + 1) % len(self.buf)
def dequeue(self):
if self.is_empty():
raise IndexError("empty")
x = self.buf[self.head]
self.head = (self.head + 1) % len(self.buf)
return x
class SpareSlotRing:
"""Way 1: capacity+1 slots, one always left unused. Full means tail+1 == head."""
def __init__(self, capacity):
self.buf = [None] * (capacity + 1)
self.head = self.tail = 0
def is_empty(self):
return self.head == self.tail
def is_full(self):
return (self.tail + 1) % len(self.buf) == self.head
def enqueue(self, x):
if self.is_full():
return False
self.buf[self.tail] = x
self.tail = (self.tail + 1) % len(self.buf)
return True
def dequeue(self):
if self.is_empty():
raise IndexError("empty")
x = self.buf[self.head]
self.head = (self.head + 1) % len(self.buf)
return x
class CountRing:
"""Way 2: store the number of items. All slots usable."""
def __init__(self, capacity):
self.buf = [None] * capacity
self.head = self.count = 0
def is_empty(self):
return self.count == 0
def is_full(self):
return self.count == len(self.buf)
def enqueue(self, x):
if self.is_full():
return False
self.buf[(self.head + self.count) % len(self.buf)] = x
self.count += 1
return True
def dequeue(self):
if self.is_empty():
raise IndexError("empty")
x = self.buf[self.head]
self.head = (self.head + 1) % len(self.buf)
self.count -= 1
return x
class FreeRunningRing:
"""Way 3: head and tail only ever increase; the slot is index % capacity.
tail - head is the number of items, so empty is 0 and full is capacity."""
def __init__(self, capacity):
self.buf = [None] * capacity
self.head = self.tail = 0
def is_empty(self):
return self.tail == self.head
def is_full(self):
return self.tail - self.head == len(self.buf)
def enqueue(self, x):
if self.is_full():
return False
self.buf[self.tail % len(self.buf)] = x
self.tail += 1
return True
def dequeue(self):
if self.is_empty():
raise IndexError("empty")
x = self.buf[self.head % len(self.buf)]
self.head += 1
return x
class FlagRing:
"""Way 4: one boolean remembers whether the last operation was a write."""
def __init__(self, capacity):
self.buf = [None] * capacity
self.head = self.tail = 0
self.last_was_write = False
def is_empty(self):
return self.head == self.tail and not self.last_was_write
def is_full(self):
return self.head == self.tail and self.last_was_write
def enqueue(self, x):
if self.is_full():
return False
self.buf[self.tail] = x
self.tail = (self.tail + 1) % len(self.buf)
self.last_was_write = True
return True
def dequeue(self):
if self.is_empty():
raise IndexError("empty")
x = self.buf[self.head]
self.head = (self.head + 1) % len(self.buf)
self.last_was_write = False
return x
ring = BrokenRing(4)
print("BrokenRing, capacity 4")
for x in "abcd":
ring.enqueue(x)
print(f" enqueue {x}: head={ring.head} tail={ring.tail} is_empty={ring.is_empty()}")
try:
ring.dequeue()
except IndexError as e:
print(" 4 items stored, but dequeue raises IndexError:", e)
ring.enqueue("e")
print(" a fifth enqueue overwrites slot 0:", ring.buf)
print("Same 4 enqueues on each fix (capacity 4)")
for cls in (SpareSlotRing, CountRing, FreeRunningRing, FlagRing):
r = cls(4)
accepted = [r.enqueue(x) for x in "abcde"]
state = vars(r)
print(f" {cls.__name__:17} accepted={accepted} is_full={r.is_full()} is_empty={r.is_empty()}"
f" head={r.head} " + (f"tail={r.tail}" if "tail" in state else f"count={r.count}"))
random.seed(45)
for cls in (SpareSlotRing, CountRing, FreeRunningRing, FlagRing):
for _ in range(300):
cap = random.randint(1, 6)
r, ref = cls(cap), deque()
for _ in range(60):
if random.random() < 0.55:
ok = r.enqueue(len(ref))
assert ok == (len(ref) < cap)
if ok:
ref.append(len(ref))
elif ref:
assert r.dequeue() == ref.popleft()
else:
assert r.is_empty()
assert r.is_empty() == (len(ref) == 0) and r.is_full() == (len(ref) == cap)
print("four fixed rings agree with a deque (bounded at capacity) on 1200 random runs")
print("Why head and tail alone cannot separate empty from full (4 slots, head at slot 1)")
for level in range(5):
print(f" {level} items stored: head=1 tail={(1 + level) % 4}")
print("Both sides writing one shared count (producer adds 1, consumer removes 1, count starts at 2)")
count = 2
producer_read = count
consumer_read = count
count = producer_read + 1
print(" producer wrote", count)
count = consumer_read - 1
print(" consumer wrote", count, "but 2 items are stored")
print("Slot used by index 253..258 when indices wrap at 256 (an 8-bit unsigned index)")
for n in (4, 3):
print(f" n={n}: {[(i & 0xFF) % n for i in range(253, 259)]}")
The program printed:
BrokenRing, capacity 4
enqueue a: head=0 tail=1 is_empty=False
enqueue b: head=0 tail=2 is_empty=False
enqueue c: head=0 tail=3 is_empty=False
enqueue d: head=0 tail=0 is_empty=True
4 items stored, but dequeue raises IndexError: empty
a fifth enqueue overwrites slot 0: ['e', 'b', 'c', 'd']
Same 4 enqueues on each fix (capacity 4)
SpareSlotRing accepted=[True, True, True, True, False] is_full=True is_empty=False head=0 tail=4
CountRing accepted=[True, True, True, True, False] is_full=True is_empty=False head=0 count=4
FreeRunningRing accepted=[True, True, True, True, False] is_full=True is_empty=False head=0 tail=4
FlagRing accepted=[True, True, True, True, False] is_full=True is_empty=False head=0 tail=0
four fixed rings agree with a deque (bounded at capacity) on 1200 random runs
Why head and tail alone cannot separate empty from full (4 slots, head at slot 1)
0 items stored: head=1 tail=1
1 items stored: head=1 tail=2
2 items stored: head=1 tail=3
3 items stored: head=1 tail=0
4 items stored: head=1 tail=1
Both sides writing one shared count (producer adds 1, consumer removes 1, count starts at 2)
producer wrote 3
consumer wrote 1 but 2 items are stored
Slot used by index 253..258 when indices wrap at 256 (an 8-bit unsigned index)
n=4: [1, 2, 3, 0, 1, 2]
n=3: [1, 2, 0, 0, 1, 2]
After the fourth enqueue, four items are stored but is_empty() is True, and dequeue raises IndexError. The four items are lost to every caller. The fifth enqueue the program then makes overwrites slot 0 silently (buf now starts with 'e' instead of 'a'), because nothing checks for full.
The lines after the four fixed rings read as follows. With head at slot 1 and a 4-slot ring, 0 items and 4 items both print tail=1, which is the ambiguity every way in the table below has to remove. In the shared-count lines, the producer and the consumer each read the count (2) before either writes; the producer writes 3, the consumer then writes 1, and the real number of stored items (2) is lost. That is what happens when both sides write the same field: each write is based on a value that the other side has already changed. In the last lines, an 8-bit unsigned index counts up to 255 and wraps to 0. With n = 4 the slots run 1, 2, 3, 0, 1, 2 without a gap. With n = 3 the slot sequence is 1, 2, 0, 0, 1, 2: slot 0 is used twice in a row because 256 is not a multiple of 3.
Four ways to tell full from empty
A producer is the code that writes (enqueues) items and a consumer is the code that reads (dequeues) them. They may be two threads or an interrupt handler (a routine the hardware runs the instant a device signals) and the main loop. A lock lets only one of them run a guarded piece of code at a time. An atomic operation is one the hardware performs as a single indivisible step, so no other code can see it half done.
| Way | What it adds | Usable slots | Trade-off |
|---|---|---|---|
| Spare slot | Allocate capacity + 1 slots, never fill the last one | capacity | Full is (tail + 1) % n == head. One wasted slot. Producer writes only tail, consumer writes only head, so neither can overwrite the other's update |
| Count | A count field | all n | Simple. count is changed by both sides, so a producer and a consumer running concurrently need a lock or an atomic (the shared-count lines of the output show the lost update without one) |
| Free-running indices | head and tail only ever increase; slot is index % n | all n | tail - head is the item count, so empty is 0 and full is n. Each index has one writer. In C with unsigned wraparound (the index goes from its maximum back to 0), n should be a power of two |
| Last-operation flag | One boolean: was the last operation a write? | all n | When head == tail, full if the last operation was a write, empty if it was a read. Both sides write the flag |
All four are implemented in the listing above (SpareSlotRing, CountRing, FreeRunningRing, FlagRing); each class's enqueue and dequeue is the sketch asked for. The free-running version needs the power-of-two rule in a fixed-width language: when an unsigned 32-bit index wraps from 4294967295 to 0, index % n stays continuous only if n divides 2^32, which holds for powers of two and fails for other sizes. The 8-bit demonstration in the listing shows the same thing at a size you can read: 256 is a multiple of 4 but not of 3.
Recommendation: use the count field when one thread owns the buffer, because it is the easiest to get right. Use the spare slot (or free-running indices with a power-of-two size) when a producer and a consumer, such as an interrupt handler and the main loop, share the buffer, because each side then writes only its own index (this also needs the correct memory-ordering guarantees on the target: the rules about when one core's writes become visible to another, so the consumer never sees the new tail before the item itself, and these depend on the platform). What would change it: a tight memory budget favours count or free-running over the spare slot.
What the fixed rings print
The middle of the output shows each fixed class receiving the same five enqueues on capacity 4. The first four are accepted, the fifth is rejected, is_full() is True and is_empty() is False. The count version ends with count=4. The flag version ends with head=0 tail=0, the same positions as an empty ring, and only the flag (last operation was a write) says full. The spare-slot version has 5 slots, so tail=4 is a different position from head=0. In the free-running version tail - head is 4 - 0 = 4, which equals the capacity.
Complexity
enqueue, dequeue, is_empty, is_full are O(1) time. Space is O(capacity). No loops, no recursion. The check line of the output records all four fixed classes compared with a bounded collections.deque on 1200 random runs.
Edge cases and common mistakes
- Critical section (a stretch of code that must not be interleaved with the other side's): any read-modify-write on a field both sides change, such as
count, needs one. - Wrapping: compute
(index + 1) % nafter every move, not only on enqueue. - Allocating n slots and using the spare-slot rule, which then holds only n - 1 items. Allocate n + 1.
- Capacity 1 with the spare slot: two slots, and the full test
(tail + 1) % 2 == headstill works. - Skipping the empty check in
dequeue. In the count version it returns a stale slot and drivescountto -1, after whichis_empty()is false. - Using separate
is_fulllogic inenqueueand in a publicis_full, which then disagree. - In C, using a signed index and
%on a negative number. A signed remainder can be negative in C, so keep indices unsigned.
Follow-ups
Overwrite the oldest item on full instead of rejecting. Read several items at once across the wrap point (two contiguous segments). Resize the ring while it holds data (copy in logical order, reset head to 0).
Running the code
# save the listing above as ring_full_empty.py (Python 3.12, standard library only)
python ring_full_empty.py
Implement a fixed-capacity queue on an array with enqueue, dequeue, peek, is_empty and is_full, using wrap-around indices. Walk through a sequence of operations that wraps past the end of the array.
Sample Answer
The idea in plain words
A fixed-size array is cheap and needs no allocation after creation, but a naive queue on it has a flaw: if dequeue shifts every remaining item one slot left, each dequeue costs O(n). A circular buffer (also called a ring buffer) avoids the shifting. Keep an index head for the oldest item. Dequeue just moves head forward by one. Enqueue writes at the first free slot, which is head + size. When an index would run past the last slot, wrap around to slot 0 using the remainder operator %: (index + 1) % capacity. The array is treated as a circle, so the freed slots at the front get reused.
The design choice that matters is how to tell empty from full. If you only store head and tail, both situations look like head == tail. The simplest fix, used below, is to store a size counter: empty is size == 0, full is size == capacity. The alternative is to leave one slot permanently unused, which costs one slot but needs no counter.
Approach, step by step
- State: an array
itemsof fixed length,head(index of the oldest item),size(how many items are stored). enqueue(v): if full, refuse (here: raiseOverflowError; in embedded code a returnedfalseis the usual choice). Otherwise write at(head + size) % capacityand increasesize.dequeue(): if empty, refuse. Otherwise readitems[head], clear the slot, sethead = (head + 1) % capacity, decreasesize.peek(): returnitems[head]without changing anything; refuse if empty.is_empty()andis_full()comparesizewith 0 and with the capacity.
The tail is never stored. It is always computed as (head + size) % capacity, which removes one value that could drift out of sync.
The code
import random
from collections import deque
class CircularQueue:
def __init__(self, capacity):
if capacity < 1:
raise ValueError("capacity must be at least 1")
self.items = [None] * capacity
self.head = 0 # index of the oldest item (next to leave)
self.size = 0 # number of items stored
def is_empty(self):
return self.size == 0
def is_full(self):
return self.size == len(self.items)
def enqueue(self, value):
if self.is_full():
raise OverflowError("queue is full")
tail = (self.head + self.size) % len(self.items) # first free slot
self.items[tail] = value
self.size += 1
def dequeue(self):
if self.is_empty():
raise IndexError("queue is empty")
value = self.items[self.head]
self.items[self.head] = None # drop the reference
self.head = (self.head + 1) % len(self.items) # wrap past the end
self.size -= 1
return value
def peek(self):
if self.is_empty():
raise IndexError("queue is empty")
return self.items[self.head]
def show(label, q, result=""):
tail = (q.head + q.size) % len(q.items)
print(f"{label:<13}{str(q.items):<27}head={q.head} tail={tail} size={q.size} {result}")
def walkthrough():
q = CircularQueue(4)
show("start", q)
for v in (10, 20, 30, 40):
q.enqueue(v); show(f"enqueue({v})", q)
try:
q.enqueue(50)
except OverflowError as e:
show("enqueue(50)", q, f"-> {e}")
show("dequeue()", q, f"-> {q.dequeue()}")
show("dequeue()", q, f"-> {q.dequeue()}")
q.enqueue(50); show("enqueue(50)", q) # lands in slot 0
q.enqueue(60); show("enqueue(60)", q) # lands in slot 1, queue is full again
show("peek()", q, f"-> {q.peek()}")
out = []
while not q.is_empty():
out.append(q.dequeue())
show("drain", q, f"-> {out}")
try:
q.dequeue()
except IndexError as e:
show("dequeue()", q, f"-> {e}")
def random_check():
random.seed(3)
for _ in range(500):
cap = random.randint(1, 6)
q, ref = CircularQueue(cap), deque()
for _ in range(80):
if random.random() < 0.5:
if len(ref) == cap:
assert q.is_full()
try:
q.enqueue(0); assert False
except OverflowError:
pass
else:
v = random.randint(0, 99)
q.enqueue(v); ref.append(v)
elif ref:
assert q.peek() == ref[0] and q.dequeue() == ref.popleft()
else:
assert q.is_empty()
assert q.size == len(ref)
print("500 random runs with capacities 1 to 6 match collections.deque")
if __name__ == "__main__":
walkthrough()
random_check()
Run, it prints:
start [None, None, None, None] head=0 tail=0 size=0
enqueue(10) [10, None, None, None] head=0 tail=1 size=1
enqueue(20) [10, 20, None, None] head=0 tail=2 size=2
enqueue(30) [10, 20, 30, None] head=0 tail=3 size=3
enqueue(40) [10, 20, 30, 40] head=0 tail=0 size=4
enqueue(50) [10, 20, 30, 40] head=0 tail=0 size=4 -> queue is full
dequeue() [None, 20, 30, 40] head=1 tail=0 size=3 -> 10
dequeue() [None, None, 30, 40] head=2 tail=0 size=2 -> 20
enqueue(50) [50, None, 30, 40] head=2 tail=1 size=3
enqueue(60) [50, 60, 30, 40] head=2 tail=2 size=4
peek() [50, 60, 30, 40] head=2 tail=2 size=4 -> 30
drain [None, None, None, None] head=2 tail=2 size=0 -> [30, 40, 50, 60]
dequeue() [None, None, None, None] head=2 tail=2 size=0 -> queue is empty
500 random runs with capacities 1 to 6 match collections.deque
Worked trace of a wrap-around
Capacity 4. tail in the output is the slot the next enqueue will use.
- Four enqueues fill slots 0 to 3. The tail has wrapped back to 0 and
size=4, so the queue is full. The extraenqueue(50)is refused and nothing changes. - Two dequeues return 10 and 20.
headmoves to 2 and slots 0 and 1 are free again. enqueue(50)goes to slot(2 + 2) % 4 = 0, andenqueue(60)goes to slot(2 + 3) % 4 = 1. This is the wrap past the end of the array: the logical order is 30, 40, 50, 60, which sits in slots 2, 3, 0, 1.peek()returns 30 (slot 2), the oldest item. Draining returns 30, 40, 50, 60 in arrival order. After the drainheadis 2 again withsize=0: the position of an empty queue does not matter, onlysizedoes.- A dequeue on the empty queue is refused.
Leaving one slot unused instead of counting
Without a size counter, head == tail has to mean exactly one thing. Make it mean empty, and never let the queue fill every slot: with N slots it holds at most N - 1 items, and it counts as full when advancing tail by one would land on head, that is (tail + 1) % N == head. The reason is in the trace: with 4 slots and 3 items, a fourth write would push tail back to slot 0, the same slot as head, and a full queue would then look exactly like an empty one. Giving up one slot keeps the two states apart.
class OneSlotQueue:
"""Ring buffer that keeps one slot unused, so head == tail can only mean empty."""
def __init__(self, slots):
if slots < 2:
raise ValueError("need at least 2 slots")
self.items = [None] * slots
self.head = 0 # slot of the oldest item
self.tail = 0 # slot where the next item will be written
def is_empty(self):
return self.head == self.tail
def is_full(self):
return (self.tail + 1) % len(self.items) == self.head
def enqueue(self, value):
if self.is_full():
raise OverflowError("queue is full")
self.items[self.tail] = value
self.tail = (self.tail + 1) % len(self.items)
def dequeue(self):
if self.is_empty():
raise IndexError("queue is empty")
value, self.items[self.head] = self.items[self.head], None
self.head = (self.head + 1) % len(self.items)
return value
def show(label, q, note=""):
print(f"{label:<12}{str(q.items):<28}head={q.head} tail={q.tail} "
f"empty={q.is_empty()} full={q.is_full()} {note}")
q = OneSlotQueue(4) # 4 slots, at most 3 items
show("start", q)
for v in (10, 20, 30):
q.enqueue(v)
show(f"enqueue({v})", q)
print("a 4th item would move tail to", (q.tail + 1) % 4, "which equals head", q.head, "so it would look empty")
try:
q.enqueue(40)
except OverflowError as e:
print("enqueue(40) ->", e)
print("dequeue() ->", q.dequeue()); show("", q)
q.enqueue(40); show("enqueue(40)", q, "<- tail wrapped to slot 0")
print("drain ->", [q.dequeue() for _ in range(3)]); show("", q)
try:
OneSlotQueue(1)
except ValueError as e:
print("OneSlotQueue(1) ->", e)
Run, it prints:
start [None, None, None, None] head=0 tail=0 empty=True full=False
enqueue(10) [10, None, None, None] head=0 tail=1 empty=False full=False
enqueue(20) [10, 20, None, None] head=0 tail=2 empty=False full=False
enqueue(30) [10, 20, 30, None] head=0 tail=3 empty=False full=True
a 4th item would move tail to 0 which equals head 0 so it would look empty
enqueue(40) -> queue is full
dequeue() -> 10
[None, 20, 30, None] head=1 tail=3 empty=False full=False
enqueue(40) [None, 20, 30, 40] head=1 tail=0 empty=False full=True <- tail wrapped to slot 0
drain -> [20, 30, 40]
[None, None, None, None] head=0 tail=0 empty=True full=False
OneSlotQueue(1) -> need at least 2 slots
Reading the output: tail is the slot the next write uses. After the third enqueue the queue is full while one slot is still empty, which is the price of this design. After dequeue() returns 10, head moves to 1 and enqueue(40) writes into slot 0, so tail wraps to 0 and the queue is full again with head=1. The head == tail state occurs only in the first and last rows, where the queue is empty.
Complexity
Every operation is O(1) time: a few comparisons, one index calculation and one array access. Space is O(capacity), fixed at construction, with O(1) extra for head and size. Nothing allocates during enqueue or dequeue, which is why this shape is common in embedded code, device drivers and audio or network buffers.
Edge cases and common mistakes
- Capacity 1:
headstays 0,(0 + 1) % 1 == 0, and the queue alternates between empty and full. The random check includes capacity 1. - Empty versus full ambiguity when only two indices are kept. Either keep
size, or keep one slot unused and call the queue full when(tail + 1) % capacity == head, as the one-slot version above does. - Forgetting the modulo on
headindequeue, which runs off the end of the array. - Using
head + sizewithout the modulo when computing the write slot. - Leaving old references in dequeued slots. In Python or Java this keeps objects alive longer than needed, which is why
dequeueclears the slot. - Computing
sizeastail - headwithout handling the wrapped case (tail smaller than head gives a negative number).
Running the code
python circular_queue.py
Python 3.12, standard library only.
You need to keep only the last k records of a very large stream, with O(1) insertion, O(1) removal of the oldest record, and occasional random reads within the window. Compare a circular linked list with an array ring buffer.
Sample Answer
Recommendation
Use the array ring buffer. Both structures give O(1) insertion and O(1) removal of the oldest record, so the deciding requirement is "occasional random reads within the window". An array reaches any position in one step; a circular linked list must walk pointer by pointer. The only reasons to pick the linked list are listed at the end.
Terms: a ring buffer is a fixed array used as a circle, with an index that wraps from the end back to 0. A circular linked list is a chain of nodes whose last node points back to the first. "Window" is the last k records.
How each one works
Array ring buffer. An array of k cells and one index, write, that says where the next record goes. Adding a record writes slots[write] and moves write forward modulo k. Once the array is full, slots[write] holds the oldest record, so the write itself evicts it. The record that is age steps old (0 = newest) is at slots[(write - 1 - age) % k]: one arithmetic step and one memory read. The newest record is at write - 1 because write is where the next one goes. Subtracting age walks back from there, and % k wraps a negative result to the other end of the array: Python's % with a positive k never gives a negative number, so -1 % 5 is 4. (In C and Java, % of a negative number is negative, so add k before taking the remainder.) The first lines of the output work this through for k = 5.
Circular linked list. k nodes linked in a circle, with one pointer, oldest, to the node that will be overwritten next. Adding a record writes into that node and advances the pointer by one hop. This is also O(1) and, because the nodes are allocated once up front, allocates nothing on the hot path (the code that runs on every insert). But the record that is age steps old can only be reached by following next pointers from oldest.
Singly linked circular lists cannot walk backwards, so the walk length for a random age is on average about k/2 hops in the code below: the ages are spread evenly, so the distances k - 1 - age run from 0 up to k - 1 and average (k - 1) / 2. A doubly linked list (each node also has a prev pointer) could start from whichever end is closer: the newest record is one step backwards from oldest, so the walk is min(k - 1 - age, age + 1). That distance never exceeds about k/2 and averages about k/4, still O(k). The exact average lines in the output compute both averages over every age for k = 100,000.
Code and measurements
The driver first works the age formula through for k = 5. It then builds both windows with k = 100,000 records, fills them, checks that 200 random reads return the same records, and counts hops and stored fields. A field here is one stored reference: a cell of the array, or the record or next attribute of a node. Counting fields gives numbers that do not depend on the Python build or the CPU.
import random
class Slot:
__slots__ = ("record", "next") # a node has exactly these two fields and no per-object dictionary
class CircularListWindow:
"""k preallocated nodes linked in a circle; `oldest` is both the next to overwrite and the eviction point."""
def __init__(self, k):
self.k, self.hops = k, 0
nodes = [Slot() for _ in range(k)]
for i, node in enumerate(nodes):
node.record, node.next = None, nodes[(i + 1) % k]
self.oldest = nodes[0]
self.size = 0
def add(self, record):
self.oldest.record = record
self.oldest = self.oldest.next
self.size = min(self.size + 1, self.k)
def get(self, age):
"""The age-th newest record (0 = newest): walk from `oldest`, which costs `hops`."""
node = self.oldest
for _ in range(self.k - 1 - age):
node = node.next
self.hops += 1
return node.record
class ArrayWindow:
def __init__(self, k):
self.k, self.slots, self.write = k, [None] * k, 0
self.size = 0
def add(self, record):
self.slots[self.write] = record
self.write = (self.write + 1) % self.k
self.size = min(self.size + 1, self.k)
def get(self, age):
return self.slots[(self.write - 1 - age) % self.k]
def filled(factory, k, records):
window = factory(k)
for r in records:
window.add(r)
return window
def count_nodes(window):
"""Walk once around the circle and count the nodes."""
node, count = window.oldest.next, 1
while node is not window.oldest:
node, count = node.next, count + 1
return count
def age_demo():
ring = filled(ArrayWindow, 5, range(1, 8)) # records 1..7 into 5 cells: 6 and 7 overwrote 1 and 2
print(f"k=5, records 1..7 added: slots={ring.slots} write={ring.write}")
for age in range(5):
raw = ring.write - 1 - age
index = raw % 5
print(f"age {age}: write - 1 - age = {raw}, {raw} % 5 = {index} -> record {ring.slots[index]}")
if __name__ == "__main__":
age_demo()
k = 100_000
singly = sum(k - 1 - age for age in range(k)) / k
doubly = sum(min(k - 1 - age, age + 1) for age in range(k)) / k
print(f"exact average hops over every age, k={k}: singly linked {singly:,.1f}, doubly linked {doubly:,.1f}")
records = [object() for _ in range(k)]
ring = filled(ArrayWindow, k, records)
chain = filled(CircularListWindow, k, records)
print(f"fields per record: array ring 1, circular list {len(Slot.__slots__)}; nodes in the circle: {count_nodes(chain):,}")
rng = random.Random(5)
ages = [rng.randrange(k) for _ in range(200)]
for age in ages:
assert ring.get(age) is chain.get(age) is records[k - 1 - age]
print(f"200 random reads: array 1 index step each, circular list {chain.hops / 200:,.0f} pointer hops each on average")
Output:
k=5, records 1..7 added: slots=[6, 7, 3, 4, 5] write=2
age 0: write - 1 - age = 1, 1 % 5 = 1 -> record 7
age 1: write - 1 - age = 0, 0 % 5 = 0 -> record 6
age 2: write - 1 - age = -1, -1 % 5 = 4 -> record 5
age 3: write - 1 - age = -2, -2 % 5 = 3 -> record 4
age 4: write - 1 - age = -3, -3 % 5 = 2 -> record 3
exact average hops over every age, k=100000: singly linked 49,999.5, doubly linked 25,000.0
fields per record: array ring 1, circular list 2; nodes in the circle: 100,000
200 random reads: array 1 index step each, circular list 52,790 pointer hops each on average
The costs line up with the structure. The array stores one field per record, in one block. The circular list stores a node per record, each node holds two fields (the record and next) and is a separate object, so the container holds twice the fields and 100,000 separate objects. A random read costs one index step in the array and about 52,790 pointer hops in the list. That is a little above the exact average of 49,999.5 only because the 200 ages are a random sample of the 100,000 possible ones; the doubly linked average of 25,000.0 is the k/4 figure.
Comparison
| array ring buffer | circular linked list | |
|---|---|---|
| add + evict oldest | O(1) | O(1) |
| random read inside the window | O(1) | O(k) |
| stored fields per record (container only) | 1 | 2, in a separate object |
| CPU cache behaviour | cells are contiguous (side by side in one block), so a read also brings its neighbours into the CPU's fast cache | nodes are scattered, so each hop can need a new block of memory |
| window size k changes at runtime | resize means copying | add or remove nodes in place |
| remove a record from the middle | O(k) shifting | O(1) once you hold the node, if the list is doubly linked (a singly linked list also needs the previous node) |
On a 64-bit platform a pointer is 8 bytes, so these counts mean about 8 bytes per record for the ring and at least 16 for the list, before the allocator's own bookkeeping for each separate node. In CPython a node is a full object with a header, so the real figure is larger still; in a compiled language the direction is the same with different byte counts.
What would change the choice
- The window size k changes often, or you must remove records from the middle (for example expire by timestamp rather than by count) and you keep a handle to each node (a reference you saved to the node, for example in a dictionary from record id to node): choose a doubly linked list, which can unlink a node it holds without searching for the node before it.
- Records have very different sizes and live inline: a ring buffer of raw bytes in which each record is stored as its length followed by its contents, with the start positions (offsets) of the records kept alongside, or nodes. A ring of references to separately allocated records still works.
- Reads are never random (only the oldest or newest): the two are equal on speed and the array is still smaller.
Edge cases and common mistakes
- Before the window is full, the live part is only the first
sizecells; usesize, not k, when choosing random positions. - Saying "linked list insertion is O(1)" as if that settled it: reads are part of the requirement.
- Allocating a node per record in the linked version: adds allocator cost and garbage-collection cost (time the runtime spends finding and freeing objects nobody uses any more) on every insert. Preallocating the k nodes, as above, removes it.
- Off-by-one in the age formula: newest is at
write - 1, notwrite.
Running the code
Save the block as window_compare.py. Python 3.12, standard library only; the hop count comes from the seeded sample of ages, so it is the same on every run:
python window_compare.py
In C, implement a fixed-size circular buffer with init, push, pop, is_full and is_empty. Support a mode where a full buffer overwrites the oldest element and a mode where push returns an error.
Sample Answer
The idea in plain words
A circular buffer (ring buffer) is a fixed array used as a queue: you write at one end of the stored data and read at the other, and positions wrap from the last slot back to slot 0 instead of shifting data. Because the array never moves or grows, there is no dynamic allocation, which is why embedded C code favours it.
The design question is how to tell full from empty, since the read and write positions can coincide in both states. This implementation stores a count of items. Then count == 0 is empty and count == capacity is full, all slots are usable, and the write position needs no field of its own: the next slot to write is (head + count) % capacity.
Approach, step by step
- The struct holds a pointer to caller-supplied storage,
capacity,head(slot of the oldest item),count, and themode. Taking the storage from the caller means the buffer can live in a static array, with nomalloc. rb_initrejects NULL pointers and capacity 0 (the%would divide by zero) and setshead = count = 0.rb_push, buffer not full: write at(head + count) % capacityand add 1 tocount.rb_push, buffer full, reject mode: return-1, change nothing.rb_push, buffer full, overwrite mode: the oldest item sits athead, so write the new value there and advancehead. The overwritten slot is now the newest,countstays atcapacity.rb_pop: if empty return-1. Otherwise copy the item atheadto*out, advanceheadwith wrap, subtract 1 fromcount.
C has no way to return two things, so rb_pop uses the out-parameter idiom: the return value is a status code (0 for success, -1 for failure) and the popped value is written through a pointer the caller passes in. The caller declares int out;, passes &out (the address of that variable), and the function's *out = ... stores into the caller's variable. The same style explains why rb_push returns a status instead of a value.
The code
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* An enum is a named set of integer constants: the two modes get readable names. */
typedef enum { RB_REJECT_WHEN_FULL, RB_OVERWRITE_OLDEST } rb_mode;
typedef struct {
int *data; /* caller-supplied storage, capacity ints */
size_t capacity; /* size_t: the unsigned integer type C uses for sizes and indices */
size_t head; /* index of the oldest element */
size_t count; /* number of stored elements: 0..capacity */
rb_mode mode;
} ring_buffer;
int rb_init(ring_buffer *rb, int *storage, size_t capacity, rb_mode mode) {
if (rb == NULL || storage == NULL || capacity == 0) return -1;
rb->data = storage;
rb->capacity = capacity;
rb->head = 0;
rb->count = 0;
rb->mode = mode;
return 0;
}
/* const on the parameter promises these two functions only read the buffer. */
int rb_is_empty(const ring_buffer *rb) { return rb->count == 0; }
int rb_is_full(const ring_buffer *rb) { return rb->count == rb->capacity; }
/* Returns 0 on success, -1 if the buffer is full in reject mode. */
int rb_push(ring_buffer *rb, int value) {
if (rb_is_full(rb)) {
if (rb->mode == RB_REJECT_WHEN_FULL) return -1;
rb->data[rb->head] = value; /* overwrite the oldest slot ... */
rb->head = (rb->head + 1) % rb->capacity; /* ... which becomes the newest */
return 0;
}
rb->data[(rb->head + rb->count) % rb->capacity] = value;
rb->count++;
return 0;
}
/* Out-parameter idiom: the return value is a status code (0 ok, -1 failure), so the
popped value comes back through the pointer `out`, which the caller points at its own
variable; `*out = ...` writes into that variable. */
/* Returns 0 and stores the oldest element in *out, or -1 if empty. */
int rb_pop(ring_buffer *rb, int *out) {
if (rb_is_empty(rb)) return -1;
*out = rb->data[rb->head];
rb->head = (rb->head + 1) % rb->capacity;
rb->count--;
return 0;
}
static void show(const ring_buffer *rb, const char *what) {
/* %zu is the printf format for a size_t */
printf("%-18s head=%zu count=%zu slots=[", what, rb->head, rb->count);
for (size_t i = 0; i < rb->capacity; i++)
printf("%d%s", rb->data[i], i + 1 < rb->capacity ? " " : "");
printf("]\n");
}
int main(void) {
int storage[4] = {0, 0, 0, 0};
ring_buffer rb;
char label[32];
int out = 0;
for (int m = 0; m < 2; m++) {
rb_init(&rb, storage, 4, m == 0 ? RB_REJECT_WHEN_FULL : RB_OVERWRITE_OLDEST);
memset(storage, 0, sizeof storage);
printf("%s mode\n", m == 0 ? "reject-when-full" : "overwrite-oldest");
for (int v = 1; v <= 6; v++) {
int rc = rb_push(&rb, v);
snprintf(label, sizeof label, "push %d -> rc=%d", v, rc);
show(&rb, label);
}
for (int i = 0; i < 2; i++) {
rb_pop(&rb, &out);
snprintf(label, sizeof label, "pop -> %d", out);
show(&rb, label);
}
rb_push(&rb, 7);
show(&rb, "push 7");
}
/* The guards: bad arguments are rejected, and a failed pop leaves *out alone. */
int rc_storage = rb_init(&rb, NULL, 4, RB_REJECT_WHEN_FULL);
int rc_zero = rb_init(&rb, storage, 0, RB_REJECT_WHEN_FULL);
int rc_buffer = rb_init(NULL, storage, 4, RB_REJECT_WHEN_FULL);
printf("rb_init rc: NULL storage=%d, capacity 0=%d, NULL buffer=%d\n", rc_storage, rc_zero, rc_buffer);
rb_init(&rb, storage, 4, RB_REJECT_WHEN_FULL);
out = -99;
int rc_empty = rb_pop(&rb, &out);
printf("pop on empty: rc=%d, out still %d\n", rc_empty, out);
/* Compare against a plain-array model on pseudo-random operations. The seed update is a
linear congruential generator: a fixed formula that yields a repeatable stream of
pseudo-random numbers, so every run does the same operations. The model is a plain
array whose oldest element is model[0]; memmove shifts it left to drop that element. */
uint32_t seed = 46;
for (int m = 0; m < 2; m++) {
for (size_t cap = 1; cap <= 5; cap++) {
int *store = malloc(cap * sizeof *store);
int model[64];
size_t n = 0;
rb_init(&rb, store, cap, m == 0 ? RB_REJECT_WHEN_FULL : RB_OVERWRITE_OLDEST);
for (int step = 0; step < 4000; step++) {
seed = seed * 1664525u + 1013904223u;
if ((seed >> 16) % 100 < 55) {
int rc = rb_push(&rb, step);
if (n == cap && m == 0) {
if (rc != -1) { puts("FAIL: push accepted when full"); return 1; }
} else {
if (rc != 0) { puts("FAIL: push rejected"); return 1; }
if (n == cap) { memmove(model, model + 1, (n - 1) * sizeof *model); n--; }
model[n++] = step;
}
} else {
int rc = rb_pop(&rb, &out);
if (n == 0) {
if (rc != -1) { puts("FAIL: pop from empty"); return 1; }
} else {
if (rc != 0 || out != model[0]) { puts("FAIL: wrong pop"); return 1; }
memmove(model, model + 1, (n - 1) * sizeof *model);
n--;
}
}
if (rb.count != n || rb_is_empty(&rb) != (n == 0) || rb_is_full(&rb) != (n == cap)) {
puts("FAIL: state mismatch");
return 1;
}
}
free(store);
}
}
puts("model check passed: 2 modes x 5 capacities x 4000 operations");
return 0;
}
Worked trace
The program printed:
reject-when-full mode
push 1 -> rc=0 head=0 count=1 slots=[1 0 0 0]
push 2 -> rc=0 head=0 count=2 slots=[1 2 0 0]
push 3 -> rc=0 head=0 count=3 slots=[1 2 3 0]
push 4 -> rc=0 head=0 count=4 slots=[1 2 3 4]
push 5 -> rc=-1 head=0 count=4 slots=[1 2 3 4]
push 6 -> rc=-1 head=0 count=4 slots=[1 2 3 4]
pop -> 1 head=1 count=3 slots=[1 2 3 4]
pop -> 2 head=2 count=2 slots=[1 2 3 4]
push 7 head=2 count=3 slots=[7 2 3 4]
overwrite-oldest mode
push 1 -> rc=0 head=0 count=1 slots=[1 0 0 0]
push 2 -> rc=0 head=0 count=2 slots=[1 2 0 0]
push 3 -> rc=0 head=0 count=3 slots=[1 2 3 0]
push 4 -> rc=0 head=0 count=4 slots=[1 2 3 4]
push 5 -> rc=0 head=1 count=4 slots=[5 2 3 4]
push 6 -> rc=0 head=2 count=4 slots=[5 6 3 4]
pop -> 3 head=3 count=3 slots=[5 6 3 4]
pop -> 4 head=0 count=2 slots=[5 6 3 4]
push 7 head=0 count=3 slots=[5 6 7 4]
rb_init rc: NULL storage=-1, capacity 0=-1, NULL buffer=-1
pop on empty: rc=-1, out still -99
model check passed: 2 modes x 5 capacities x 4000 operations
Reading the reject-mode run: after four pushes the slots are [1 2 3 4] and count=4. Pushes 5 and 6 return -1 and leave the buffer unchanged. Two pops return 1 and 2 and move head to 2. The next push lands in slot (2 + 2) % 4 = 0, replacing the stale 1, giving [7 2 3 4] with the stored items 3, 4, 7 in oldest-to-newest order.
Reading the overwrite-mode run: push 5 writes over the oldest value in slot 0 and moves head to 1; push 6 writes over slot 1 and moves head to 2. The buffer now holds 3, 4, 5, 6 oldest to newest. The pops return 3 and 4, head wraps from 3 to 0, and push 7 lands in slot (0 + 2) % 4 = 2. Popped slots are not cleared (after the two pops, slots 2 and 3 still show 3 and 4 until reused); only head and count define what is stored.
The two lines before the last one show that rb_init returns -1 for a NULL storage pointer, a zero capacity and a NULL buffer, and that a pop on an empty buffer returns -1 and leaves the caller's variable at -99. The final line comes from a check (its comments in the listing explain the random-number formula and the array model) that runs both modes at capacities 1 to 5 for 4000 random operations each, comparing every result and the count, full and empty flags with a plain array model.
Complexity
Every function is O(1) time: a few additions and one %. Space is the storage array of capacity ints plus a small struct, and nothing is allocated by the buffer itself.
Edge cases and common mistakes
- Capacity 1: push then pop works; in overwrite mode each push replaces the single value.
- Pop on empty returns
-1and leaves*outuntouched, so the caller must check the return value before usingout. - Forgetting to advance
headon an overwrite, which leaves the newest item at the head and returns data in the wrong order. - Using
head == tailas the only test, which cannot separate full from empty (the reason for storingcount). - A signed index with
%: C gives a negative remainder for a negative left operand, so this code usessize_tfor every index. - Popped slots are not cleared. Clear them if they hold secrets or pointers you must not keep alive.
- Not safe for an interrupt handler (a routine the hardware runs the moment a device signals) pushing while the main loop pops: both sides write
count, so one update can overwrite the other. Wrap the calls in a critical section (a stretch of code that must run without the other side interleaving, here by disabling interrupts briefly), or use separate free-running head and tail counters (two numbers that only ever increase, with the slot found as the counter%capacity, so the producer writes only the write counter and the consumer only the read counter).
Follow-ups
Make it a byte buffer with bulk rb_write/rb_read that handle the wrap with at most two memcpy calls. Make it safe for one producer and one consumer without locks. Make the element type generic with a macro or void * and an element size.
Running the code
The program compiles without warnings and runs clean under AddressSanitizer and UndefinedBehaviorSanitizer (two compiler checks that report out-of-bounds access and undefined arithmetic). It was built with GCC 14.2.0 in a python:3.12 container on aarch64.
# save the listing above as ring_buffer.c
gcc -std=c11 -Wall -Wextra -fsanitize=address,undefined -g ring_buffer.c -o ring_buffer
./ring_buffer
Why can traversing a linked list be much slower than traversing an array on modern CPUs even when both are O(n)? Explain the hardware effects, then describe the techniques you would use to reduce pointer-chasing costs in a linked structure that must stay linked, such as unrolling or pooling.
Sample Answer
The idea in plain words
Both traversals do n steps, so Big-O calls them equal. The hardware does not. A CPU does not read memory one number at a time: it fetches a cache line (a block of consecutive bytes, 64 bytes on most x86-64 and many ARM CPUs, 128 on some) into a small, fast cache, and anything already in the cache is cheap to read again. Main memory is far slower than the cache, so speed comes from reading data that is already there or arriving early.
An array makes that easy: its elements are neighbours, so one fetched line brings in several elements, and the addresses of the next elements are known in advance. (Latency is the waiting time for one request to memory; bandwidth is how much data per second can flow once requests are flowing. A list traversal is limited by latency, an array scan mostly by bandwidth.) A linked list makes it hard for two reasons: its nodes can be anywhere in memory, and the address of the next node is stored inside the current node, so the CPU cannot even start the next load until the current one has finished. That second effect, a chain of dependent loads, is the core of pointer-chasing cost.
The hardware effects
- Spatial locality and cache lines. Reading
a[i]fetches the whole 64-byte line it sits in, which holds up to 15 of the following 4-byte ints (15 ifa[i]is the first int of its line, fewer otherwise), for free. A node in a scattered list brings in its own line and usually nothing else you will use. - Prefetching. The CPU watches the sequence of addresses and, when it sees a steady stride (a fixed gap between successive addresses) such as
a[0], a[1], a[2], fetches the following lines before they are asked for. It can do that for an array. For a list it can only guess if the nodes happen to sit at regular spacing in memory. - Memory-level parallelism. An out-of-order CPU (one that starts later instructions while an earlier one waits for memory, as long as the later ones do not depend on it) can have many loads in flight at once if their addresses do not depend on each other. Array loads are independent, so the memory latency is overlapped. List loads form a chain, so the total time is roughly n times the latency of one trip to wherever the node lives.
- TLB. Programs use virtual addresses, and each access needs a translation to a physical page. The TLB (translation lookaside buffer) is a small cache of recent translations. A page is commonly 4 KiB. An array walk crosses into a new page every 4096 bytes. Scattered nodes can land in a different page on almost every step, and a TLB miss triggers a walk of the page tables (the operating system's map from virtual pages to physical pages, stored in ordinary memory), which is extra memory reads.
- Branch prediction. The loop branch
while nodeis easy to predict for both structures, so branch prediction is not the main reason lists are slower. It matters indirectly: when the loop has a data-dependent branch (for exampleif node.value > x), the condition depends on the loaded value. For an array the CPU runs ahead and resolves it early. For a list the value arrives late, so a misprediction is discovered late and more speculative work is thrown away. Speculative work is what the CPU executes on a guess about which way a branch will go; if the guess is wrong, that work is discarded.
A model that counts these effects
The program replays address sequences through a simulated cache (512 lines of 64 bytes, fully associative, least-recently-used replacement) and a simulated TLB (64 pages of 4096 bytes), for 65536 4-byte values. "Fully associative" means any line may sit in any cache slot; real caches let each line live in only a few slots, so real miss counts are somewhat higher when many lines map to the same slots. "Least-recently-used replacement" means that when the cache is full, the line untouched for the longest time is evicted to make room. With these two rules the model counts only the misses caused by the layout itself. The first table below shows what layout alone does to the miss counts; the second applies the same idea to chains of segments. It is a simplified model: it ignores the prefetcher, real associativity and memory timing, so its numbers show the effect of layout, not the speed of any particular CPU.
import random
from collections import OrderedDict
LINE = 64 # bytes per cache line
PAGE = 4096 # bytes per page
CACHE_LINES = 512 # model cache: 512 lines = 32 KiB, fully associative, LRU
TLB_ENTRIES = 64 # model TLB: 64 page translations, fully associative, LRU
class LRU:
def __init__(self, capacity):
self.capacity, self.items, self.misses = capacity, OrderedDict(), 0
def touch(self, key):
if key in self.items:
self.items.move_to_end(key)
return
self.misses += 1
self.items[key] = True
if len(self.items) > self.capacity:
self.items.popitem(last=False)
def run(addresses):
"""Replay a list of (address, size) reads. Returns (cache misses, TLB misses)."""
cache, tlb = LRU(CACHE_LINES), LRU(TLB_ENTRIES)
for addr, size in addresses:
for line in range(addr // LINE, (addr + size - 1) // LINE + 1):
cache.touch(line)
for page in range(addr // PAGE, (addr + size - 1) // PAGE + 1):
tlb.touch(page)
return cache.misses, tlb.misses
N = 1 << 16 # 65536 elements, all 4-byte ints
rng = random.Random(1)
scattered = list(range(N))
rng.shuffle(scattered) # node k of the list lives in slot scattered[k]
layouts = [] # (name, reads, dependent loads)
layouts.append(("array of int32", [(4 * i, 4) for i in range(N)], 0))
layouts.append(("list, 16 B nodes, in list order", [(16 * i, 16) for i in range(N)], N))
layouts.append(("list, 16 B nodes, scattered", [(16 * s, 16) for s in scattered], N))
layouts.append(("list, 8 B nodes (32-bit index), in order", [(8 * i, 8) for i in range(N)], N))
layouts.append(("list, 8 B nodes (32-bit index), scattered", [(8 * s, 8) for s in scattered], N))
CHUNK = 14 # 14 ints (56 B) + 8 B next pointer = one 64 B line
chunks = (N + CHUNK - 1) // CHUNK
layouts.append(("unrolled list, 64 B nodes, scattered", [(64 * s, 64) for s in rng.sample(range(chunks), chunks)], chunks))
print(f"{N} elements; model cache {CACHE_LINES} lines of {LINE} B, TLB {TLB_ENTRIES} pages of {PAGE} B")
print(f"{'layout':<44}{'cache misses':>13}{'TLB misses':>12}{'dependent loads':>17}")
for name, reads, chases in layouts:
cm, tm = run(reads)
print(f"{name:<44}{cm:>13}{tm:>12}{chases:>17}")
print()
print("segment chain: 1 MiB of payload split into segments of s bytes (+8 B next pointer), segments scattered")
print(f"{'segment payload s':>18}{'segments':>10}{'cache misses':>14}{'dependent loads':>17}")
TOTAL = 1 << 20
for s in (16, 64, 256, 4096):
seg = s + 8
count = TOTAL // s
slots = list(range(count))
rng.shuffle(slots)
stride = (seg + 15) // 16 * 16 # each segment is placed on a 16-byte boundary
cm, _ = run([(stride * k, seg) for k in slots])
print(f"{s:>18}{count:>10}{cm:>14}{count:>17}")
cm, _ = run([(i * 64, 64) for i in range(TOTAL // 64)])
print(f"{'contiguous buffer':>18}{1:>10}{cm:>14}{0:>17}")
print()
print("passes over the same 65536 scattered values: walk the list p times, or convert once and scan p times")
print(f"{'passes p':>9}{'list misses':>13}{'convert misses':>16}")
ARRAY_BASE = 1 << 30 # the new array lives far from the nodes
node_reads = [(16 * s, 16) for s in scattered]
array_reads = [(ARRAY_BASE + 4 * i, 4) for i in range(N)]
for p in (1, 2, 3):
list_cm, _ = run(node_reads * p)
convert_cm, _ = run(node_reads + array_reads + array_reads * p) # one chase, writes, then p scans
print(f"{p:>9}{list_cm:>13}{convert_cm:>16}")
Run with Python 3.12.15, it prints:
65536 elements; model cache 512 lines of 64 B, TLB 64 pages of 4096 B
layout cache misses TLB misses dependent loads
array of int32 4096 64 0
list, 16 B nodes, in list order 16384 256 65536
list, 16 B nodes, scattered 63945 49244 65536
list, 8 B nodes (32-bit index), in order 8192 128 65536
list, 8 B nodes (32-bit index), scattered 61844 33000 65536
unrolled list, 64 B nodes, scattered 4682 627 4682
segment chain: 1 MiB of payload split into segments of s bytes (+8 B next pointer), segments scattered
segment payload s segments cache misses dependent loads
16 65536 65056 65536
64 16384 32372 16384
256 4096 20310 4096
4096 256 16627 256
contiguous buffer 1 16384 0
passes over the same 65536 scattered values: walk the list p times, or convert once and scan p times
passes p list misses convert misses
1 63945 72137
2 127882 76233
3 191819 80329
How to read it:
- Array: 4096 misses = 65536 x 4 B / 64 B, one miss per line, and 64 TLB misses (one per page). No dependent loads.
- Perfectly laid-out list with 16-byte nodes (a 4-byte value, padding, an 8-byte pointer on a 64-bit machine): 16384 misses, four times the array, because each element drags 16 bytes with it instead of 4. It still has 65536 dependent loads.
- Scattered list: 63945 misses, almost one per node, and 49244 TLB misses, because the 1 MiB working set (the memory the loop touches) is far bigger than the 32 KiB model cache and the 64-page TLB. This is the case that "linked lists are slow" refers to.
Reducing pointer-chasing cost in a structure that must stay linked
In interviews the usual answers are pooling and unrolling, with a short mention of why scattered nodes hurt. Packing, software prefetch and the conversion trade-off in item 5 are deeper material, asked mostly for systems and performance roles.
- Pool the nodes (allocate them from one contiguous block, called an arena, handing out the next free slot for each new node, in the order you will traverse them). The table shows 16384 misses and 256 TLB misses for the in-order layout against 63945 and 49244 scattered. Pooling also removes per-node
mallocoverhead. Inserts and deletes scramble the order over time, so rebuild (compact) the pool in list order now and then; that is one O(n) pass. - Pack the nodes. Use 32-bit indices into the pool instead of 64-bit pointers, and drop padding: 8-byte nodes halve the in-order misses to 8192. The cost is an index-to-address step and a limit of about 4 billion nodes. Keep the hot fields (value, next) together and move cold fields elsewhere.
- Unroll the list: store several elements in each node. With 14 ints and a next pointer filling one 64-byte line, the scattered unrolled list takes 4682 misses and 4682 dependent loads, against 63945 and 65536. Inserts shift elements inside one chunk, and chunks run partly empty.
- Prefetch in software. When each node needs real work, issue a prefetch for the next node before processing the current one (GCC and Clang offer
__builtin_prefetch(address), which asks the CPU to start loading that address into the cache without stalling the program and, per the GCC documentation, does not fault on an invalid address), or walk several independent lists in an interleaved loop so their latencies overlap. - Give up pointer chasing for read-heavy phases. Converting a list to an array costs one chase and then every later pass is a sequential scan. Any single pass over a scattered list pays one full chase, because every node must be loaded. Reversing the list in place is one such pass: it does its work while it chases and needs no second structure. Converting to an array is also one chase, plus writing the new array. So the conversion only pays off when the array is scanned more than once afterwards. The last table printed above counts it for the 65536 scattered values: one pass costs 63945 misses on the list and 72137 with the conversion (63945 for the chase, 4096 to write the array, 4096 to scan it), so the list wins for one pass. At two passes the list costs 127882 and the conversion 76233, and the gap widens with every further pass.
Chaining variable-length segments
A buffer made of linked segments (for example a message stored as a chain of separately allocated chunks) pays a fixed cost per segment: one dependent pointer load, a fresh cache line, and the loop overhead around a copy of a few bytes. The second table in the output shows it for 1 MiB of payload: 16-byte segments cause 65056 misses and 65536 dependent loads, against 16384 misses and no chase for a contiguous buffer. At 4096 bytes per segment, 16627 misses and 256 loads remain, close to the contiguous case. So throughput falls as segments shrink: keep segments large, or coalesce small ones into a contiguous buffer before processing.
Complexity and decision
Traversal is O(n) time and O(1) extra space for both structures; only the constant differs. Use an array (or a chunked list) for scan-heavy work. Keep a plain linked list only when you need O(1) splicing at held positions, stable node addresses, or intrusive membership in several lists (an intrusive list keeps its link pointers inside the object itself, one pair per list, so one object can sit in several lists at once without any wrapper nodes), and then pool and compact it.
Common mistakes
- Treating equal Big-O as equal speed.
- Believing a list is faster for insertion without counting the walk to the insertion point.
- Assuming pooling fixes locality for good (the list order drifts from the memory order).
- Benchmarking a list that was just built (nodes allocated in order and still warm) and generalizing to a list that has lived for hours.
Running the code
docker run --rm -v "$PWD":/w -w /w python:3.12 python locality_model.py
Save the listing as locality_model.py. It uses only the standard library.
Unlock Full Question Bank
Get access to all 11 Linked Lists, Stacks, and Queues interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.