data-structures

Custom Data Structures (JavaScript)

Complexity and code characteristics

Choose a structure for the property you need to control — not only for speed.

Big-O (typical; n = size, k = key/word length):

• Singly-linked push/pop at head: O(1); search / index: O(n)
• Doubly-linked append/prepend / splice at known node: O(1); index: O(n) (nearer-end walk helps)
• Cons prepend / uncons: O(1); reverse / map / random access: O(n); tails share structure
• CircularBuffer / Queue / Deque / Stack ends: amortized O(1); grow rare O(n); never hot Array.shift
• UnrolledList enqueue/dequeue: amortized O(1); better locality than per-item nodes; pool cuts allocs
• BST insert/search: O(log n) balanced, O(n) skewed; in-order: O(n)
• Binary heap push/pop: O(log n); peek: O(1)
• Trie insert/has: O(k); autocomplete: O(matches × k)
• Adjacency-list addEdge: O(1); BFS/DFS: O(V + E)
• LRU (Map) get/set/evict: O(1); G-Counter inc O(1), merge O(replicas); Pool capture O(1) amortized
• Prefer the structure whose hot operation is O(1) or O(log n); measure before optimizing rare paths

Readability and semantics:

• Name by role: pending (Queue), frontier (Deque), undo (Stack) — not buffer1
• Type states intent: ring/unrolled = throughput; cons = persistent; heap = priority; trie = prefix
• Small public API (enqueue/dequeue) — do not expose nodes or buffers

Stability and contracts:

• Return copies or iterators; document live vs snapshot and iteration order
• Cap growth (capacity, pool size, LRU max); unbounded queues/caches are operability bugs
• Immutable Cons/Struct: updates are new values (prepend, fork); mutable lists document aliasing

Testability:

• Assert on contents ([...q], toArray(), size), not private fields; keep Symbol.iterator
• Deterministic fixtures; inject clocks/timeouts for Pool waiters

Encapsulation and cost:

• Hide representation so callers survive swaps (array → ring → unrolled)
• Amortized grow and node pools trade memory for latency; clear slots on dequeue for GC
• Power-of-2 ring capacity; index with & (len - 1) instead of %