Lists, stacks and queues
Introduit| English | Sens |
|---|---|
| array/əˈreɪ/ | An indexed collection of elements arranged in one or more dimensions. |
| linked list/lɪŋkt lɪst/ | linked list |
| node/nəʊd/ | An individual unit or point in a network, graph, tree or linked data structure. |
| stack/stæk/ | A last-in, first-out data structure in which items are added and removed at the same end. |
| queue/kjuː/ | A data structure in which items are normally removed in the order they were added. |
Two layouts, different ends
- A Python list is a contiguous array: index $i$ computes the address in one step, but inserting at the front slides everyone. A linked list trades the jump for cheap splices: each node carries a pointer to the next.
- A stack adds and removes at one end (LIFO); a queue enters one end and leaves the other (FIFO).
{exercise:uni-cs0502-layouts}
Index number i in a contiguous array costs —
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
The cells sit side by side: the address is computed, not searched for.
Why append is amortized O(1)
- The array grows by doubling: appending $n$ items copies each element at most once across all regrows, so the average append is constant.
- Front insertion never amortises: every
insert(0)slides all residents — $n$ front-inserts move $\Theta(n^2)$ elements, and the count quadruples when $n$ doubles.
{exercise:uni-cs0502-append}
Append at the end of a Python list is —
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Doubling regrows copy each element at most once overall, so the average append is constant.
Traces
- Stack:
push 3, push 7, push 1, thenpop, popreturns $1$ then $7$ — last in, first out. Balanced brackets ride the same discipline: scan([]){}pushing opens; each closer must match the top, while([)]fails because)finds[on top. - Queue: enqueue
a, b, c; two dequeues returnathenb; the front isc.collections.dequeserves both ends in $O(1)$ —list.pop(0)in a loop is the classic $O(n)$ trap.
Two stacks fake a queue: an inbox and an outbox, each element handled at most twice — which is why a real deque just does both ends natively.
{exercise:uni-cs0502-trace}
push 3, push 7, push 1, pop, pop returns —
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
A stack pops in reverse push order: last in, first out.