15.05Beginner / Intermediate8 topics25 min8 interactive animations

Building structures from scratch

Compact reference implementations of the eight core structures: dynamic array, linked list, queue, stack, hash table, binary search tree, binary heap and trie, each compiled and tested against the JDK.

Learning goals

Write each structure from scratch with its invariants in mind
Relate every operation to its cost in the previous lessons
Test a homemade structure against the JDK collection it imitates

Prerequisites

Everything in Part II so far

15.05.1

Dynamic array

A dynamic array keeps an int[] plus a size. add doubles the array when it is full (copying costs O(n) but happens after n/2 insertions, so it is O(1) amortised); inserting or removing in the middle shifts the tail with System.arraycopy. get is a bounds check and an index.

Java

1class DynamicArray {
2    private int[] data = new int[4];
3    private int size;
4    int size() { return size; }
5    int get(int i) {
6        if (i < 0 || i >= size) throw new IndexOutOfBoundsException("index " + i + ", size " + size);
7        return data[i];
8    }
9    void add(int value) { add(size, value); }
10    void add(int index, int value) {
11        if (index < 0 || index > size) throw new IndexOutOfBoundsException("index " + index + ", size " + size);
12        if (size == data.length) data = Arrays.copyOf(data, data.length * 2);        // amortised O(1)
13        System.arraycopy(data, index, data, index + 1, size - index);                // shift the tail right
14        data[index] = value;
15        size++;
16    }
17    int removeAt(int index) {
18        if (index < 0 || index >= size) throw new IndexOutOfBoundsException("index " + index + ", size " + size);
19        int old = data[index];
20        System.arraycopy(data, index + 1, data, index, size - index - 1);            // shift the tail left
21        size--;
22        return old;
23    }
24}

Best

O(1)

Average

O(1) amortised append, O(n) middle

Worst

O(n)

Space

O(n)

Dynamic array: capacity, growth and shrinking

Interactive · edit the input

size elements in the buffer · length 0

Used slot (size)Spare capacity

data[] · capacity 1

Setup

A new dynamic array starts with capacity 1 and no elements.

Step 1 / 21

Java

1void add(int x) {
2    if (size == data.length) {                        // buffer is full
3        data = Arrays.copyOf(data, newCapacity());     // allocate bigger, copy size elements
4    }
5    data[size++] = x;
6}
7int removeLast() {
8    int x = data[--size];
9    if (size <= data.length / 4) data = Arrays.copyOf(data, Math.max(1, data.length / 2));   // optional shrink
10    return x;
11}

Live state

0 copies0 resizes

size

capacity

No condition evaluated on this step

Execution trace (dry run table)Show 21 steps

Step	Line	State	What happens
1	L1	size=0 capacity=1	A new dynamic array starts with capacity 1 and no elements.
2	L2	size=0 capacity=1 x=4	size 0 < capacity 1: there is a spare slot, so adding is O(1).
3	L5	size=1 capacity=1 x=4	Write 4 into data[0] and increase size to 1.
4	L2	size=1 capacity=1 x=8	size 1 equals capacity 1: no room for 8, so the buffer must grow.
5	L3	size=1 capacity=2	Allocate capacity 2 and copy the 1 element (1 copy so far).
6	L5	size=2 capacity=2 x=8	Write 8 into data[1] and increase size to 2.
7	L2	size=2 capacity=2 x=15	size 2 equals capacity 2: no room for 15, so the buffer must grow.
8	L3	size=2 capacity=4	Allocate capacity 4 and copy the 2 elements (3 copys so far).
9	L5	size=3 capacity=4 x=15	Write 15 into data[2] and increase size to 3.
10	L2	size=3 capacity=4 x=16	size 3 < capacity 4: there is a spare slot, so adding is O(1).
11	L5	size=4 capacity=4 x=16	Write 16 into data[3] and increase size to 4.
12	L2	size=4 capacity=4 x=23	size 4 equals capacity 4: no room for 23, so the buffer must grow.
13	L3	size=4 capacity=8	Allocate capacity 8 and copy the 4 elements (7 copys so far).
14	L5	size=5 capacity=8 x=23	Write 23 into data[4] and increase size to 5.
15	L2	size=5 capacity=8 x=42	size 5 < capacity 8: there is a spare slot, so adding is O(1).
16	L5	size=6 capacity=8 x=42	Write 42 into data[5] and increase size to 6.
17	L2	size=6 capacity=8 x=7	size 6 < capacity 8: there is a spare slot, so adding is O(1).
18	L5	size=7 capacity=8 x=7	Write 7 into data[6] and increase size to 7.
19	L2	size=7 capacity=8 x=9	size 7 < capacity 8: there is a spare slot, so adding is O(1).
20	L5	size=8 capacity=8 x=9	Write 9 into data[7] and increase size to 8.
21	L11	size=8 capacity=8 copies=7	Final: size 8, capacity 8 (0 spare slots), 3 resizes that copied 7 elements in total. Doubling keeps total copies below 2n.

15.05.2

Linked list

A singly linked list with head and tail references. Adding at either end and removing the first node are O(1); get(i) and removing by value walk the list. The two classic mistakes are forgetting to set tail when the first node is added and forgetting to reset it when the last node is removed.

Java

1class SinglyLinkedList {
2    private static class Node { int val; Node next; Node(int v) { val = v; } }
3    private Node head, tail;
4    private int size;
5    int size() { return size; }
6    void addFirst(int v) {
7        Node n = new Node(v);
8        n.next = head; head = n;
9        if (tail == null) tail = n;                          // first node: also the tail
10        size++;
11    }
12    void addLast(int v) {
13        Node n = new Node(v);
14        if (tail == null) head = n; else tail.next = n;
15        tail = n;
16        size++;
17    }
18    int removeFirst() {
19        if (head == null) throw new NoSuchElementException();
20        int v = head.val;
21        head = head.next;
22        if (head == null) tail = null;                       // the list became empty
23        size--;
24        return v;
25    }
26    int get(int index) {
27        if (index < 0 || index >= size) throw new IndexOutOfBoundsException("index " + index + ", size " + size);
28        Node n = head;
29        for (int i = 0; i < index; i++) n = n.next;          // O(n): walk from the head
30        return n.val;
31    }
32    boolean removeValue(int v) {                             // first occurrence
33        Node prev = null;
34        for (Node cur = head; cur != null; prev = cur, cur = cur.next) {
35            if (cur.val != v) continue;
36            if (prev == null) head = cur.next; else prev.next = cur.next;
37            if (cur == tail) tail = prev;                    // removed the last node
38            size--;
39            return true;
40        }
41        return false;
42    }
43}

Best

O(1)

Average

O(n) for get/remove by value

Worst

O(n)

Space

O(n)

Singly linked list: insert and delete

Interactive · edit the input

linked list · 4 nodes

null

head

curr / prevNew nodeUnlinked node (garbage)Match

Setup

Insert at index. A node holds a value and a reference to the next node; the list is reached only through head.

Step 1 / 7

Java

1class Node { int val; Node next; Node(int v) { val = v; } }
2static Node insertHead(Node head, int v) { Node n = new Node(v); n.next = head; return n; }          // O(1)
3static Node insertTail(Node head, int v) {                                  // O(n) without a tail pointer
4    Node n = new Node(v);
5    if (head == null) return n;
6    Node cur = head; while (cur.next != null) cur = cur.next;                // walk to the last node
7    cur.next = n; return head;
8}
9static Node insertAt(Node head, int index, int v) {                         // O(index)
10    if (index == 0) return insertHead(head, v);
11    Node prev = head; for (int i = 0; i < index - 1; i++) prev = prev.next;   // stop at the node before the gap
12    Node n = new Node(v); n.next = prev.next; prev.next = n; return head;     // link the new node first, then splice it in
13}
14static Node deleteHead(Node head) { return head == null ? null : head.next; }                       // O(1)
15static Node deleteTail(Node head) {
16    if (head == null || head.next == null) return null;
17    Node cur = head; while (cur.next.next != null) cur = cur.next;           // stop at the second-to-last node
18    cur.next = null; return head;
19}
20static Node deleteValue(Node head, int x) {
21    if (head == null) return null;  if (head.val == x) return head.next;
22    Node cur = head; while (cur.next != null && cur.next.val != x) cur = cur.next;
23    if (cur.next != null) cur.next = cur.next.next;                          // bypass: the old node becomes garbage
24    return head;
25}

Live state

length

head

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L1	length=4 head=10	Insert at index. A node holds a value and a reference to the next node; the list is reached only through head.
2	L11	length=4 head=10 i=0	Walk 1 step to reach the node before position 2.
3	L11	length=4 head=10 i=1	prev = 20.
4	L12	length=5 head=10	Create node 25; it is not linked yet.
5	L12	length=5 head=10	n.next = prev.next: link the new node to the rest of the list FIRST, otherwise the rest would be lost.
6	L12	length=5 head=10	prev.next = n: splice the new node in. Only two references changed; nothing was shifted.
7	L12	return=[10, 20, 25, 30, 40]	Inserted 25 at index 2: [10, 20, 25, 30, 40]. Cost is the walk, O(index).

15.05.3

Queue

A growable circular queue: head is the index of the front, size counts the values, and the next free slot is (head + size) % length. When full, grow copies the values into a bigger array in front-to-back order and resets head to 0, which also removes the wrap-around.

Java

1class RingQueue {
2    private int[] data = new int[4];
3    private int head, size;
4    boolean isEmpty() { return size == 0; }
5    void offer(int x) {
6        if (size == data.length) grow();
7        data[(head + size) % data.length] = x;               // the slot just after the last value
8        size++;
9    }
10    int poll() {
11        if (size == 0) throw new NoSuchElementException();
12        int x = data[head];
13        head = (head + 1) % data.length;                     // wrap around
14        size--;
15        return x;
16    }
17    int peek() {
18        if (size == 0) throw new NoSuchElementException();
19        return data[head];
20    }
21    private void grow() {
22        int[] bigger = new int[data.length * 2];
23        for (int i = 0; i < size; i++) bigger[i] = data[(head + i) % data.length];   // unwrap into order
24        data = bigger;
25        head = 0;
26    }
27}

Best

O(1)

Average

O(1) amortised

Worst

O(n) at a resize

Space

O(n)

Circular queue: head, tail and a size counter

Interactive · edit the input

data[4] · head 0 · tail 0 · size 0

0 HT

Setup

An array of 4. head is where the next value leaves, tail is where the next value arrives, size counts the values.

Step 1 / 29

Java

1class RingQueue {
2    private final int[] data; private int head, tail, size;
3    RingQueue(int capacity) { data = new int[capacity]; }
4    boolean offer(int x) {
5        if (size == data.length) return false;              // full
6        data[tail] = x;
7        tail = (tail + 1) % data.length;                   // wrap around
8        size++; return true;
9    }
10    Integer poll() {
11        if (size == 0) return null;                         // empty
12        int x = data[head];
13        head = (head + 1) % data.length;                   // wrap around
14        size--; return x;
15    }
16}

Live state

head

tail

size

No condition evaluated on this step

Execution trace (dry run table)Show 29 steps

Step	Line	State	What happens
1	L2	head=0 tail=0 size=0	An array of 4. head is where the next value leaves, tail is where the next value arrives, size counts the values.
2	L5	head=0 tail=0 size=0 op=offer(1)	offer(1): there is room.
3	L6	head=0 tail=0 size=1 op=offer(1)	data[0] = 1.
4	L7	head=0 tail=1 size=1 op=offer(1)	tail = (0 + 1) % 4 = 1.
5	L5	head=0 tail=1 size=1 op=offer(2)	offer(2): there is room.
6	L6	head=0 tail=1 size=2 op=offer(2)	data[1] = 2.
7	L7	head=0 tail=2 size=2 op=offer(2)	tail = (1 + 1) % 4 = 2.
8	L5	head=0 tail=2 size=2 op=offer(3)	offer(3): there is room.
9	L6	head=0 tail=2 size=3 op=offer(3)	data[2] = 3.
10	L7	head=0 tail=3 size=3 op=offer(3)	tail = (2 + 1) % 4 = 3.
11	L11	head=0 tail=3 size=3 op=poll()	poll(): there is a value at head.
12	L12	head=0 tail=3 size=3 op=poll() returned=1	x = data[0] = 1. The slot keeps its old number (shown struck out when free): only head and size decide what is live.
13	L13	head=1 tail=3 size=2 op=poll() returned=1	head = (0 + 1) % 4 = 1. Returned 1.
14	L11	head=1 tail=3 size=2 op=poll()	poll(): there is a value at head.
15	L12	head=1 tail=3 size=2 op=poll() returned=2	x = data[1] = 2. The slot keeps its old number (shown struck out when free): only head and size decide what is live.
16	L13	head=2 tail=3 size=1 op=poll() returned=2	head = (1 + 1) % 4 = 2. Returned 2.
17	L5	head=2 tail=3 size=1 op=offer(4)	offer(4): there is room.
18	L6	head=2 tail=3 size=2 op=offer(4)	data[3] = 4.
19	L7	head=2 tail=0 size=2 op=offer(4)	tail = (3 + 1) % 4 = 0: past the last index, so it wraps to the start of the array.
20	L5	head=2 tail=0 size=2 op=offer(5)	offer(5): there is room.
21	L6	head=2 tail=0 size=3 op=offer(5)	data[0] = 5.
22	L7	head=2 tail=1 size=3 op=offer(5)	tail = (0 + 1) % 4 = 1.
23	L5	head=2 tail=1 size=3 op=offer(6)	offer(6): there is room.
24	L6	head=2 tail=1 size=4 op=offer(6)	data[1] = 6.
25	L7	head=2 tail=2 size=4 op=offer(6)	tail = (1 + 1) % 4 = 2.
26	L11	head=2 tail=2 size=4 op=poll()	poll(): there is a value at head.
27	L12	head=2 tail=2 size=4 op=poll() returned=3	x = data[2] = 3. The slot keeps its old number (shown struck out when free): only head and size decide what is live.
28	L13	head=3 tail=2 size=3 op=poll() returned=3	head = (2 + 1) % 4 = 3. Returned 3.
29	L16	head=3 tail=2 size=3 return=[4, 5, 6]	Queue contents from head: [4, 5, 6]; 0 operations rejected.

15.05.4

Stack

An array stack: push writes at size and increments it, pop decrements and reads. The array doubles when it is full. peek reads the top without removing it. Both underflow cases throw, like java.util.Stack.

Java

1class ArrayStack {
2    private int[] data = new int[4];
3    private int size;
4    boolean isEmpty() { return size == 0; }
5    void push(int x) {
6        if (size == data.length) data = Arrays.copyOf(data, size * 2);
7        data[size++] = x;
8    }
9    int pop() {
10        if (size == 0) throw new EmptyStackException();
11        return data[--size];
12    }
13    int peek() {
14        if (size == 0) throw new EmptyStackException();
15        return data[size - 1];
16    }
17}

Best

O(1)

Average

O(1) amortised

Worst

O(n) at a resize

Space

O(n)

Array-backed stack: push, pop, peek, overflow and underflow

Interactive · edit the input

data[] · capacity 3 · size 0

Setup

An empty stack backed by an array of 3. The top is data[size - 1]; push and pop only touch the end, so both are O(1).

Step 1 / 11

Java

1class ArrayStack {
2    private int[] data; private int size;
3    ArrayStack(int capacity) { data = new int[capacity]; }
4    void push(int x) {
5        if (size == data.length) data = Arrays.copyOf(data, data.length * 2);   // resizable; a fixed stack rejects instead
6        data[size++] = x;
7    }
8    int pop() {
9        if (size == 0) throw new NoSuchElementException("stack underflow");
10        return data[--size];
11    }
12    int peek() {
13        if (size == 0) throw new NoSuchElementException("stack underflow");
14        return data[size - 1];                      // look without removing
15    }
16    boolean isEmpty() { return size == 0; }
17}

Live state

size

capacity

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L3	size=0 capacity=3	An empty stack backed by an array of 3. The top is data[size - 1]; push and pop only touch the end, so both are O(1).
2	L6	op=push(5) size=1 top=5	data[size++] = 5: 5 is the new top.
3	L6	op=push(8) size=2 top=8	data[size++] = 8: 8 is the new top.
4	L6	op=push(3) size=3 top=3	data[size++] = 3: 3 is the new top.
5	L14	op=peek() top=3 size=3	peek() returns 3 without removing it: size stays 3.
6	L10	op=pop() returned=3 size=2	Return data[--size] = 3: the most recently pushed value leaves first (LIFO). The slot is simply ignored from now on.
7	L10	op=pop() returned=8 size=1	Return data[--size] = 8: the most recently pushed value leaves first (LIFO). The slot is simply ignored from now on.
8	L10	op=pop() returned=5 size=0	Return data[--size] = 5: the most recently pushed value leaves first (LIFO). The slot is simply ignored from now on.
9	L9	op=pop() size=0 errors=1	pop() on an empty stack: underflow. Java's ArrayDeque.pop throws NoSuchElementException; poll() would return null.
10	L6	op=push(7) size=1 top=7	data[size++] = 7: 7 is the new top.
11	L16	size=1 errors=1 return=[7]	Final stack (bottom to top): [7]; 1 rejected operation.

15.05.5

Hash table

A generic hash map with separate chaining, a power-of-two table, Java's bit-spreading index and a resize at load factor 0.75. put replaces the value of an existing key and returns the old one, like java.util.HashMap. resize relinks the existing entries into the new table instead of allocating new ones.

Java

1class MyHashMap<K, V> {
2    private static class Entry<K, V> {
3        final K key; V value; Entry<K, V> next;
4        Entry(K k, V v, Entry<K, V> n) { key = k; value = v; next = n; }
5    }
6    private Entry<K, V>[] table = newTable(16);
7    private int size;
8    @SuppressWarnings("unchecked")
9    private static <K, V> Entry<K, V>[] newTable(int n) { return (Entry<K, V>[]) new Entry[n]; }
10    private int index(Object key, int length) {
11        int h = key == null ? 0 : key.hashCode();
12        return (h ^ (h >>> 16)) & (length - 1);              // length is a power of two
13    }
14    int size() { return size; }
15    V get(Object key) {
16        for (Entry<K, V> e = table[index(key, table.length)]; e != null; e = e.next)
17            if (Objects.equals(e.key, key)) return e.value;
18        return null;
19    }
20    V put(K key, V value) {
21        int i = index(key, table.length);
22        for (Entry<K, V> e = table[i]; e != null; e = e.next)
23            if (Objects.equals(e.key, key)) { V old = e.value; e.value = value; return old; }
24        table[i] = new Entry<>(key, value, table[i]);        // new entry at the head of its chain
25        if (++size > table.length * 3 / 4) resize();         // load factor 0.75
26        return null;
27    }
28    V remove(Object key) {
29        int i = index(key, table.length);
30        Entry<K, V> prev = null;
31        for (Entry<K, V> e = table[i]; e != null; prev = e, e = e.next) {
32            if (!Objects.equals(e.key, key)) continue;
33            if (prev == null) table[i] = e.next; else prev.next = e.next;
34            size--;
35            return e.value;
36        }
37        return null;
38    }
39    private void resize() {
40        Entry<K, V>[] old = table;
41        table = newTable(old.length * 2);
42        for (Entry<K, V> head : old)
43            for (Entry<K, V> e = head; e != null; ) {
44                Entry<K, V> next = e.next;
45                int i = index(e.key, table.length);
46                e.next = table[i]; table[i] = e;             // relink the same node: no allocation
47                e = next;
48            }
49    }
50}

Best

O(1)

Average

O(1) expected, amortised on put

Worst

O(n)

Space

O(n)

Load factor and rehashing

Interactive · edit the input

table · 2 buckets

∅0

∅1

Setup

2 empty buckets and a maximum load factor of 0.75: the table doubles as soon as size > 0.75 × buckets.

Step 1 / 31

Java

1class ChainedSet {
2    private LinkedList<Integer>[] table; private int size; private final double maxLoad;
3    void add(int key) {
4        int b = Math.floorMod(key, table.length);
5        if (table[b].contains(key)) return;                          // already present
6        table[b].add(key); size++;
7        if (size > maxLoad * table.length) resize();                 // load factor too high
8    }
9    private void resize() {
10        LinkedList<Integer>[] old = table;
11        table = newTable(old.length * 2);                            // double the number of buckets
12        for (LinkedList<Integer> chain : old)
13            for (int key : chain) table[Math.floorMod(key, table.length)].add(key);   // every key is rehashed
14    }
15}

Live state

0 resizes0 keys moved

size

buckets

load factor

0.00

limit

0.75

No condition evaluated on this step

Execution trace (dry run table)Show 31 steps

Step	Line	State	What happens
1	L2	size=0 buckets=2 load factor=0.00 limit=0.75	2 empty buckets and a maximum load factor of 0.75: the table doubles as soon as size > 0.75 × buckets.
2	L4	size=0 buckets=2 load factor=0.00 limit=0.75 key=5 bucket=1	add(5): 5 % 2 = 1.
3	L7	size=1 buckets=2 load factor=0.50 limit=0.75 key=5	Added 5: 1 ≤ 1.5, no resize yet.
4	L4	size=1 buckets=2 load factor=0.50 limit=0.75 key=12 bucket=0	add(12): 12 % 2 = 0.
5	L7	size=2 buckets=2 load factor=1.00 limit=0.75 key=12	Added 12: 2 keys exceed the limit 1.5, so the table must grow.
6	L11	size=2 buckets=2 load factor=1.00 limit=0.75 new buckets=4	Allocate a new array of 4 buckets. Bucket indices depend on the table size, so every key must be hashed again.
7	L13	size=2 buckets=2 load factor=1.00 limit=0.75 moving from=0 new buckets=4	Rehash bucket 0 (12): each key goes to key % 4. Keys that collided before often separate now.
8	L13	size=2 buckets=2 load factor=1.00 limit=0.75 moving from=1 new buckets=4	Rehash bucket 1 (5): each key goes to key % 4. Keys that collided before often separate now.
9	L14	size=2 buckets=4 load factor=0.50 limit=0.75	Resize done: 4 buckets, load factor 0.50. Cost: O(n) now, but it happens after the table has doubled, so adding is O(1) amortised.
10	L4	size=2 buckets=4 load factor=0.50 limit=0.75 key=9 bucket=1	add(9): 9 % 4 = 1.
11	L7	size=3 buckets=4 load factor=0.75 limit=0.75 key=9	Added 9: 3 ≤ 3, no resize yet.
12	L4	size=3 buckets=4 load factor=0.75 limit=0.75 key=20 bucket=0	add(20): 20 % 4 = 0.
13	L7	size=4 buckets=4 load factor=1.00 limit=0.75 key=20	Added 20: 4 keys exceed the limit 3, so the table must grow.
14	L11	size=4 buckets=4 load factor=1.00 limit=0.75 new buckets=8	Allocate a new array of 8 buckets. Bucket indices depend on the table size, so every key must be hashed again.
15	L13	size=4 buckets=4 load factor=1.00 limit=0.75 moving from=0 new buckets=8	Rehash bucket 0 (12, 20): each key goes to key % 8. Keys that collided before often separate now.
16	L13	size=4 buckets=4 load factor=1.00 limit=0.75 moving from=1 new buckets=8	Rehash bucket 1 (5, 9): each key goes to key % 8. Keys that collided before often separate now.
17	L14	size=4 buckets=8 load factor=0.50 limit=0.75	Resize done: 8 buckets, load factor 0.50. Cost: O(n) now, but it happens after the table has doubled, so adding is O(1) amortised.
18	L4	size=4 buckets=8 load factor=0.50 limit=0.75 key=33 bucket=1	add(33): 33 % 8 = 1.
19	L7	size=5 buckets=8 load factor=0.63 limit=0.75 key=33	Added 33: 5 ≤ 6, no resize yet.
20	L4	size=5 buckets=8 load factor=0.63 limit=0.75 key=7 bucket=7	add(7): 7 % 8 = 7.
21	L7	size=6 buckets=8 load factor=0.75 limit=0.75 key=7	Added 7: 6 ≤ 6, no resize yet.
22	L4	size=6 buckets=8 load factor=0.75 limit=0.75 key=18 bucket=2	add(18): 18 % 8 = 2.
23	L7	size=7 buckets=8 load factor=0.88 limit=0.75 key=18	Added 18: 7 keys exceed the limit 6, so the table must grow.
24	L11	size=7 buckets=8 load factor=0.88 limit=0.75 new buckets=16	Allocate a new array of 16 buckets. Bucket indices depend on the table size, so every key must be hashed again.
25	L13	size=7 buckets=8 load factor=0.88 limit=0.75 moving from=1 new buckets=16	Rehash bucket 1 (9, 33): each key goes to key % 16. Keys that collided before often separate now.
26	L13	size=7 buckets=8 load factor=0.88 limit=0.75 moving from=2 new buckets=16	Rehash bucket 2 (18): each key goes to key % 16. Keys that collided before often separate now.
27	L13	size=7 buckets=8 load factor=0.88 limit=0.75 moving from=4 new buckets=16	Rehash bucket 4 (12, 20): each key goes to key % 16. Keys that collided before often separate now.
28	L13	size=7 buckets=8 load factor=0.88 limit=0.75 moving from=5 new buckets=16	Rehash bucket 5 (5): each key goes to key % 16. Keys that collided before often separate now.
29	L13	size=7 buckets=8 load factor=0.88 limit=0.75 moving from=7 new buckets=16	Rehash bucket 7 (7): each key goes to key % 16. Keys that collided before often separate now.
30	L14	size=7 buckets=16 load factor=0.44 limit=0.75	Resize done: 16 buckets, load factor 0.44. Cost: O(n) now, but it happens after the table has doubled, so adding is O(1) amortised.
31	L15	size=7 buckets=16 load factor=0.44 limit=0.75 return=[[],[33],[18],[],[20],[5],[],[7],[],[9],[],[],[12],[],[],[]]	7 keys in 16 buckets after 3 resizes; 13 key moves spent on rehashing.

15.05.6

BST

A binary search tree of int keys: smaller keys go left, larger go right. insert and contains follow one path; remove handles three cases: a node with no or one child is replaced by that child, and a node with two children takes the key of its in-order successor, which is then removed from the right subtree. An in-order walk returns the keys sorted. Without balancing, sorted input makes the tree a chain with O(n) operations; Chapter 26 (Self-Balancing Search Trees and B-Trees) adds balancing.

Java

1class Bst {
2    private static class Node { int key; Node left, right; Node(int k) { key = k; } }
3    private Node root;
4    void insert(int key) { root = insert(root, key); }
5    private Node insert(Node n, int key) {
6        if (n == null) return new Node(key);
7        if (key < n.key) n.left = insert(n.left, key);
8        else if (key > n.key) n.right = insert(n.right, key);       // equal keys are ignored
9        return n;
10    }
11    boolean contains(int key) {
12        Node n = root;
13        while (n != null) {
14            if (key == n.key) return true;
15            n = key < n.key ? n.left : n.right;
16        }
17        return false;
18    }
19    void remove(int key) { root = remove(root, key); }
20    private Node remove(Node n, int key) {
21        if (n == null) return null;
22        if (key < n.key) n.left = remove(n.left, key);
23        else if (key > n.key) n.right = remove(n.right, key);
24        else {
25            if (n.left == null) return n.right;                      // zero or one child: splice out
26            if (n.right == null) return n.left;
27            Node s = n.right; while (s.left != null) s = s.left;     // two children: in-order successor
28            n.key = s.key;
29            n.right = remove(n.right, s.key);
30        }
31        return n;
32    }
33    List<Integer> inorder() { List<Integer> out = new ArrayList<>(); inorder(root, out); return out; }
34    private void inorder(Node n, List<Integer> out) {
35        if (n == null) return;
36        inorder(n.left, out); out.add(n.key); inorder(n.right, out);
37    }
38}

Best

O(log n)

Average

O(log n)

Worst

O(n) when unbalanced

Space

O(n)

Binary search tree: insert, search, delete and in-order traversal

Interactive · edit the input

Setup

An empty tree. Rule: every key in a node's left subtree is smaller, every key in its right subtree is larger.

Step 1 / 13

Java

1class Bst {
2    private static class Node { int key; Node left, right; Node(int k) { key = k; } }
3    private Node root;
4    void insert(int key) { root = insert(root, key); }
5    private Node insert(Node n, int key) {
6        if (n == null) return new Node(key);                      // found the empty spot
7        if (key < n.key) n.left = insert(n.left, key);
8        else if (key > n.key) n.right = insert(n.right, key);     // equal keys are ignored
9        return n;
10    }
11    boolean contains(int key) {
12        Node n = root;
13        while (n != null) {
14            if (key == n.key) return true;
15            n = key < n.key ? n.left : n.right;                    // discard one whole subtree
16        }
17        return false;
18    }
19    void delete(int key) { root = delete(root, key); }
20    private Node delete(Node n, int key) {
21        if (n == null) return null;                               // key is not in the tree
22        if (key < n.key) n.left = delete(n.left, key);
23        else if (key > n.key) n.right = delete(n.right, key);
24        else {
25            if (n.left == null) return n.right;                    // zero or one child: splice the node out
26            if (n.right == null) return n.left;
27            Node s = n.right; while (s.left != null) s = s.left;   // two children: in-order successor
28            n.key = s.key;                                         // copy its key up
29            n.right = delete(n.right, s.key);                      // then remove the successor
30        }
31        return n;
32    }
33    void inorder(Node n, List<Integer> out) {
34        if (n == null) return;
35        inorder(n.left, out); out.add(n.key); inorder(n.right, out);   // left, node, right: sorted order
36    }
37}

Live state

0 comparisons

size

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L3	size=0	An empty tree. Rule: every key in a node's left subtree is smaller, every key in its right subtree is larger.
2	L6	inserted=50 size=1	Insert 50: the tree is empty, so it becomes the root.
3	L7	inserted=30 size=2	Insert 30: compared with 50, it ends as the left child of 50.
4	L8	inserted=70 size=3	Insert 70: compared with 50, it ends as the right child of 50.
5	L7	inserted=20 size=4	Insert 20: compared with 50 → 30, it ends as the left child of 30.
6	L8	inserted=40 size=5	Insert 40: compared with 50 → 30, it ends as the right child of 30.
7	L7	inserted=60 size=6	Insert 60: compared with 50 → 70, it ends as the left child of 70.
8	L8	inserted=80 size=7	Insert 80: compared with 50 → 70, it ends as the right child of 70.
9	L12	key=60 size=7	Search for 60: start at the root.
10	L14	key=60 node=50 steps=1	60 > 50: go right; the whole left subtree is ruled out.
11	L14	key=60 node=70 steps=2	60 < 70: go left; the whole right subtree is ruled out.
12	L14	key=60 node=60 steps=3	60 == 60: found after 3 comparisons.
13	L14	return=true steps=3	contains(60) = true in 3 steps; the tree has 7 keys, so most of them were never looked at.

15.05.7

Binary heap

A min-heap stored in an array: the children of index i are 2i + 1 and 2i + 2, and every parent is at most its children. add appends and sifts up; poll moves the last element to the root and sifts down. Ties never swap, which gives the same array layout as java.util.PriorityQueue for the same sequence of operations.

Java

1class MinHeap {
2    private int[] a = new int[8];
3    private int size;
4    int size() { return size; }
5    void add(int x) {
6        if (size == a.length) a = Arrays.copyOf(a, size * 2);
7        a[size] = x;
8        siftUp(size++);
9    }
10    int peek() {
11        if (size == 0) throw new NoSuchElementException();
12        return a[0];
13    }
14    int poll() {
15        if (size == 0) throw new NoSuchElementException();
16        int top = a[0];
17        a[0] = a[--size];                                    // last element to the root
18        if (size > 0) siftDown(0);
19        return top;
20    }
21    private void siftUp(int i) {
22        while (i > 0) {
23            int p = (i - 1) / 2;
24            if (a[i] >= a[p]) break;                         // ties do not move
25            swap(i, p); i = p;
26        }
27    }
28    private void siftDown(int i) {
29        while (true) {
30            int l = 2 * i + 1, r = l + 1, m = i;
31            if (l < size && a[l] < a[m]) m = l;
32            if (r < size && a[r] < a[m]) m = r;
33            if (m == i) return;
34            swap(i, m); i = m;
35        }
36    }
37    private void swap(int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
38    int[] snapshot() { return Arrays.copyOf(a, size); }
39}

Best

O(1) peek

Average

O(log n)

Worst

O(log n)

Space

O(n)

PriorityQueue: offer, poll and peek on a binary heap

Interactive · edit the input

The heap is empty.

int[] arr · length 0

Being comparedJust movedRoot (next to leave)

polled so far (in order)

none yet

Setup

An empty min-queue. It is a binary heap stored in an array: the children of index i are 2i+1 and 2i+2.

Step 1 / 26

Java

1Comparator<Integer> cmp = Comparator.naturalOrder();   // Comparator.reverseOrder() makes a max-queue
2PriorityQueue<Integer> pq = new PriorityQueue<>(cmp);
3pq.offer(x);              // append at the end, then sift up
4Integer top = pq.poll();  // last element to the root, then sift down
5Integer next = pq.peek(); // the root only; nothing is removed

Live state

0 comparisons0 heap swaps

size

order

min first

No condition evaluated on this step

Execution trace (dry run table)Show 26 steps

Step	Line	State	What happens
1	L2	size=0 order=min first	An empty min-queue. It is a binary heap stored in an array: the children of index i are 2i+1 and 2i+2.
2	L3	op=offer(5) size=1	offer(5): append at the end (index 0), the only place that keeps the tree complete.
3	L3	op=offer(3) size=2	offer(3): append at the end (index 1), the only place that keeps the tree complete.
4	L3	op=offer(3) child=3 parent=5	The child has higher priority than its parent, so they swap.
5	L3	op=offer(3)	Swapped: 3 moves up to index 0.
6	L3	op=offer(8) size=3	offer(8): append at the end (index 2), the only place that keeps the tree complete.
7	L3	op=offer(8) child=8 parent=3	The parent keeps priority over the child (ties do not swap): sift up stops.
8	L3	op=offer(1) size=4	offer(1): append at the end (index 3), the only place that keeps the tree complete.
9	L3	op=offer(1) child=1 parent=5	The child has higher priority than its parent, so they swap.
10	L3	op=offer(1)	Swapped: 1 moves up to index 1.
11	L3	op=offer(1) child=1 parent=3	The child has higher priority than its parent, so they swap.
12	L3	op=offer(1)	Swapped: 1 moves up to index 0.
13	L4	op=poll() returned=1 size=3	poll() returns the root 1. The last element (5) moves to the root to fill the gap, then sifts down.
14	L4	op=poll() node=5 better child=3	The better child (3) beats the node, so they swap.
15	L4	op=poll()	Swapped: 3 moves up to index 0.
16	L3	op=offer(4) size=4	offer(4): append at the end (index 3), the only place that keeps the tree complete.
17	L3	op=offer(4) child=4 parent=5	The child has higher priority than its parent, so they swap.
18	L3	op=offer(4)	Swapped: 4 moves up to index 1.
19	L3	op=offer(4) child=4 parent=3	The parent keeps priority over the child (ties do not swap): sift up stops.
20	L4	op=poll() returned=3 size=3	poll() returns the root 3. The last element (5) moves to the root to fill the gap, then sifts down.
21	L4	op=poll() node=5 better child=4	The better child (4) beats the node, so they swap.
22	L4	op=poll()	Swapped: 4 moves up to index 0.
23	L4	op=poll() returned=4 size=2	poll() returns the root 4. The last element (8) moves to the root to fill the gap, then sifts down.
24	L4	op=poll() node=8 better child=5	The better child (5) beats the node, so they swap.
25	L4	op=poll()	Swapped: 5 moves up to index 0.
26	L5	size=2 return=[5, 8]	Heap array: [5, 8]. Only the root is guaranteed to be the best value; the rest is just heap-ordered, not sorted.

15.05.8

Trie

A trie for lowercase words: each node has 26 child slots and an end flag. insert creates missing edges and marks the last node; contains requires the path to exist and end at a marked node; startsWith only requires the path. Every operation costs O(length of the word), independent of how many words are stored. The price is memory: a node with a 26-slot child array measured 144 bytes (24 for the node, 120 for the array).

Java

1class Trie {
2    private static class Node { Node[] next = new Node[26]; boolean end; }
3    private final Node root = new Node();
4    void insert(String word) {
5        Node n = root;
6        for (char c : word.toCharArray()) {
7            if (n.next[c - 'a'] == null) n.next[c - 'a'] = new Node();    // create the missing edge
8            n = n.next[c - 'a'];
9        }
10        n.end = true;                                                      // a word ends here
11    }
12    private Node find(String s) {
13        Node n = root;
14        for (char c : s.toCharArray()) {
15            n = n.next[c - 'a'];
16            if (n == null) return null;                                    // the path breaks
17        }
18        return n;
19    }
20    boolean contains(String word) { Node n = find(word); return n != null && n.end; }
21    boolean startsWith(String prefix) { return find(prefix) != null; }
22}

Best

O(L)

Average

O(L)

Worst

O(L)

Space

O(total characters × 26)

Trie: insert words, then search a word or a prefix

Interactive · edit the input

trie · 1 node

root

Being followedNew nodeMatchMissing edgeA word ends here

Setup

An empty trie: only the root. Each edge is one letter; a word is the path from the root to a node marked as an ending.

Step 1 / 25

Java

1class Trie {
2    private static class Node { Node[] next = new Node[26]; boolean end; }
3    private final Node root = new Node();
4    void insert(String word) {
5        Node n = root;
6        for (char c : word.toCharArray()) {
7            if (n.next[c - 'a'] == null) n.next[c - 'a'] = new Node();    // create the missing edge
8            n = n.next[c - 'a'];
9        }
10        n.end = true;                                                      // a word ends here
11    }
12    private Node find(String s) {
13        Node n = root;
14        for (char c : s.toCharArray()) {
15            n = n.next[c - 'a'];
16            if (n == null) return null;                                    // the path breaks
17        }
18        return n;
19    }
20    boolean contains(String word) { Node n = find(word); return n != null && n.end; }
21    boolean startsWith(String prefix) { return find(prefix) != null; }
22}

Live state

0 nodes created

words

No condition evaluated on this step

Execution trace (dry run table)Show 25 steps

Step	Line	State	What happens
1	L3	words=5	An empty trie: only the root. Each edge is one letter; a word is the path from the root to a node marked as an ending.
2	L7	word=car char=c nodes created=1	insert("car"): there is no 'c' edge below "root", so a new node is created.
3	L7	word=car char=a nodes created=2	insert("car"): there is no 'a' edge below "c", so a new node is created.
4	L7	word=car char=r nodes created=3	insert("car"): there is no 'r' edge below "ca", so a new node is created.
5	L10	word=car new nodes=3	Mark the last node of "car" as a word ending (3 new nodes).
6	L8	word=cart char=c	insert("cart"): the 'c' edge already exists (a shared prefix), so it is reused: no new node.
7	L8	word=cart char=a	insert("cart"): the 'a' edge already exists (a shared prefix), so it is reused: no new node.
8	L8	word=cart char=r	insert("cart"): the 'r' edge already exists (a shared prefix), so it is reused: no new node.
9	L7	word=cart char=t nodes created=4	insert("cart"): there is no 't' edge below "car", so a new node is created.
10	L10	word=cart new nodes=1	Mark the last node of "cart" as a word ending (1 new node).
11	L8	word=cat char=c	insert("cat"): the 'c' edge already exists (a shared prefix), so it is reused: no new node.
12	L8	word=cat char=a	insert("cat"): the 'a' edge already exists (a shared prefix), so it is reused: no new node.
13	L7	word=cat char=t nodes created=5	insert("cat"): there is no 't' edge below "ca", so a new node is created.
14	L10	word=cat new nodes=1	Mark the last node of "cat" as a word ending (1 new node).
15	L7	word=dog char=d nodes created=6	insert("dog"): there is no 'd' edge below "root", so a new node is created.
16	L7	word=dog char=o nodes created=7	insert("dog"): there is no 'o' edge below "d", so a new node is created.
17	L7	word=dog char=g nodes created=8	insert("dog"): there is no 'g' edge below "do", so a new node is created.
18	L10	word=dog new nodes=3	Mark the last node of "dog" as a word ending (3 new nodes).
19	L8	word=do char=d	insert("do"): the 'd' edge already exists (a shared prefix), so it is reused: no new node.
20	L8	word=do char=o	insert("do"): the 'o' edge already exists (a shared prefix), so it is reused: no new node.
21	L10	word=do new nodes=0	Mark the last node of "do" as a word ending (no new nodes were needed: it was a prefix of existing words).
22	L13	query=ca	startsWith("ca"): follow the query letter by letter from the root.
23	L15	query=ca char=c matched=1	'c' edge exists: now at the node for "c".
24	L15	query=ca char=a matched=2	'a' edge exists: now at the node for "ca".
25	L21	return=true	The whole prefix was found: startsWith("ca") = true. Cost: O(2), independent of how many words are stored.

Practice ladder

Now try it yourself

Easy

Implement a stack with an array
Implement Queue using an array

Medium

Design HashMap
Implement Trie (Prefix Tree)

Advanced

Design a hash map with open addressing
Implement a binary heap with a decrease-key operation

Key takeaways

All eight structures are a few dozen lines once the invariants are clear.
Most bugs sit at the boundaries: empty, full, first node, last node, resize.
Test a homemade structure against the JDK class it imitates with random operations.