go-data-structures

Go Data Structures

Pick the structure that fits the access pattern — not the most familiar one. Slices and maps are the workhorses; arrays, container types, and the slices/maps packages cover the rest. Understanding the header layout, growth costs, and copy semantics of each turns most performance questions into one-line decisions.

Core Rules

1. Slices and maps are reference types — assigning copies the header, not the data. Use slices.Clone / maps.Clone for a true copy.
2. Preallocate with make([]T, 0, n) and make(map[K]V, n) whenever the size is known or estimable.
3. Always assign the result of append — the backing array may move.
4. Use slices and maps packages (Go 1.21+) instead of hand-rolled helpers.
5. map[K]struct{} is the canonical set — zero-byte values, no boolean ambiguity.
6. strings.Builder for string building, bytes.Buffer when you need io.Reader/io.Writer.

Picking a Structure

What do you need?
├─ Ordered, fixed compile-time size      → [N]T  array
├─ Ordered, dynamic size                 → []T   slice
│  ├─ Known size               → make([]T, 0, n)
│  └─ JSON output must be []   → []T{} literal (not nil)
├─ Key/value lookup                      → map[K]V
│  ├─ Need a set            → map[K]struct{}
│  └─ Known size            → make(map[K]V, n)
├─ Priority queue / top-k                → container/heap
├─ Frequent middle insertion             → container/list
├─ Fixed-size rolling window             → container/ring
├─ Pure string building                  → strings.Builder
└─ Read+write of bytes                   → bytes.Buffer

Slice Internals

A slice is a 3-word header: pointer, length, capacity. Multiple slices can alias the same backing array — s[1:4] shares memory with s.

Capacity Growth

The exact algorithm has changed across versions; do not rely on it. As of recent Go:

• len < 256 → capacity roughly doubles.
• len ≥ 256 → grows by ~25%.
• Each growth allocates a new backing array and copies — O(n) per growth.