Module 3
Arrays, linked lists, stacks & queues
Every linear structure is a bet about which operations you'll do most. An array stores elements contiguously, so arithmetic finds any index instantly — O(1) access, great cache behavior — but inserting in the middle shifts everything after it: O(n). A linked list inverts the bet: each node points to the next, so splicing a node in or out is O(1) once you're standing there, but getting there is an O(n) walk — no shortcuts, no index math.
Stacks and queues aren't new memory layouts — they're disciplines imposed on either one. A stack only touches one end (LIFO: last in, first out); a queue adds at one end and removes at the other (FIFO: first in, first out). The discipline is the point: it makes both operations O(1) and the behavior predictable enough to build on — call stacks, undo histories and DFS on the stack side; task scheduling, buffering and BFS on the queue side.
| Operation | Array | Linked list | Stack | Queue |
|---|---|---|---|---|
| Index access a[i] | O(1) | O(n) | — | — |
| Search (unsorted) | O(n) | O(n) | O(n) | O(n) |
| Insert/remove at end | O(1)* | O(1)† | O(1) push/pop | O(1) enqueue |
| Insert/remove at front | O(n) | O(1) | — | O(1) dequeue |
| Insert/remove in middle | O(n) | O(1)‡ | — | — |
* amortized (dynamic array resize) † with a tail pointer ‡ given a reference to the node — finding it is still O(n)
🎛 Stack vs queue — same inserts, different exits
Stack — LIFO (top on the right)
pop takes the highlighted end — undo history, call stacks, DFS, matching brackets
Queue — FIFO (front on the left)
dequeue takes the highlighted end — task queues, BFS, rate limiters, printers
Worked example — valid brackets, the canonical stack problem
Is "([]{})" balanced? Openers wait on a stack; every closer must match the most recent unmatched opener — exactly LIFO:
def valid(s):
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in s:
if ch in '([{':
stack.append(ch) # opener waits
elif not stack or stack.pop() != pairs[ch]:
return False # wrong or missing opener
return not stack # leftovers = unclosed
# O(n) time, O(n) space — and the moment you say "most recent first",
# you've already said "stack"Choosing in one line each
- Array / dynamic array — default collection; you index, iterate, and append. 95% of the time this is the answer.
- Linked list — constant-time splicing at known positions; the machinery inside LRU caches and deques. Rarely reached for directly, often asked about.
- Stack — “most recent first”: nesting, undo, backtracking, DFS, expression evaluation.
- Queue / deque — “in arrival order”: BFS, schedulers, buffers, sliding windows (deque).
Say it out loud
- “Inserting at the front repeatedly is O(n) per insert on an array — a deque makes that O(1).”
- “I need the most recently seen unmatched element — that phrase means stack.”
- “Linked list wins only if I already hold a reference to the node; otherwise the O(n) find eats the O(1) splice.”