Skip to content
LumenaryAcademy
Core 60 min

Arrays, linked lists, stacks and queues

Two ways to keep things in a row — side by side, or each holding the next one's hand — and the four structures nearly every program is built on.

Code tested · 7AI-draftedAwaiting review by a computer scientist

Your guides: Chloe · The Computer Scientist, Margaret · The Experimenter, Gideon · The Verifier

MotivationH

Where do the items live?

A bus company in Accra keeps the list of passengers waiting for the next coach to Kumasi. A text editor in Hanoi remembers the last two hundred changes so that Undo can take them back one by one. A music app in Montevideo plays the songs in its queue in order, while the listener keeps adding more at the end and occasionally drags one to the front.

All three programs keep a sequence of items. In Python you would reach for a list without thinking, and for small programs that is the right reflex. But underneath every list there is a decision the computer must make: where in memory does each item live? There are two basic answers.

  • Side by side. Put the items in one unbroken block of memory, item 0 first, then item 1, and so on. This is an array.
  • Anywhere, holding hands. Put each item wherever there is room, and have each item remember where the next one is. This is a linked list.

Almost everything in this lesson follows from that one choice: which operations are fast, which are slow, how much memory is wasted, and how well the computer's caches can help. On top of these two layouts we will build the two most useful disciplines for a sequence — the stack, where the last item in is the first out, and the queue, where the first in is the first out — and see where each one quietly runs the software you use every day.

The lesson assumes you know Python lists from Collections and big-O notation from Complexity.

IntuitionH

Memory is a long street of numbered houses

To a program, memory looks like an enormously long street of numbered houses, each holding one byte. The number of a house is its address. If an array of 8-byte numbers starts at address bb, then item ii lives at address b+8ib + 8i. Finding it takes one multiplication and one addition, no matter whether ii is 3 or 3 million. That is why reading a[i] costs O(1)O(1): the array is a formula, not a search.

The price of living side by side shows up when you want to squeeze in a newcomer. To insert at the front of an array of nn items, every item must move one house down the street: nn moves, so O(n)O(n). And when the block is full, there may be no free house next door at all.

A linked list makes the opposite trade. Each item sits in its own small node, together with the address of the next node. To insert at the front you create a node and point it at the old first node: two steps, whatever the length. But to find item ii you must start at the head and follow ii links, one after another: O(i)O(i).

array: one block72940123address of item i = b + i × sizelinked list: scattered nodes7294None
The same four items as an array (top), where position alone tells you the address, and as a singly linked list (bottom), where each node stores the address of the next one and the last points to nothing.

Analogy, not a formal construction

An array is a row of numbered cinema seats: if your ticket says seat 17, you walk straight to it. A linked list is a treasure hunt: each clue tells you where the next clue is hidden. Adding a new first clue is easy (hide it anywhere and make it point to the old first clue), but reaching the seventeenth clue means visiting the sixteen before it.

There is a second, less obvious difference. Processors do not fetch single bytes from main memory; they fetch whole cache lines, typically 64 bytes at a time, and they guess which line you will want next. Walking through an array, the next item is almost always already in the cache. Walking through a linked list, every node may be somewhere new, and the processor must wait for each one before it even knows where the next one is. This pointer chasing can make a linked-list traversal many times slower than an array traversal of the same length, even though both are O(n)O(n). The lesson on the memory hierarchy explains why.

One more fact about Python in particular: a Python list is an array of references. The block of memory holds addresses of objects, and the objects themselves (ints, strings, other lists) live elsewhere. That is why one list can hold values of different types. When you want raw numbers packed side by side, use the standard array module or NumPy.

DefinitionsH

Definitions

Definition— array

An array is a fixed number of slots of equal size stored in one contiguous block of memory, so that the address of slot ii is computed directly from ii.

Definition— dynamic array

A dynamic array keeps a size nn (how many items are in use) and a capacity c≥nc \ge n (how many slots are allocated). Appending when n<cn < c writes into the next free slot; appending when n=cn = c first allocates a larger block, copies the nn items across, and frees the old block. Python's list, Java's ArrayList, C++'s std::vector and Rust's Vec are dynamic arrays.

Definition— amortised cost

An operation has amortised cost f(n)f(n) if every sequence of mm such operations, starting from an empty structure, costs at most m⋅f(n)m \cdot f(n) in total. Individual operations may be expensive; the average over any sequence is not. (No probability is involved: this is a guarantee about the worst sequence.)

Definition— linked lists

A singly linked list is a chain of nodes, each holding a value and a reference to the next node; the list itself stores a reference to the first node (the head) and often to the last (the tail). In a doubly linked list each node also holds a reference to the previous node.

Definition— abstract data type

An abstract data type (ADT) is defined by its operations and their behaviour, not by its memory layout. A stack supports push(x) and pop(), where pop removes the most recently pushed item that has not yet been removed: last in, first out (LIFO). A queue supports enqueue(x) and dequeue(), where dequeue removes the least recently added item: first in, first out (FIFO). A deque (double-ended queue, pronounced "deck") allows adding and removing at both ends.

ExplanationH

Dynamic arrays and amortised doubling

Suppose a dynamic array is full and someone appends. The array must allocate a larger block and copy everything across, which costs Θ(n)\Theta(n). If it grew by just one slot each time, every append would copy everything, and nn appends would cost 1+2+⋯+(n−1)=Θ(n2)1 + 2 + \cdots + (n-1) = \Theta(n^2). The trick that makes dynamic arrays practical is to grow by a constant factor.

Theorem— Doubling gives amortised O(1) appends

A dynamic array that starts with capacity 1 and doubles its capacity whenever an append finds it full performs fewer than 2n2n item copies during any sequence of nn appends. Hence the total cost of the nn appends is O(n)O(n) and the amortised cost of an append is O(1)O(1).

Proof

Copies happen only when an append finds the array full. With doubling, the capacities are 1,2,4,8,…1, 2, 4, 8, \ldots, so the resizes happen when the size is 1,2,4,…,2k1, 2, 4, \ldots, 2^k, copying that many items each time. The last resize happens on the append that brings the size from 2k2^k to 2k+12^k + 1, so 2k+1≤n2^k + 1 \le n, that is 2k<n2^k < n. The total number of copies is

1+2+4+⋯+2k=2k+1−1<2⋅2k<2n.1 + 2 + 4 + \cdots + 2^k = 2^{k+1} - 1 < 2 \cdot 2^k < 2n.

Each append also writes its own item once, so the total work is less than 3n=O(n)3n = O(n).

∎

Here is another way to see it, sometimes called the banker's method. Charge every append 3 coins. One pays for writing the item; the other two are saved in the item's slot. Just after a resize to capacity 2c2c the array holds cc items and no savings. By the time it is full again, cc new items have been appended, saving 2c2c coins — exactly enough to pay for copying all 2c2c items into the next block. The bank never goes into debt, so 3 coins per append always suffice.

Nothing is special about the number 2. If the capacity is multiplied by any factor r>1r > 1, the copies form a geometric series n(1+1/r+1/r2+⋯ )≤n⋅rr−1n(1 + 1/r + 1/r^2 + \cdots) \le n \cdot \frac{r}{r-1}, still O(n)O(n). A larger rr means fewer copies and more wasted space. Real libraries pick different points on that trade-off: CPython over-allocates by roughly an eighth (see list_resize in listobject.c), Java's ArrayList grows by half, and C++ leaves the factor to the implementation. Growing by a constant number of slots, however large, is always quadratic in the end.

python
def copies_for(n, grow):
    """Simulate n appends. grow(c) is the new capacity of a full array of capacity c."""
    capacity, size, copies = 1, 0, 0
    for _ in range(n):
        if size == capacity:          # full: allocate a bigger block and move everything
            copies += size
            capacity = grow(capacity)
        size += 1
    return copies

n = 100_000
rules = {
    "double (x2)": lambda c: 2 * c,
    "grow by half (x1.5)": lambda c: c + c // 2 + 1,
    "CPython-like (x1.125)": lambda c: c + (c >> 3) + 6,
    "add 100 slots": lambda c: c + 100,
}
for name, grow in rules.items():
    k = copies_for(n, grow)
    print(f"{name:22} {k:>12,} copies  = {k / n:7.2f} per append")

# A real Python list: at which lengths does its memory block grow?
import sys
items, last, grew_at = [], sys.getsizeof([]), []
for i in range(80):
    items.append(i)
    if sys.getsizeof(items) != last:
        grew_at.append(len(items))
        last = sys.getsizeof(items)
print("this Python's list grew when its length became", grew_at)
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

The exact lengths in the last line depend on the Python version, but the gaps between them widen as the list grows: that widening is the geometric growth at work.

Shrinking. A list that grows can also shrink after many pops. The tempting rule "halve the capacity when the array is half full" has a trap: an array sitting exactly at the boundary can alternate between a grow and a shrink on every single append and pop, each costing Θ(n)\Theta(n). The standard fix is hysteresis: double when full, but halve only when the array is a quarter full. After any resize the array is half full, so at least c/4c/4 cheap operations must happen before the next resize, and they pay for it.

ExplanationH

Linked lists, singly and doubly

A singly linked list in Python needs only a tiny class:

python
class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

head = Node(7, Node(2, Node(9, Node(4))))   # 7 -> 2 -> 9 -> 4 -> None

Inserting at the front is head = Node(x, head): constant time. Inserting after a node you already hold is also constant time: node.next = Node(x, node.next). But removing a node needs its predecessor, because the predecessor's next must skip over it, and in a singly linked list the only way to find the predecessor is to walk from the head. A doubly linked list fixes that: each node knows both neighbours, so a node can unlink itself in O(1)O(1).

The fiddliest part of linked-list code is the special cases: an empty list, removing the head, removing the tail. A sentinel (a dummy node that is never removed) makes them disappear. In a circular doubly linked list with a sentinel, the sentinel's next is the first real node and its prev the last, and an empty list is a sentinel pointing at itself. Every insertion and every removal is then the same few pointer assignments, with no if in sight.

OperationDynamic arraySingly linked (head and tail)Doubly linked
Read item iiO(1)O(1)O(i)O(i)O(min⁡(i,n−i))O(\min(i, n-i))
Insert or remove at the frontO(n)O(n)O(1)O(1)O(1)O(1)
Append at the backO(1)O(1) amortisedO(1)O(1)O(1)O(1)
Remove at the backO(1)O(1)O(n)O(n)O(1)O(1)
Insert or remove beside a node you holdO(n)O(n)O(1)O(1) after it, O(n)O(n) beforeO(1)O(1)
Search for a valueO(n)O(n)O(n)O(n)O(n)O(n)
Extra memory per itema little spare capacityone referencetwo references

Read the table carefully: linked lists win only when you already hold a reference to the place where the change happens. That is exactly the situation in a least-recently-used (LRU) cache, one of the most common structures in real systems. A cache keeps at most kk entries; when it is full, it throws away the entry that was used longest ago. A dictionary maps each key to its node, and a doubly linked list keeps the nodes in order of last use. Looking up a key finds its node in O(1)O(1), unlinks it in O(1)O(1) and moves it to the front in O(1)O(1); evicting takes the node at the back. The pure-Python versions of functools.lru_cache and collections.OrderedDict in CPython's standard library are built exactly this way, with a circular doubly linked list and a sentinel.

python
class Node:
    __slots__ = ("key", "value", "prev", "next")
    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.prev = self.next = self          # a lone node is a circle of one

class LRUCache:
    """At most `capacity` entries; the least recently used one is evicted first."""
    def __init__(self, capacity):
        self.capacity = capacity
        self.nodes = {}                      # key -> Node
        self.root = Node()                   # sentinel: root.next is newest, root.prev oldest

    def _unlink(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _push_front(self, node):
        node.prev, node.next = self.root, self.root.next
        self.root.next.prev = node
        self.root.next = node

    def get(self, key):
        node = self.nodes.get(key)
        if node is None:
            return None
        self._unlink(node)                   # O(1): the node knows both neighbours
        self._push_front(node)
        return node.value

    def put(self, key, value):
        if key in self.nodes:
            self._unlink(self.nodes[key])
        elif len(self.nodes) == self.capacity:
            oldest = self.root.prev
            self._unlink(oldest)
            del self.nodes[oldest.key]
            print(f"  evicted {oldest.key}")
        node = Node(key, value)
        self.nodes[key] = node
        self._push_front(node)

    def keys_newest_first(self):
        out, node = [], self.root.next
        while node is not self.root:
            out.append(node.key)
            node = node.next
        return out

cache = LRUCache(3)
for city, temp in [("Lima", 19), ("Oslo", 4), ("Pune", 31)]:
    cache.put(city, temp)
print(cache.keys_newest_first())
cache.get("Lima")                            # Lima becomes the newest
cache.put("Kyiv", 9)                         # full: Oslo, the oldest, goes
print(cache.keys_newest_first())
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Other places linked lists earn their keep: the Linux kernel threads intrusive lists through its own structures, so a process descriptor can sit on several lists at once without any extra allocation (kernel documentation); memory allocators keep free blocks on free lists; and functional languages use immutable linked lists because two lists can safely share the same tail. Outside such cases, prefer an array. Even inserting in the middle of a few thousand items is usually faster in an array, because one bulk memory move over contiguous memory is cheap and caches love it.

ExplanationH

Stacks: last in, first out

A stack is the discipline of a pile of plates: you add to the top and take from the top. In Python, a list is a good stack, because both append and pop() work at the end of the array, in amortised O(1)O(1). You have used a stack every time you called a function: the call stack holds one frame per active call, and returning pops it.

Stacks appear whenever the most recent unfinished business must be dealt with first:

  • Undo and redo. Every edit is pushed on an undo stack. Undo pops it and pushes it on a redo stack; a new edit clears the redo stack.
  • Matching brackets. Compilers, editors and JSON parsers check that every (, [ and { is closed by the right partner, in the right order.
  • Evaluating expressions. Calculators and interpreters turn 3 + 4 * 2 into operations using stacks of operands and operators; the Python virtual machine itself is a stack machine (see compilers and interpreters).
  • Depth-first search of a graph, as you will see in Graphs.

Example— Are the brackets balanced?

Scan the text left to right. Push every opening bracket. At a closing bracket, the stack's top must be its partner: pop it if so, report an error if not (or if the stack is empty). At the end, the stack must be empty, or some bracket was never closed.

Why is this correct? The loop keeps an invariant: after reading any prefix of the text, the stack holds exactly the opening brackets of that prefix that have not yet been closed, oldest at the bottom. The most recently opened bracket that is still open is on top, and in a balanced text the next closing bracket must close precisely that one. So a mismatch at the top proves the text is unbalanced, and if no mismatch ever happens and the stack ends empty, every bracket was closed by its partner in properly nested order. The scan touches each character once and does O(1)O(1) work per character: O(n)O(n) time and, in the worst case (all openers), O(n)O(n) space.

python
PAIRS = {")": "(", "]": "[", "}": "{"}

def balanced(text):
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in PAIRS:
            if not stack or stack.pop() != PAIRS[ch]:
                return False
    return not stack

for s in ["f(a[i], {k: v})", "(]", "((x)", "print('ok')"]:
    print(f"{s!r:20} balanced: {balanced(s)}")

class Editor:
    """Undo and redo with two stacks."""
    def __init__(self):
        self.text, self.undo_stack, self.redo_stack = "", [], []

    def type(self, s):
        self.undo_stack.append(self.text)
        self.redo_stack.clear()              # a new edit makes the old future unreachable
        self.text += s

    def undo(self):
        if self.undo_stack:
            self.redo_stack.append(self.text)
            self.text = self.undo_stack.pop()

    def redo(self):
        if self.redo_stack:
            self.undo_stack.append(self.text)
            self.text = self.redo_stack.pop()

ed = Editor()
for word in ["Habari ", "ya ", "asubuhi"]:
    ed.type(word)
ed.undo(); print(repr(ed.text))
ed.undo(); print(repr(ed.text))
ed.redo(); print(repr(ed.text))
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
ExplanationH

Queues, deques and circular buffers

A queue serves items in the order they arrived: first come, first served. Print spoolers, web servers' request backlogs, the tasks waiting for a worker, the packets waiting for a network card, and the frontier of a breadth-first search are all queues.

The obvious Python queue, a list with append to join and pop(0) to leave, is a trap. pop(0) removes the item at the front of the array, so every remaining item shifts one slot left: O(n)O(n) per dequeue and O(n2)O(n^2) to drain a queue of nn items. The standard library's answer is collections.deque, which supports append, appendleft, pop and popleft in O(1)O(1). CPython builds it as a doubly linked list of blocks, each an array of 64 slots: within a block the items enjoy array locality, and the links let both ends grow without ever shifting anything. The price is that reading d[i] in the middle is O(n)O(n), so a deque is not a replacement for a list in general.

For queues shared between threads, use queue.Queue, which adds the locking that producers and consumers need; the lesson on concurrency explains why.

Circular buffers. Many systems want a queue that never allocates memory once it is running: an audio driver passing samples to the sound card, a network card's receive ring, a logger keeping the last thousand events, a trading system that cannot afford a pause. A circular buffer (ring buffer) is a fixed array of capacity kk plus two numbers: the index head of the oldest item and the count of items. The next free slot is (head + count) % k. Enqueueing writes there; dequeueing reads at head and advances it by one, wrapping round to 0 at the end. Both are O(1)O(1) with no copying at all. When the buffer is full there are two policies: refuse the new item (which tells the producer to slow down, called backpressure) or overwrite the oldest (right for "the last kk readings"). Python's deque(maxlen=k) implements the overwrite policy; the Linux kernel documents its lock-free ring buffers, and high-throughput systems such as the LMAX Disruptor are built around one.

python
from collections import deque
import time

class RingBuffer:
    """A FIFO queue in a fixed array; refuses new items when full."""
    def __init__(self, capacity):
        self.slots = [None] * capacity
        self.head = 0
        self.count = 0

    def enqueue(self, item):
        if self.count == len(self.slots):
            return False                      # full: backpressure
        self.slots[(self.head + self.count) % len(self.slots)] = item
        self.count += 1
        return True

    def dequeue(self):
        if self.count == 0:
            raise IndexError("dequeue from empty buffer")
        item = self.slots[self.head]
        self.slots[self.head] = None          # let the item be garbage-collected
        self.head = (self.head + 1) % len(self.slots)
        self.count -= 1
        return item

ring = RingBuffer(3)
print([ring.enqueue(x) for x in "ABCD"])      # the fourth is refused
print(ring.dequeue(), ring.dequeue())
ring.enqueue("E"); ring.enqueue("F")          # these wrap round to slots 0 and 1
print(ring.slots, "head =", ring.head)
print([ring.dequeue() for _ in range(3)])

# deque(maxlen=k) overwrites instead: the last 4 sensor readings
recent = deque(maxlen=4)
for reading in [21.5, 22.0, 22.4, 23.1, 22.8, 22.2]:
    recent.append(reading)
print("last four:", list(recent), "mean:", round(sum(recent) / len(recent), 2))

# list.pop(0) versus deque.popleft() on a queue of n items
n = 30_000
q = list(range(n)); t = time.perf_counter()
while q: q.pop(0)
list_time = time.perf_counter() - t
d = deque(range(n)); t = time.perf_counter()
while d: d.popleft()
deque_time = time.perf_counter() - t
print(f"draining {n:,} items: list {list_time:.3f}s, deque {deque_time:.4f}s")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
Common misconceptionsH

Common misconceptions

Misconception

"Linked lists insert in O(1), so they are faster than arrays for insertion." Only once you hold the node. To insert at position ii you must first walk ii links, so the whole operation is O(i)O(i), and the walk is slow pointer chasing. Unless you already have a reference to the spot (as in an LRU cache), an array is usually faster in practice.

Misconception

"Amortised O(1) means every append is fast." Most appends are, but the one that triggers a resize copies the whole array. Over a long sequence the average is constant; a single append can still take Θ(n)\Theta(n). In a program with a deadline on every step — audio, games, control systems — preallocate, or use a fixed ring buffer.

Misconception

"Amortised means average over random inputs." It does not. Amortised analysis bounds the total cost of every sequence of operations; there is no probability in it. "Expected" cost, which you will meet in Hash tables, is the one that averages over chance.

Misconception

"A stack is a list." A stack is an abstract data type — a promise about push and pop. A Python list, a linked list or a fixed array with a counter can each implement it. Separating the promise from the implementation is what lets you swap one for another when the costs matter.

History & global context

A little history

Linked lists were introduced in the mid-1950s by Allen Newell, Cliff Shaw and Herbert Simon for their Information Processing Language, which they used to write some of the first artificial-intelligence programs; list processing went on to become the heart of Lisp. At around the same time in Munich, Friedrich L. Bauer and Klaus Samelson worked out how to translate arithmetic expressions with a stack — their "cellar principle" (Kellerprinzip) — and patented it in 1957. Circular storage is older still: the mercury delay lines of the first stored-program computers kept their bits travelling round and round a loop. The ideas are seventy years old; the reasons to choose between them are as current as the latest processor's cache.

Optional Christian reflection · First come, first served

A reflection from the Christian tradition that inspires Lumenary Academy. It is not part of the mathematics and you are welcome to skip it.

The queue is one of the few data structures with a moral idea built into its definition: whoever has waited longest is served next. Fairness of this kind matters, and engineers defend it carefully. It is worth noticing that the Gospels describe a different economy — "So the last shall be first, and the first last" (Matthew 20:16, King James Version) — in which a generous master pays the latecomers a full day's wage. Grace is not a scheduling policy. But it may be good, now and then, to remember that the people in the queue are more than their position in it.

Exercises

Exercises

1. Arrays, linked lists, stacks and queues

Warm-upHuman

A Python list items holds nn items. What is the cost of items.insert(0, x)?

Choose one

2. Arrays, linked lists, stacks and queues

CoreHuman

A dynamic array starts empty with capacity 1. Whenever an append finds it full, it allocates a block of twice the capacity and copies every existing item across, then writes the new item. How many item copies (not counting the writes of the new items) happen during the first 17 appends?

3. Arrays, linked lists, stacks and queues

Warm-upHuman

A web browser's Back button returns you to the page you visited most recently before the current one; pressing it again goes one page further back. Which abstract data type fits the history behind the Back button best?

Choose one

4. Arrays, linked lists, stacks and queues

CoreComputational

An editor wants to highlight the first problem with the brackets (), [] and {} in a line of code. Write first_error(text) that returns:

  • -1 if every bracket is matched and properly nested (other characters are ignored);
  • otherwise, if some closing bracket has no matching partner (the stack is empty or its top is the wrong kind), the index of the first such closing bracket;
  • otherwise (the text ended with brackets still open), the index of the earliest opening bracket that was never closed.

For example first_error("{[}]") is 2, first_error("ok)(") is 2, and first_error("[x](y{z") is 3.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

5. Arrays, linked lists, stacks and queues

CoreComputational

Build a FIFO queue out of two Python lists used only as stacks (only append, pop() with no argument, len and truthiness). Complete TwoStackQueue with enqueue(x), dequeue() (which raises IndexError when the queue is empty) and __len__.

Your dequeue should be amortised O(1)O(1): over any sequence of operations, each item should be moved between the two stacks at most once.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

6. Arrays, linked lists, stacks and queues

CoreComputational

Write reverse(head) that reverses a singly linked list in place and returns the new head. Do not create any new nodes: re-point the existing ones. It must work on the empty list (None) and on lists of 100,000 nodes (so a recursive solution will hit Python's recursion limit).

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

7. Arrays, linked lists, stacks and queues

CoreHuman

d is a collections.deque holding nn items. Which of these operations take O(1)O(1) time in CPython? Select all that apply.

Choose all that apply

8. Arrays, linked lists, stacks and queues

StretchHuman

A dynamic array doubles its capacity when an append finds it full. To save memory it should also shrink after many pops. Which shrinking rule keeps every sequence of appends and pops at amortised O(1)O(1) per operation?

Choose one

Further reading and resources

  • collections.deque · Python documentationThe standard double-ended queue, including the maxlen option used for circular buffers.
  • CPython source: Objects/listobject.cSearch for list_resize to see exactly how much spare room a Python list reserves when it grows.
  • CPython source: Modules/_collectionsmodule.cThe deque implementation, a doubly linked list of 64-slot blocks, with a long explanatory comment at the top.
  • TimeComplexity · Python WikiThe cost of every common operation on list, deque, dict and set in CPython.
  • Linked Lists in Linux · The Linux kernel documentationHow the kernel embeds list links inside its own structures (intrusive lists).
  • Circular Buffers · The Linux kernel documentation
  • Open Data Structures · Pat MorinA free, openly licensed textbook; its chapters on array-based lists and linked lists go further than this lesson.