Elementary Data Structures
By the end of this lesson you will be able to build a stack and a queue on top of a plain array (including real overflow and underflow checks), splice nodes into a doubly linked list using a sentinel so there are zero special cases, simulate pointers and objects in a language that only has arrays (and see exactly what "out of memory" looks like), and represent ANY rooted tree — no matter how many children a node has — using just two pointers per node.
Until now the lessons worked on plain arrays. From here on we build data structures: first the elementary containers made from arrays and pointers (this lesson), then hash tables, binary search trees and balanced trees in the lessons that follow. A dynamic set is just "a collection of things I can add to, remove from, and ask questions about, while my program runs." Every structure in this lesson is one way to build a dynamic set — the differences are all about which operations are fast and which are slow.
1. Stacks and queues
Both can be built directly on top of an array. A stack needs one attribute, top — the number of stored elements, which is also the index of the next free slot (0 means empty). Overflow and underflow checks are easy to forget, so this lesson always shows them for real: overflow and underflow below are genuine thrown exceptions, not text that merely claims they would happen.
_s[0..capacity-1]. Because top counts the stored elements, the top element lives at _s[top - 1] and the next free slot is _s[top]: a push writes to _s[top] and then increments top; a pop decrements top and then reads _s[top]. Overflow/underflow are thrown as real exceptions, exactly matching what the animations above show — this is the very class exercised in verify/c10.dart.Where each listing line lives in the code: isEmpty is isEmpty() (top == 0), push is push (overflow check, then the write at _s[top] and top = top + 1), pop is pop (underflow check, top = top - 1, then the read at _s[top]).
Input size → what is feasible: capacity ≤ 106 and up to 106 operations → every push/pop is O(1), so about 106 steps in total; a version that shifted the whole array on each call would be 1012.
top and one array slot — no shifting, no scanning. Both run in O(1), whether the stack holds 3 elements or 3 million.Two stacks sharing one array
Stack 1 grows from the left end of the array, stack 2 from the right end, so overflow happens only when all n slots are used (top1 + top2 == n), not when one stack alone fills half of the array:
Input size → what is feasible: n ≤ 106 slots, any split between the two stacks → O(1) per operation, O(n) space; two separate arrays of n/2 would overflow while half the memory is still free.
A queue needs TWO attributes, head (index of the oldest element) and tail (index of the next FREE slot), and it wraps both around the end of the array back to the start — a circular queue. Picture a circular parking lot with numbered spaces: cars enter at the "tail" space and leave from the "head" space, and once you pass the last space you wrap back around to space 0. There is one subtlety: if the queue stores only head and tail, the array must keep one slot permanently empty. Without that spare slot, "the lot is completely full" and "the lot is completely empty" would both look like head == tail — indistinguishable. With the spare slot, empty is head == tail, and full is "one more car would make the tail catch up with the head."
head and tail are plain array indices, and wrapping is one modulo: tail = (tail + 1) % length. The queue is empty when head == tail and full when (tail + 1) % length == head, which is why only length - 1 elements fit.Two facts as code: the number of stored elements is (tail − head) mod length, and an array of length slots can store only length − 1 elements (fillUntilOverflow counts them):
Input size → what is feasible: length ≤ 106, up to 106 operations → O(1) each; list.removeAt(0) as dequeue would be up to 1012 element moves in total.
head and tail and is backed by an array of length n can only ever hold n − 1 usable elements, not n — that reserved slot is the price of telling empty and full apart with simple index comparisons. (Keeping a separate element count instead of leaving a gap avoids the waste: the circular deque in the interview bank below does exactly that.)The deque as code (front and size replace head/tail; the rear slot is (front + size - 1) mod capacity):
A queue from two stacks, and a stack from two queues
A queue from two stacks: elements are only moved from the input stack to the output stack when the output stack is empty, so each element is moved at most once — at most 4 stack operations per element (push, pop, push, pop), i.e. amortized O(1). A stack from two queues goes the other way: push is O(1) but pop is Θ(n).
Input size → what is feasible: up to 106 operations → the two-stack queue does at most 4·106 stack operations; the two-queue stack makes pop cost n, so only 103–104 pops are comfortable (n = 105 pops on a 105-element stack is 1010).
List already is a stack (add / removeLast are O(1), see D26 · every List method); Queue / ListQueue is a ring buffer used as a queue or a deque with O(1) at both ends, and LinkedList is an intrusive doubly linked list whose entries are the nodes themselves (D28 · Queue, LinkedList and the rest of dart:collection). Never use list.removeAt(0) as dequeue: it is O(n).2. Linked lists
search walks from the head comparing keys — Θ(n) worst case, since the key you want might be the very last node, or missing entirely. insert and delete only rewire a handful of pointers, so they're O(1) — if you already hold a pointer to the node; deleting "the node with key 5" still costs a Θ(n) search to find it first.
The three operations WITHOUT a sentinel (a doubly linked list whose head is null when empty) — note the branches in insert and delete that the sentinel will remove:
search(k): first node with key k, or null 1 x ← head 2 while x ≠ null and x.key ≠ k: 3 x ← x.next 4 return x insert(x): put node x at the front 1 x.next ← head 2 if head ≠ null: 3 head.prev ← x 4 head ← x 5 x.prev ← null delete(x): unlink node x 1 if x.prev ≠ null: 2 x.prev.next ← x.next 3 else: 4 head ← x.next 5 if x.next ≠ null: 6 x.next.prev ← x.prev
The same three procedures in Dart (no index arithmetic here, there is no array):
Input size → what is feasible: n ≤ 105 nodes → SEARCH is up to 105 steps, INSERT/DELETE are O(1); 105 searches on a 105-node list is 1010, so move to a hash table (a later lesson) when searches dominate.
A sentinel removes those branches: one extra dummy node, nil, stands in for every null pointer and turns the list into a circular doubly linked list (the empty list is just nil pointing to itself both ways). Every "is this the first/last node?" check disappears from insert and delete — fewer branches, smaller constant factor, same asymptotic cost. Below are search, insert and delete for the sentinel version, animated on a circular doubly linked list.
DNode? fields (next/prev) are the pointers. The sentinel nil is a real, permanent DNode object built once in the constructor (never null), and search returning "nil" becomes returning Dart's null at the API boundary (search() checks x == nil internally, then translates that one result to null for callers who never see the sentinel).Stacks and queues on top of linked lists, and the constant-space reversal (prev, cur and a saved next are the only extra pointers):
Input size → what is feasible: up to 106 nodes → every stack/queue operation is O(1) and the reversal is one pass (106 steps); the recursive reversal needs 106 stack frames and overflows at about 104.
next and prev pointers: x.np = x.next XOR x.prev (bitwise, treating null as address 0). Walking forward from a known previous node p lets you recover the next node as x.np XOR p, so the WHOLE list can be reversed in O(1) by just swapping which end you call "head." This only works because real machines let you XOR two memory addresses together — Dart (and most managed languages) never exposes raw addresses, so this trick is a systems-programming idea, not something you can port directly; the "Expert" question below asks you to reason about it conceptually instead of compiling it.The XOR list in code. Dart cannot read an object’s address, so a node’s “address” is its slot number in two arrays (0 stands for null) and np[x] = next XOR prev; reading next = np[x] ^ prev works because XOR undoes itself, and reverse() just swaps head and tail:
3. Implementing pointers and objects
key lives in array key[], field next lives in array next[], both at the SAME index." A "pointer" is nothing more than that shared index — languages without native pointers/records (older Fortran, or a from-scratch systems language) build linked structures exactly this way.This is the parallel-array representation: arrays key[], next[], prev[], one slot per possible object, index i across all three arrays describing "object i." (The single-array representation packs one object's fields contiguously inside one big array using fixed offsets — more compact for same-sized objects, but fiddlier.) The remaining question: when a new node is needed, which UNUSED index do we hand out? The answer is a free list — the unused slots themselves are linked together (via the same next[] array!) into a list, used exactly like a stack.
key/next as ordinary 0-indexed List<int?>, so array slot i in the diagrams above IS Dart index i directly. An empty free list is free == null.The two representations side by side — the same doubly linked list with insertFront / delete, built on the free list. Parallel arrays: object x is slot x of key[], next[] and prev[]. Single array: object x occupies three consecutive cells a[x], a[x+1], a[x+2], and a “pointer” is the offset of the first cell (a multiple of 3). The first object is slot/offset 0, and the "no object" marker is −1.
Input size → what is feasible: n ≤ 106 objects → 3 arrays of 106 cells (or one of 3·106) is about 24–72 MB of Dart ints; allocate/free are O(1), so 106 operations cost about 106 steps.
allocate and freeObject are both O(1) — "allocating memory" here is just popping an index off the free-list stack, and "freeing" it is pushing the index back on. When the free list runs out (free == null), that is a REAL out-of-space error, shown above exactly as it happens — nothing is faked.Compaction as code: walk the list in order; the p-th node must end up in slot p, so swap it into place (or just move it if slot p is free) while repairing the neighbours’ pointers, then rebuild the free list from slot n. One pass, constant extra variables:
Input size → what is feasible: n ≤ 106 live objects in a pool of N ≤ 2·106 → Θ(n) for the walk plus N − n to rebuild the free list.
4. Representing rooted trees
left and a right pointer. But a real org chart has managers with 1 child, 2 children, or 20 — a fixed number of child pointers per node either wastes space (most nodes have far fewer than 20 children) or can't represent the tree at all.The fix is the left-child, right-sibling representation: give every node exactly TWO pointers no matter how many children it has — leftChild (its first, i.e. leftmost, child) and rightSibling (the next child of ITS OWN parent). To visit all of a node's children, you walk a linked list: start at leftChild, then keep following rightSibling until you hit null. This represents an arbitrary rooted tree in Θ(n) space no matter how lopsided the branching is.
leftChild and rightSibling are Dart fields on an LCRSNode object. insertChild below is the SAME procedure the animation traces, just written in Dart; the explicit-stack printing version is included too, cross-checked against a plain recursive traversal in verify/c10.dart.Three more tree facts as code. Printing every node recursively and listing the children of a node; the space claim (2n pointers for left-child/right-sibling against n·d child slots in the naive layout, where d is the largest number of children); and a parent-pointer walk that prints a binary tree in O(n) with no stack and no recursion:
Two pointers and ONE boolean per node: link is the next sibling when isSibling is true and the parent when it is false (only the last child has no next sibling, so its slot is free to hold the parent):
Input size → what is feasible: n ≤ 105 nodes → building and printing are O(n); the recursive print needs one stack frame per level, so a path-shaped tree deeper than about 104 overflows — use the explicit stack above. A node with 105 children is fine for left-child/right-sibling (2 pointers) but would need 105 slots in the naive layout.
leftChild points DOWN a generation (to a child), but rightSibling points ACROSS the same generation (to another child of the same parent) — it never points to a grandchild. Tracing the diagram slowly, generation by generation, is the fastest way to stop confusing them.parent(i) = (i − 1) ~/ 2 for 0-indexed arrays). A union-find forest (see the disjoint-sets lesson) only ever needs to walk UPWARD, so each node keeps a single parent pointer and nothing else. The right representation always follows from which directions you actually need to travel.5. Choosing a list design & random-jump search
Which list should you build? The choices that matter are: does the list keep a tail pointer, does each node carry a prev pointer, and is there a circular sentinel? The table gives the cost of six operations on n nodes for four designs (“hold x” means you already have a pointer to node x). Reading it is a quick way to see WHY each extra pointer costs memory in exchange for speed:
| Singly (head only) | Singly + tail | Doubly (head + tail) | Circular doubly + sentinel | |
|---|---|---|---|---|
| pushFront(x) | O(1) | O(1) | O(1) | O(1) |
| pushBack(x) | O(n) | O(1) | O(1) | O(1) |
| popFront() | O(1) | O(1) | O(1) | O(1) |
| popBack() | O(n)† | O(n)† | O(1) | O(1) |
| remove(x), hold x | O(n)† | O(n)† | O(1) | O(1) |
| search(k) | Θ(n) | Θ(n) | Θ(n) | Θ(n) |
† Unlinking a node needs its predecessor, and a singly linked node cannot look backward: the only way to find the predecessor is a scan from the head. A tail pointer fixes pushBack (you know where the end is) but not popBack (you still need the node BEFORE the tail). In the circular sentinel form the last node is nil.prev, so both ends are reachable in O(1).
The singly linked costs as code: pushBack without a tail pointer walks to the last node (Θ(n)), popBack walks to the node before the last (Θ(n)) even when a tail pointer exists, and removing a held node walks to its predecessor. Each method returns the number of nodes walked. A queue with head AND tail pointers (above) enqueues with no walk at all, and the doubly linked list removes a held node with two pointer writes:
Input size → what is feasible: n ≤ 104 nodes → a Theta(n) walk is 104 steps per call (108 for 104 calls); for n = 106 use the doubly linked list (O(1) removal) or a hash table.
Random-jump search is the one genuinely new algorithmic idea in this lesson: a SORTED singly linked list stored compactly in arrays key[]/next[] can be searched faster than the obvious Θ(n) walk, using nothing but occasional random jumps.
randomJumpSearch(key, next, head, k): slot holding k in a sorted list, or NIL 1 i ← head 2 while i ≠ NIL and key[i] < k: 3 j ← random slot in 0..n − 1 4 if key[i] < key[j] and key[j] ≤ k: // j is ahead of i but not past k 5 i ← j 6 if key[i] = k: return i 7 i ← next[i] 8 if i ≠ NIL and key[i] = k: return i 9 return NIL
key[]/next[] with head as the first slot and next[i] == -1 marking the end (plain Dart ints have no null-as-zero convention). The random slot is rng.nextInt(n) (0..n−1), and the Random generator is passed in explicitly so a test can seed it for determinism. The code matches the listing line for line.The expected-time claim as code: count the iterations of the loop over many seeded runs (the target is the last key, the worst case for a walk). The measured average is about 1.2–1.3 · √n (n = 106 → about 1300 iterations against 106 for a plain walk), and the t + n/t trade-off is smallest at t = √n:
Input size → what is feasible: n ≤ 106 keys, 104 searches → a plain walk is 1010 steps in total, random-jump search about 1.3·107; for much larger n or frequent updates use a tree or hash table (later lessons).
k (key[j] ≤ k), but line 7 then runs i ← next[i] unconditionally, which would step one node past the answer, and line 8 would answer NIL for a key that is present. So right after every jump, line 6 checks key[i] = k and returns at once. (Forbidding the jump from landing on k by writing key[j] < k would also be correct, but then the walk itself has to find k.)Quiz
Interview questions
Cheat sheet
| Structure | Search | Insert | Delete | Space | When to use |
|---|---|---|---|---|---|
| Array stack | — | O(1) push | O(1) pop | O(n) | LIFO: undo history, call stack, DFS, balanced-bracket checks |
| Circular-array queue | — | O(1) enqueue | O(1) dequeue | O(n) | FIFO: task scheduling, BFS, producer/consumer buffers |
| Doubly linked list (sentinel) | Θ(n) | O(1) at known node | O(1) at known node | O(n) + 1 sentinel | Frequent mid-list splicing; LRU cache's recency order |
| Parallel arrays + free list | — | O(1) allocate | O(1) free | O(n) fixed pool | Simulating pointers/objects in array-only languages |
| Left-child, right-sibling tree | O(n) walk | O(1) at known parent | O(children) | Θ(n) | Arbitrary branching factor (file systems, org charts, DOM) |
| Compact sorted list + random jumps | O(√n) expected | — | — | O(n) | Read-mostly sorted data too small to justify a tree/hash table |