golang-data-structures

$27

A slice is a 3-word header: pointer, length, capacity. Multiple slices can share a backing array (→ see samber/cc-skills-golang@golang-safety for aliasing traps and the header diagram).

Capacity Growth

• < 256 elements: capacity doubles

-

= 256 elements: grows by ~25% (newcap += (newcap + 3*256) / 4)

• Each growth copies the entire backing array — O(n)

Preallocation

// Exact size known

users := make([]User, 0, len(ids))

// Approximate size known

results := make([]Result, 0, estimatedCount)

// Pre-grow before bulk append (Go 1.21+)

s = slices.Grow(s, additionalNeeded)

slices Package (Go 1.21+)

Key functions: Sort/SortFunc, BinarySearch, Contains, Compact, Grow. For Clone, Equal, DeleteFunc → see samber/cc-skills-golang@golang-safety skill.

Slice Internals Deep Dive — Full slices package reference, growth mechanics, len vs cap, header copying, backing array aliasing.

Map Internals

Maps are hash tables with 8-entry buckets and overflow chains. They are reference types — assigning a map copies the pointer, not the data.

Preallocation

m := make(map[string]*User, len(users)) // avoids rehashing during population

maps Package Quick Reference (Go 1.21+)

Function

Purpose

Collect (1.23+)

Build map from iterator

Insert (1.23+)

Insert entries from iterator

All (1.23+)

Iterator over all entries

Keys, Values

Iterators over keys/values

For Clone, Equal, sorted iteration → see samber/cc-skills-golang@golang-safety skill.

Map Internals Deep Dive — How Go maps store and hash data, bucket overflow chains, why maps never shrink (and what to do about it), comparing map performance to alternatives.

Arrays

Fixed-size, value types. Copied entirely on assignment. Use for compile-time-known sizes:

type Digest [32]byte           // fixed-size, value type

var grid [3][3]int             // multi-dimensional

cache := map[[2]int]Result{}   // arrays are comparable — usable as map keys

Prefer slices for everything else — arrays cannot grow and pass by value (expensive for large sizes).

container/ Standard Library

Package

Data Structure

Best For

container/list

Doubly-linked list

LRU caches, frequent middle insertion/removal

container/heap

Min-heap (priority queue)

Top-K, scheduling, Dijkstra

container/ring

Circular buffer

Rolling windows, round-robin

bufio

Buffered reader/writer/scanner

Efficient I/O with small reads/writes

Container types use any (no type safety) — consider generic wrappers. Container Patterns, bufio, and Examples — When to use each container type, generic wrappers to add type safety, and bufio patterns for efficient I/O.

strings.Builder vs bytes.Buffer

Use strings.Builder for pure string concatenation (avoids copy on String()), bytes.Buffer when you need io.Reader or byte manipulation. Both support Grow(n). Details and comparison

Generic Collections (Go 1.18+)

Use the tightest constraint possible. comparable for map keys, cmp.Ordered for sorting, custom interfaces for domain-specific ordering.

type Set[T comparable] map[T]struct{}

func (s Set[T]) Add(v T)          { s[v] = struct{}{} }

func (s Set[T]) Contains(v T) bool { _, ok := s[v]; return ok }

Writing Generic Data Structures — Using Go 1.18+ generics for type-safe containers, understanding constraint satisfaction, and building domain-specific generic types.

Pointer Types

Type

Use Case

Zero Value

*T

Normal indirection, mutation, optional values

nil

unsafe.Pointer

FFI, low-level memory layout (6 spec patterns only)

nil

weak.Pointer[T] (1.24+)

Caches, canonicalization, weak references

N/A

Pointer Types Deep Dive — Normal pointers, unsafe.Pointer (the 6 valid spec patterns), and weak.Pointer[T] for GC-safe caches that don't prevent cleanup.

Copy Semantics Quick Reference

Type

Copy Behavior

Independence

int, float, bool, string

Value (deep copy)

Fully independent

array, struct

Value (deep copy)

Fully independent

slice

Header copied, backing array shared

Use slices.Clone

map

Reference copied

Use maps.Clone

channel

Reference copied

Same channel

*T (pointer)

Address copied

Same underlying value

interface

Value copied (type + value pair)

Depends on held type

Third-Party Libraries

For advanced data structures (trees, sets, queues, stacks) beyond the standard library:

• **emirpasic/gods** — comprehensive collection library (trees, sets, lists, stacks, maps, queues)

• **deckarep/golang-set** — thread-safe and non-thread-safe set implementations

• **gammazero/deque** — fast double-ended queue

When using third-party libraries, refer to their official documentation and code examples for current API signatures. Context7 can help as a discoverability platform.

Cross-References

• → See samber/cc-skills-golang@golang-performance skill for struct field alignment, memory layout optimization, and cache locality

• → See samber/cc-skills-golang@golang-safety skill for nil map/slice pitfalls, append aliasing, defensive copying, slices.Clone/Equal

• → See samber/cc-skills-golang@golang-concurrency skill for channels, sync.Map, sync.Pool, and all sync primitives

• → See samber/cc-skills-golang@golang-design-patterns skill for string vs []byte vs []rune, iterators, streaming

• → See samber/cc-skills-golang@golang-structs-interfaces skill for struct composition, embedding, and generics vs any

• → See samber/cc-skills-golang@golang-code-style skill for slice/map initialization style

Common Mistakes

Mistake

Fix

Growing a slice in a loop without preallocation

Each growth copies the entire backing array — O(n) per growth. Use make([]T, 0, n) or slices.Grow

Using container/list when a slice would suffice

Linked lists have poor cache locality (each node is a separate heap allocation). Benchmark first

bytes.Buffer for pure string building

Buffer's String() copies the underlying bytes. strings.Builder avoids this copy

unsafe.Pointer stored as uintptr across statements

GC can move the object between statements — the uintptr becomes a dangling reference

Large struct values in maps (copying overhead)

Map access copies the entire value. Use map[K]*V for large value types to avoid the copy

References

• Go Data Structures (Russ Cox)

• The Go Memory Model

• Effective Go