Data Structures Map

Abstract Types and Implementations

It helps to separate what a structure does from how it does it. A stack is defined by its behavior — push, pop, last in first out — and can be implemented with a slice or a linked list. Users of the stack should not care which.

Interface as Contract

An abstract data type (ADT) is a set of operations with defined behavior. In Go an interface expresses the ADT, and a concrete type implements it. Generics (Go 1.18+) let one implementation serve any element type.

// Stack is the ADT: behavior only, no storage decisions.
type Stack[T any] interface {
	Push(v T)
	Pop() (T, bool) // ok=false when the stack is empty
	Len() int
}

// SliceStack is one implementation, backed by a slice.
type SliceStack[T any] struct {
	items []T
}

func (s *SliceStack[T]) Push(v T) { s.items = append(s.items, v) } // amortized O(1)
func (s *SliceStack[T]) Len() int { return len(s.items) }

func (s *SliceStack[T]) Pop() (T, bool) {
	var zero T // the zero value of T, returned when empty
	if len(s.items) == 0 {
		return zero, false
	}
	v := s.items[len(s.items)-1]
	s.items = s.items[:len(s.items)-1] // O(1): shrink the length only
	return v, true
}

// compile-time check that *SliceStack[int] satisfies Stack[int]
var _ Stack[int] = (*SliceStack[int])(nil)

Choose by Operations

Before choosing a structure, list the operations your program performs and roughly how often: lookups by key, lookups by position, insertions at the end or in the middle, removal of the smallest element, iteration in sorted order. The structure that makes the most frequent operations cheap is usually right. The catalog below lists the costs.

Go's Built-in Structures

Go has three built-in collection types — arrays, slices, and maps — plus structs and pointers for building your own. Understanding their memory behavior prevents a whole class of bugs.

Arrays

An array [N]T has a length that is part of its type: [3]int and [4]int are different types. Arrays are values: assigning or passing one copies every element. They are used for small fixed-size data (a 3D point, a SHA-256 digest [32]byte) and as the storage beneath slices.

a := [3]int{1, 2, 3}
b := a       // copies all three elements
b[0] = 99    // a is unchanged: a == [1 2 3]
fmt.Println(a == [3]int{1, 2, 3}) // arrays of comparable types support ==

Slices

A slice []T is a small header of three fields — a pointer into a backing array, a length, and a capacity. Slicing creates a new header over the same array; it does not copy elements. This makes sub-slices cheap, and it also means that writing through one slice can change another.

After t := s[1:3], both headers point into one backing array. Writing t[0] = 99 changes s[1]. The capacity of t runs to the end of the shared array.

s := []int{1, 2, 3, 4, 5}
t := s[1:3]        // len 2, cap 4 — a view, not a copy
t[0] = 99          // s is now [1 99 3 4 5]

u := slices.Clone(s[1:3]) // Go 1.21+: independent copy
u[0] = -1                 // s is unaffected

// append grows capacity geometrically, so appends are amortized O(1)
var g []int
for i := 0; i < 10; i++ {
	g = append(g, i) // may move g to a new, larger backing array
}

Maps

A map map[K]V is a hash table: insertion, lookup, and deletion are O(1) on average. Keys must be comparable (== defined), so slices cannot be keys but arrays and structs of comparable fields can. Since Go 1.24 maps are implemented as Swiss tables, but the rules for using them did not change.

freq := make(map[string]int) // a nil map can be read but not written
for _, w := range strings.Fields("go is fun go") {
	freq[w]++ // missing keys read as the zero value, 0
}

// "comma ok" distinguishes a missing key from a stored zero
if n, ok := freq["go"]; ok {
	fmt.Println("go appears", n, "times")
}

// iteration order is randomized; sort keys for stable output (Go 1.23+)
for _, k := range slices.Sorted(maps.Keys(freq)) {
	fmt.Println(k, freq[k])
}

Structs and Pointers

Every linked structure in this roadmap — lists, trees, graphs — is a struct that holds pointers to other structs of the same type. A nil pointer marks "no next node" or "no child". Go's garbage collector frees nodes that are no longer reachable, so removing a node is simply a matter of unlinking it.

// ListNode is the building block of a singly linked list.
type ListNode struct {
	Val  int
	Next *ListNode // nil at the end of the list
}

// TreeNode is the building block of a binary tree.
type TreeNode struct {
	Val         int
	Left, Right *TreeNode // nil when the child is absent
}

// build 1 -> 2 -> 3 and walk it
head := &ListNode{1, &ListNode{2, &ListNode{3, nil}}}
for n := head; n != nil; n = n.Next {
	fmt.Print(n.Val, " ")
}

Standard Library Containers

The standard library adds a small set of containers and generic helpers. Knowing them saves time; implementing them yourself (in later lessons) teaches how they work. The demo 09_builtin_structures.go exercises every one.

container/list

A doubly linked list with O(1) insertion and removal at any element you hold a reference to. Values are stored as any, so reading them requires a type assertion. In practice it is used for LRU caches and ordered queues where elements move frequently; for simple sequences a slice is faster because its elements sit together in memory.

container/heap

Heap algorithms (Init in O(n), Push and Pop in O(log n)) over any type that implements heap.Interface: the sort.Interface methods plus Push and Pop. You provide the storage and the ordering; the package maintains the heap property. This is Go's priority queue, covered fully in Heaps & Priority Queues.

container/ring

A circular linked list in which the last element links back to the first. It suits round-robin rotation over a fixed set of items. A slice with a wrapping index (a ring buffer) is usually the faster choice and is built in Stacks & Queues.

slices and maps Packages

Since Go 1.21 the slices and maps packages provide generic algorithms: slices.Sort, slices.BinarySearch, slices.Index, slices.Reverse, slices.Clone, and maps.Clone, among others. Go 1.23 added iterator functions such as maps.Keys and slices.Sorted. Use them in production code — but know their cost: slices.Index and slices.Contains are linear scans.

Structure Catalog

This catalog is the roadmap in one place: each structure, the cost of its main operations, and the lesson that builds it. Costs are worst case unless marked avg (average) or am. (amortized).

Linear Structures

* O(1) deletion at a held node requires a doubly linked list, or a singly linked list when you hold the previous node.

Hierarchical Structures

Graphs and Disjoint Sets

Probabilistic and Specialized Structures

These structures solve narrow problems extremely well, often by trading exactness or generality for memory and speed. They appear in Phase 4.

• Bloom filter — set membership in a small bit array; false positives are possible, false negatives are not. Used to skip disk lookups and filter already-seen items. (Advanced Techniques)
• HyperLogLog — estimates the number of distinct elements in a stream using a few kilobytes, regardless of stream size. (Advanced Techniques)
• LRU cache — a hash map plus a doubly linked list, giving O(1) lookup and O(1) eviction of the least recently used entry. (Production Structures)
• Skip list — a layered linked list with O(log n) expected search, simpler to make concurrent than a balanced tree. (Production Structures)
• Interval tree — finds all intervals overlapping a query interval; used for scheduling conflicts and genome ranges. (Advanced Trees)
• Rope and suffix array — string representations for fast edits of very large texts and fast substring search. (String Algorithms)

Choosing a Structure

Choosing a structure is an engineering decision with measurable consequences. A short list of questions narrows the choice quickly; measurement settles the rest.

Questions to Ask

1. How do I find things? By position → slice. By key → map. By order (smallest, range, next larger) → sorted slice, balanced tree, or heap.
2. Where do insertions and deletions happen? At the end → slice. At both ends → ring-buffer deque. In the middle at a known place → linked list.
3. Do I need sorted order? Once → sort a slice. Continuously while data changes → balanced tree or heap.
4. How large is n, and how many operations? For small n, the simplest structure usually wins because constants dominate.
5. What does memory cost? A map uses several times the memory of a slice holding the same keys; a linked list adds a pointer per element and scatters elements across memory.

Case Study: A Blocklist

A service keeps N blocked user IDs and answers Q queries of the form "is this ID blocked?". Three representations are reasonable, and the right one depends on the workload:

The demo hides all three behind one interface, runs them on identical data, and times the build and query phases separately for three workloads: 10_choose_structure.go.

Common Pitfalls

Most data-structure bugs in Go come from misunderstanding how slices and maps share memory.

Slice Aliasing After append

If a slice has spare capacity, append writes into the shared backing array, and another slice over the same array sees the change. If it has no spare capacity, append moves to a new array and the two slices silently separate. Code that relies on either behavior is fragile: use slices.Clone when you need an independent copy.

base := make([]int, 3, 10) // len 3, cap 10: room to grow in place
a := append(base, 1)       // writes base's array at index 3
b := append(base, 2)       // ALSO writes index 3 — overwrites a[3]
fmt.Println(a[3], b[3])    // prints "2 2", not "1 2"

Writing to a nil Map

A declared but uninitialized map (var m map[string]int) is nil. Reading it returns zero values, but writing panics with assignment to entry in nil map. Always create maps with make or a literal before writing, including maps stored in struct fields.

Relying on Map Order

Go deliberately randomizes map iteration order, so output that depends on it changes between runs. Tests that pass locally may fail in CI. Sort the keys when order matters, or keep a separate slice that records insertion order.

Practice Lab

These exercises connect the map to real code before Phase 2 builds each structure from scratch.

Run the Demos

1. Run 09_builtin_structures.go and note where capacity growth slows from doubling. Change the element type from int to a 64-byte struct and compare.
2. Run 10_choose_structure.go. Add a fourth workload with N = 1,000,000 and Q = 100 and predict the winner before running it.

Exercises

1. Generic queue. Following the Stack[T] example, define a Queue[T] interface and a slice-backed implementation. What is the cost of removing from the front with q.items = q.items[1:], and what happens to the memory at the front?
2. Word index. Build map[string][]int mapping each word of a text to the line numbers where it appears. Print the words in alphabetical order.
3. Pick a structure. For each case, choose a structure and justify it with the catalog: an undo history; the 10 most expensive orders in a live feed; checking whether a username is taken; a playlist where songs are frequently moved.

Phase 1 is complete. Continue with Arrays & Slices, the first lesson of Phase 2.