Circular and ring buffers

A fixed-size FIFO laid out in a circle. The write position wraps around.

The whole trick: modulo

• Two indices: head (read), tail (write)
• index = (index + 1) % capacity — wraps to 0
• O(1), no allocation, fixed memory
• Full → overwrite oldest, or refuse (backpressure)

Watch it wrap and overwrite

Slots stay put; positions travel. Tail wraps past the end; oldest gets overwritten when full.

Scratch vs library

Both O(1). deque(maxlen) ≈10× faster (C vs a Python modulo per push).

Where you meet it

• Audio/network buffers, packet rings
• dmesg kernel log, "last N events"
• deque(maxlen=N) — this is what it does underneath

Takeaway

Fixed array + two wrapping indices = an endless queue in O(capacity) memory. Worst-case O(1), no GC pauses. Next tier: hashing.