Data Structure Operations — Go ↔ JS
Average / amortized unless labeled worst. Interview answers usually cite average unless skew/adversarial input is the point.
| Structure | Typical operations | Amortized / average complexity | Go stdlib anchor | JavaScript equivalent |
|---|---|---|---|---|
| Dynamic array | push / pop at end, index read/write | O(1) end; worst O(n) if growth copies | slice built-in | Array (push/pop) |
| Singly linked list | insert-after, delete-next with predecessor | O(1) with pointer; search O(n) | container/list (also doubly) | hand-rolled { value, next } |
| Doubly linked list | insert, delete, splice | O(1) with node ref; index O(n) | container/list | hand-rolled or Map as adjacency (rare) |
| Stack | push, pop, peek | O(1) | slice as stack; list.List | Array as stack (push/pop) |
| Queue / deque | enqueue, dequeue, sometimes both ends | O(1) | container/list; slice ring buffer (custom) | Array (shift is O(n)—use index head or deque pattern) |
| BST (unbalanced) | search, insert, delete | avg O(log n); worst O(n) | no std tree; sort + slice or custom | no std; hand-rolled or npm (not in interview) |
| Balanced BST (concept) | same ops, height bound | worst O(log n) | no built-in; red-black in Tree not std | no std; use SortedMap patterns sparingly |
| Hash map | get, set, delete | avg O(1); worst O(n) | map built-in | Map / plain object (string keys) |
| Binary heap | push, pop min/max | O(log n); build O(n) | container/heap | array + heapify (see JavaScript idioms) |
| Trie | insert, prefix query | O(m) per string length m | no std; custom struct children | nested Map or object children |
| Union-find | find, union | amortized α(n) | no std; custom DSU | custom DSU |
| Segment tree (conceptual) | range query / point update | O(log n) per op | no std; custom | custom (or sparse patterns) |
Notes on “stdlib anchor”
- Go favors slices + maps +
container/list+container/heap; trees and segment trees are almost always custom for interviews. - JavaScript has no native heap, trie, or DSU—express with
Array,Map/Set, and classes.
When to pick which (10 bullets)
- Need order + frequent middle inserts? Doubly linked list (or
container/list); dynamic array shifts are expensive. - Only stack discipline (LIFO)? Slice / array end
push/pop; simplest and cache-friendly. - FIFO queue and
O(1)both ends? Deque pattern (Golistor ring buffer); avoid JSshift()in hot loops. - Keyed lookups dominate? Hash map (
map/Map); tree only if you need sorted keys. - Sorted keys / order statistics? Balanced BST (often simulated by
sort+ binary search on arrays in interviews). - Top-k / streaming extremes? Heap (
container/heap/ array heap). - Prefix / autocomplete strings? Trie (children maps or fixed arrays for small alphabet).
- Components, cycles, Kruskal? Union-find (path compression + union by rank).
- Range sums on static array? Prefix sums; dynamic ranges with updates → segment tree / Fenwick (BIT) conceptually.
- Graph unweighted shortest path? BFS; non-neg weighted → Dijkstra + heap; negative edges → Bellman-Ford (see Big-O complexity).
See also: Big-O complexity, Go idioms, JavaScript idioms.
Last updated on
Spotted something unclear or wrong on this page?