Arrays, slices & maps

The three collections behind every algorithm in this course, including what a slice really is in memory and why that matters.

Arrays#

An array has a length that is part of its type: [5]int and [6]int are different types.

var marks [5]float64           // five zeros
marks[0] = 90
scores := [3]int{7, 8, 9}      // literal
auto := [...]string{"a", "b"}  // length counted for you: [2]string

Arrays are values. Assigning or passing one copies every element. That makes them safe but expensive for large data, so you rarely use them directly, except in two DSA tricks: fixed counters like [26]int for letters, and as map keys (arrays are comparable; slices are not).

Slices#

A slice is a small header with three fields:

Field	Meaning
pointer	where the slice starts in a backing array
length (`len`)	how many elements you can read
capacity (`cap`)	how many elements fit before the backing array runs out

s := []int{1, 2, 3}        // literal: len 3, cap 3
t := make([]int, 2, 8)     // len 2 (both 0), cap 8
var u []int                // nil slice: len 0, cap 0, ready to append to

Slicing a slice

s[lo:hi] makes a new header looking at elements lo to hi-1 of the same array. Nothing is copied.

array:   [ 10 | 20 | 30 | 40 | 50 ]
s := array[1:3]   ->  [20 30]   len 2, cap 4 (room up to the array's end)

Because they share memory, writing through one slice is visible through the other.

append, step by step

append(s, x) does one of two things:

If len < cap, it writes x into the next slot of the same array and returns a header with len+1.
If len == cap, it allocates a new, bigger array (about double for small slices), copies everything over, writes x, and returns a header pointing at the new array.

Watch it happen:

Code	len	cap	Same array as before?
`var s []int`	0	0
`s = append(s, 1)`	1	1	new
`s = append(s, 2)`	2	2	new
`s = append(s, 3)`	3	4	new
`s = append(s, 4)`	4	4	same
`s = append(s, 5)`	5	8	new

Doubling means each element is copied only a few times on average, so append is amortized O(1). If you know the final size, make([]int, 0, n) avoids the copies entirely.

See it: the backing array

Change the starting capacity and the values, then step through. Watch for the moment len reaches cap.

InteractiveHow append grows a sliceA slice is a window (pointer, len, cap) onto a backing array. When len reaches cap, append allocates a bigger array and copies.

len 0cap 0arrays allocated 0

array

(no array yet)

var s []int: a nil slice. No array is allocated until the first append.

1 / 12

The same mechanism explains the most common slice surprise: two slices sharing one array.

InteractiveSlices sharing a backing arrayb := a[1:3] does not copy. Writes through b show up in a, and append on b can overwrite a's elements while there is spare capacity.

a [5 elems]b len 0b cap 5

a's array

a := []int{1, 2, 3, 4, 5}: len 5, cap 5.

1 / 8

copy

copy(dst, src) copies min(len(dst), len(src)) elements and returns that count. It is how you make an independent duplicate:

dup := make([]int, len(s))
copy(dup, s)

Removing and inserting

s = append(s[:i], s[i+1:]...)   // delete index i (order kept, O(n))
s[i] = s[len(s)-1]; s = s[:len(s)-1] // delete fast (order lost, O(1))
s = slices.Insert(s, i, x)      // insert x at i

The slices package (Go 1.21+) also gives Sort, BinarySearch, Contains, Index, Reverse, Max, Min, Equal and Clone.

Two-dimensional slices

A grid is a slice of slices. Each row must be allocated:

grid := make([][]int, rows)
for r := range grid {
	grid[r] = make([]int, cols)
}

Maps#

A map stores key-value pairs with average O(1) lookup, insert and delete.

ages := map[string]int{"ana": 31} // literal
ages["budi"] = 27                  // insert or update
delete(ages, "ana")                // remove (no error if missing)
n := len(ages)                     // number of pairs

Reading a missing key returns the value type's zero value, which is why counting is so short: freq[w]++ works even the first time. To know whether a key was really there, use the comma-ok form:

if age, ok := ages["citra"]; ok {
	fmt.Println(age)
} else {
	fmt.Println("no citra")
}

Rules worth memorizing:

Keys must be comparable with ==: numbers, strings, booleans, pointers, arrays and structs of those. Slices, maps and functions cannot be keys.
Iteration order is random on purpose. Sort the keys when order matters.
A nil map can be read but panics on write. Create maps with make or a literal.
Maps are references: passing one to a function lets the function change it.
A set is map[T]struct{}. The empty struct takes zero bytes and has no ambiguous meaning.
Maps can nest: map[string]map[string]string, but each inner map must be created before use.

More examples#

The book's chemical elements map

The book builds a map of chemical elements, then upgrades it to a map of maps to store several facts per element. In modern Go a map of structs is usually clearer, and maps and slices (Go 1.21+) make printing in a stable order easy.

elements.go

package main
 
import (
	"fmt"
	"maps"
	"slices"
)
 
type Element struct {
	Name  string
	State string
}
 
func main() {
	elements := map[string]Element{
		"H":  {"Hydrogen", "gas"},
		"He": {"Helium", "gas"},
		"Li": {"Lithium", "solid"},
		"Hg": {"Mercury", "liquid"},
	}
 
	if el, ok := elements["Li"]; ok { // comma-ok: was the key present?
		fmt.Println(el.Name, el.State)
	}
	if _, ok := elements["Un"]; !ok {
		fmt.Println("Un is not an element")
	}
 
	for _, sym := range slices.Sorted(maps.Keys(elements)) { // sorted, so the output is stable
		fmt.Printf("%-2s %-9s %s\n", sym, elements[sym].Name, elements[sym].State)
	}
 
	// Group symbols by state: a map whose values are slices.
	byState := map[string][]string{}
	for _, sym := range slices.Sorted(maps.Keys(elements)) {
		st := elements[sym].State
		byState[st] = append(byState[st], sym) // appending to a missing key starts from nil
	}
	fmt.Println(byState)
 
	// Deleting while ranging is allowed in Go.
	for sym, el := range elements {
		if el.State == "gas" {
			delete(elements, sym)
		}
	}
	fmt.Println(len(elements), "non-gas elements left")
}

Output

Lithium solid
Un is not an element
H  Hydrogen  gas
He Helium    gas
Hg Mercury   liquid
Li Lithium   solid
map[gas:[H He] liquid:[Hg] solid:[Li]]
2 non-gas elements left

The chapter's exercises

exercises.go

package main
 
import "fmt"
 
func main() {
	// Find the smallest number in a slice.
	x := []int{48, 96, 86, 68, 57, 82, 63, 70, 37, 34, 83, 27, 19, 97, 9, 17}
	smallest := x[0]
	for _, v := range x[1:] {
		smallest = min(smallest, v)
	}
	fmt.Println("smallest:", smallest)
 
	// The 4th element of an array or slice is at index 3.
	arr := [6]string{"a", "b", "c", "d", "e", "f"}
	fmt.Println("4th:", arr[3], " len of arr[2:5]:", len(arr[2:5]))
 
	// What does make([]int, 3, 9) give you?
	s := make([]int, 3, 9)
	fmt.Println(s, "len", len(s), "cap", cap(s))
 
	// Arrays are values: assignment copies. Slices share.
	a := [3]int{1, 2, 3}
	b := a
	b[0] = 99
	sa := a[:]
	sb := sa
	sb[1] = 77
	fmt.Println("array a:", a, "array b:", b, "slice view of a after sb[1]=77:", sa)
 
	// A 3x3 grid as a fixed-size 2D array, which is comparable with ==.
	var g1, g2 [3][3]int
	g1[1][1] = 5
	g2[1][1] = 5
	fmt.Println("grids equal:", g1 == g2)
}

Output

smallest: 9
4th: d  len of arr[2:5]: 3
[0 0 0] len 3 cap 9
array a: [1 77 3] array b: [99 2 3] slice view of a after sb[1]=77: [1 77 3]
grids equal: true

Notice the last array line: a itself shows 77, because sa := a[:] is a slice of the array, so writing through sb changes a. Only the plain assignment b := a made a copy.

The full program#

collections.go

package main
 
import (
	"fmt"
	"maps"
	"slices"
)
 
func main() {
	// Arrays are values
	marks := [5]float64{90, 85, 72, 88, 95}
	backup := marks
	backup[0] = 0
	total := 0.0
	for _, m := range marks {
		total += m
	}
	fmt.Println(total/float64(len(marks)), marks[0], backup[0])
 
	// Slices share their array
	base := []int{1, 2, 3, 4}
	head := base[:2]
	head = append(head, 99) // overwrites base[2]
	fmt.Println(base, head, len(head), cap(head))
 
	safe := base[:2:2]
	safe = append(safe, 7) // capacity exhausted: copies
	fmt.Println(base, safe)
 
	// Growth
	var s []int
	prev := -1
	for i := range 9 {
		s = append(s, i)
		if cap(s) != prev {
			fmt.Print(cap(s), " ")
			prev = cap(s)
		}
	}
	fmt.Println()
 
	// copy and delete
	dup := make([]int, len(s))
	copy(dup, s)
	dup = append(dup[:2], dup[3:]...) // remove index 2
	fmt.Println(s[:4], dup[:4])
 
	// Maps
	cities := map[string]map[string]string{
		"JKT": {"name": "Jakarta", "island": "Java"},
		"DPS": {"name": "Denpasar", "island": "Bali"},
	}
	if c, ok := cities["DPS"]; ok {
		fmt.Println(c["name"], "is on", c["island"])
	}
	_, ok := cities["SUB"]
	fmt.Println("has SUB:", ok)
 
	freq := map[string]int{}
	for _, w := range []string{"go", "is", "fun", "go"} {
		freq[w]++
	}
	fmt.Println(slices.Sorted(maps.Keys(freq)), freq["go"], freq["rust"])
 
	seen := map[int]struct{}{}
	for _, n := range []int{3, 1, 3} {
		if _, dup := seen[n]; dup {
			fmt.Println("duplicate:", n)
		}
		seen[n] = struct{}{}
	}
}

Output

86 90 0
[1 2 99 4] [1 2 99] 3 4
[1 2 99 4] [1 2 7]
1 2 4 8 16 
[0 1 2 3] [0 1 3 4]
Denpasar is on Bali
has SUB: false
[fun go is] 2 0
duplicate: 3

Trace line two of the output: head had length 2 but capacity 4, so append wrote 99 into base[2]. In line three, safe had capacity 2, so append had to copy and base stayed untouched.

Summary#

Arrays have fixed length and copy on assignment; use them for small fixed counters and map keys.
A slice is a pointer, length and capacity over an array. Slicing shares memory; append may reallocate, so always reassign its result.
copy and slices.Clone make independent copies.
Maps give O(1) average lookups. Use comma-ok to detect missing keys, make before writing, and sort keys when order matters.
map[T]struct{} is Go's set.

Arrays, slices & maps

Arrays#

Slices#

Slicing a slice

append, step by step

See it: the backing array

copy

Removing and inserting

Two-dimensional slices

Maps#

More examples#

The book's chemical elements map

The chapter's exercises

The full program#

Summary#

Check your understanding

Practice in Go