Data Structures & Algorithms, in Go

Measure cost before you optimize — Big-O for time and space, the common growth classes, and how to read the complexity of real Go code.

A Go slice is a view over a backing array — how the (ptr, len, cap) header, append, growth, copy and re-slicing actually behave, and the aliasing traps.

Nodes joined by pointers — O(1) insert/delete at a known position, O(n) access; singly vs doubly linked, the reversal classic, and when a slice is the better choice.

LIFO and FIFO with O(1) push and pop — a stack on a Go slice, the balanced-brackets classic, and the head-index trick that keeps a queue's dequeue cheap.

Average O(1) lookup via hashing — how Go's built-in map works, collisions and load factor, the comma-ok idiom, and the ordering and nil-map gotchas.

Nodes with up to two children — structure, depth vs height, the three DFS traversals (inorder, preorder, postorder), and level-order BFS with a queue.

The BST ordering invariant (left < node < right) gives O(h) search and insert, an inorder walk yields sorted order, and balance decides log n vs n.

A binary heap packed in a slice — parent/child by index arithmetic, sift-up and sift-down in O(log n), and Go's container/heap to build a priority queue.

A prefix tree keyed by characters — Insert, Search and StartsWith in O(L) where L is the key length, the engine behind autocomplete and prefix queries.

Vertices joined by edges — adjacency lists, BFS for shortest hops, DFS for reachability and ordering, all O(V + E).

Track which elements are connected — the disjoint-set forest, Find with path compression and Union by rank for near-O(1) operations, and its jobs: connected components, cycle detection, and Kruskal's MST.

Find a value in a sorted slice in O(log n) by repeatedly halving the range — the correct loop, the off-by-one traps, and the stdlib helpers.

Why comparison sorts can't beat O(n log n) — merge sort and quicksort by hand, then the one line you actually write in Go: slices.Sort.

Replace nested loops with two indices that move with intent — converging pointers on sorted data and a sliding window for contiguous subarray and substring problems.

Define a problem in terms of itself — base case plus recursive case, the call stack and its limits, and backtracking's choose / explore / un-choose loop.

Solve problems with overlapping subproblems and optimal substructure — from exponential recursion to top-down memoization and bottom-up tabulation in Go.

Make the locally optimal choice and never look back — when greedy is provably correct, classic wins like interval scheduling, and where it fails.