Data structures

Almost every performance problem in application code comes down to one question: what does this operation cost on this structure? A lookup in a slice of a million users scans up to a million entries; the same lookup in a map takes one hash. This lesson walks through the structures you will use every week — and that every coding interview assumes you know — with what each operation costs, how it works underneath, and how it looks in Go.

#Measuring cost with Big-O

Big-O describes how the work an operation does grows as the input grows, ignoring constant factors. You will see a handful of classes over and over:

The jump from O(n) to O(n²) is the one that bites in production: a nested loop that took 1 ms over 100 test rows takes 100 seconds over 100,000 real ones. When you look at code, find the loops, find what each iteration does, and multiply. The Big-O concept note covers the rules in more depth; the next lesson applies them to algorithms.

#Arrays and dynamic arrays

An array is a contiguous block of memory holding elements of one type. Because element i lives at start + i × size, reading or writing any index is O(1). Contiguity also makes arrays fast in practice: the CPU loads memory in 64-byte cache lines, so scanning an array touches memory in the order the hardware prefers.

Go's slice is a dynamic array: a pointer, a length and a capacity. append writes into spare capacity when there is some; when there isn't, it allocates a larger array (roughly double for small slices), copies everything, and appends. A single append can therefore cost O(n), but because doubling makes copies rare, the amortized cost per append is O(1).

nums := make([]int, 0, 1000) // preallocate when you know the size
for i := range 1000 {
	nums = append(nums, i*i) // never reallocates
}

#Hash maps

A hash map stores key–value pairs. It runs the key through a hash function to get a number, uses that number to pick a bucket, and stores the pair there. Lookup repeats the hash and checks one bucket, so insert, lookup and delete are O(1) on average. Two keys can land in the same bucket (a collision); implementations handle that with small per-bucket arrays or probing, and grow the table when it fills so buckets stay short. The hash tables note goes deeper on collisions and resizing.

Hash maps are the single most useful structure for turning O(n²) code into O(n). The classic example — does any pair of numbers sum to a target? — compares every pair in the naive version, but needs one pass with a map:

// TwoSum returns the indexes of two numbers that add up to target.
func TwoSum(nums []int, target int) (int, int, bool) {
	seen := make(map[int]int, len(nums)) // value -> index
	for i, n := range nums {
		if j, ok := seen[target-n]; ok {
			return j, i, true
		}
		seen[n] = i
	}
	return 0, 0, false
}

What maps don't give you: order. Iterating a Go map yields keys in an unspecified order (deliberately randomised). If you need keys sorted, collect them and sort, or use a tree. A set in Go is a map[T]struct{}: the empty struct takes no space.

#Stacks and queues

A stack is last-in, first-out: you push on top and pop from the top. A slice is a perfect stack, since both operations touch only the end:

stack := []rune{}
stack = append(stack, '(')        // push
top := stack[len(stack)-1]        // peek
stack = stack[:len(stack)-1]      // pop
_ = top

Stacks appear wherever you need to come back to the most recent unfinished thing: matching brackets, undo history, the call stack of a running program, and depth-first search.

A queue is first-in, first-out: enqueue at the back, dequeue from the front. Popping from the front of a slice with q = q[1:] is O(1) but keeps the old backing array alive until the slice is reallocated; for long-running queues, use a ring buffer or container/list. Queues drive breadth-first search, job processing and anything handled in arrival order. A deque (double-ended queue) supports both ends and powers sliding-window algorithms.

#Linked lists

A linked list stores each element in its own node with a pointer to the next (and, if doubly linked, the previous). Inserting or removing a node you already hold is O(1) — just rewire pointers — but reaching the k-th element is O(k), and nodes are scattered in memory, so scans are slow.

In application code you will rarely choose a linked list over a slice; the cache effects usually win even when the Big-O says otherwise. They matter as building blocks: an LRU cache combines a hash map (key → node) with a doubly linked list ordered by recency, so both lookup and "move to front" are O(1). That design is a favourite interview question precisely because it combines two structures to beat either one alone.

#Trees and binary search trees

A tree is a hierarchy of nodes, each with children and no cycles: file systems, the DOM, JSON documents and org charts are all trees. A binary search tree (BST) keeps every left descendant smaller than its node and every right descendant larger, so a lookup discards half the remaining tree at each step:

type Node struct {
	Key         int
	Left, Right *Node
}

func (n *Node) Contains(key int) bool {
	for n != nil {
		switch {
		case key < n.Key:
			n = n.Left
		case key > n.Key:
			n = n.Right
		default:
			return true
		}
	}
	return false
}

That is O(log n) only while the tree is balanced. Insert sorted keys into a plain BST and it degenerates into a linked list, with O(n) lookups. Production trees rebalance themselves: red-black trees in many standard libraries, and B-trees in databases, which store hundreds of keys per node so a lookup in a billion-row index touches only three or four disk pages. Trees beat hash maps when you need ordered operations: range queries ("all orders between Monday and Friday"), the smallest key above a value, or sorted iteration.

A trie (prefix tree) stores strings character by character, so all words sharing a prefix share a path. Autocomplete and routing tables use them.

#Heaps and priority queues

A heap is a tree, stored in an array, where every parent is smaller than its children (a min-heap). The smallest element is always at index 0, and pushing or popping rebalances along one root-to-leaf path in O(log n). That makes heaps the standard priority queue: schedulers, Dijkstra's shortest path, merging sorted streams, and "top k" problems.

Go provides the algorithm in container/heap; you supply a type that implements its interface:

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

// TopK returns the k largest values, in heap order (smallest at index 0).
func TopK(nums []int, k int) []int {
	h := &MinHeap{}
	for _, n := range nums {
		heap.Push(h, n)
		if h.Len() > k {
			heap.Pop(h) // drop the smallest; the heap keeps the k largest
		}
	}
	return []int(*h)
}

Keeping a heap of size k makes top-k O(n log k) instead of O(n log n) for a full sort — a big win when k is 10 and n is ten million.

#Graphs

A graph is a set of nodes connected by edges, directed or not, weighted or not. Road networks, social follows, service dependencies and build systems are graphs. You store one as an adjacency list — a map from each node to its neighbours — which uses space proportional to nodes plus edges:

graph := map[string][]string{
	"api":      {"auth", "orders"},
	"orders":   {"payments", "db"},
	"auth":     {"db"},
	"payments": {},
	"db":       {},
}

An adjacency matrix (an n×n grid of booleans) answers "is there an edge?" in O(1) but uses n² space, so it only suits small, dense graphs. Most graph questions reduce to a traversal — breadth-first or depth-first search — which the next lesson covers.

#Choosing a structure

Start with the simplest structure that makes your hot operation cheap. A sorted slice with binary search often beats a tree for data that is built once and read many times, because it is compact and cache-friendly.

#Practice

Write a Go function FirstUnique(s string) int that returns the index of the first character that appears exactly once in s, or -1 if there is none. It must run in O(n). Then write a table-driven test with at least these cases: "leetcode" → 0, "loveleetcode" → 2, "aabb" → -1, "" → -1.

func FirstUnique(s string) int {
	counts := make(map[rune]int)
	for _, r := range s {
		counts[r]++
	}
	for i, r := range s {
		if counts[r] == 1 {
			return i
		}
	}
	return -1
}

func TestFirstUnique(t *testing.T) {
	tests := []struct {
		in   string
		want int
	}{
		{"leetcode", 0},
		{"loveleetcode", 2},
		{"aabb", -1},
		{"", -1},
	}
	for _, tt := range tests {
		t.Run(tt.in, func(t *testing.T) {
			if got := FirstUnique(tt.in); got != tt.want {
				t.Errorf("FirstUnique(%q) = %d; want %d", tt.in, got, tt.want)
			}
		})
	}
}

#Key takeaways

• Big-O tells you how cost grows with input; the step from O(n) to O(n²) is the one that breaks production.
• Slices give O(1) indexing and amortized O(1) append; inserting in the middle is O(n).
• Hash maps give average O(1) lookup and turn many nested-loop problems into a single pass, but have no order.
• Stacks (LIFO) and queues (FIFO) model "most recent first" and "arrival order"; both are easy on top of slices.
• Balanced trees give O(log n) lookups plus ordered operations; heaps give O(log n) access to the smallest or largest item.
• Graphs model relationships; store them as adjacency lists.