When slices fight you
You are building a task scheduler. Tasks arrive, get prioritized, and execute. You store them in a slice. Then a task gets cancelled. You have to find it, remove it, and shift every subsequent task down one index. The shift takes time proportional to the number of tasks. If you have ten thousand tasks, the cancellation slows down. You need a structure where removal doesn't move other items.
Go provides three containers for scenarios where slices struggle. container/list handles frequent insertions and deletions. container/heap keeps the highest priority item accessible. container/ring manages a fixed-size circular buffer. These packages solve specific problems. They are not replacements for slices. Slices remain the default choice for most data storage. Reach for containers only when the access pattern demands it.
How the containers work
Slices are contiguous blocks of memory. Insertion in the middle requires shifting elements. container/list is a doubly linked list. It allocates a separate node for each element. Each node holds a value and pointers to the previous and next nodes. Insertion or deletion updates pointers in adjacent nodes. No shifting occurs. The trade-off is memory overhead and cache locality. Linked list nodes are scattered in memory, making iteration slower than slicing through a contiguous array.
container/heap implements a priority queue. It uses a slice to store a binary tree structure. The heap property ensures the parent node always has higher priority than its children. This guarantees the top element is the minimum or maximum value. Adding an item bubbles it up to the correct position. Removing the top item drops the last element to the root and bubbles it down. Operations run in logarithmic time relative to the number of items.
container/ring is a circular linked list. The last element points back to the first. It has a fixed size. When you fill the ring, new data overwrites the oldest data. It is ideal for buffers where you only care about the most recent items and want to discard history automatically.
Minimal examples
Start with the basic operations for each container. These snippets show how to create, populate, and iterate.
package main
import (
"container/list"
"container/heap"
"container/ring"
"fmt"
)
// PriorityQueue implements heap.Interface for integers.
// Smaller values have higher priority.
type PriorityQueue []int
// Len returns the number of elements.
func (pq PriorityQueue) Len() int { return len(pq) }
// Less defines the ordering.
// Return true if element i should come before element j.
func (pq PriorityQueue) Less(i, j int) bool {
return pq[i] < pq[j]
}
// Swap exchanges elements i and j.
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
// Push adds an element to the heap.
// The receiver must be a pointer to modify the slice.
func (pq *PriorityQueue) Push(x any) {
// Type assert any to int.
// In production code, use a generic wrapper to avoid this.
*pq = append(*pq, x.(int))
}
// Pop removes and returns the highest priority element.
func (pq *PriorityQueue) Pop() any {
n := len(*pq)
item := (*pq)[n-1]
// Shrink the slice.
*pq = (*pq)[:n-1]
return item
}
func main() {
// --- List ---
// Create a doubly linked list.
l := list.New()
// Add items to the back.
l.PushBack("alpha")
l.PushBack("beta")
// Insert between elements.
// PushBackList inserts a list after an element.
middle := list.New()
middle.PushBack("gamma")
l.PushBackList(l.Front(), middle)
// Iterate forward.
fmt.Println("List:")
for e := l.Front(); e != nil; e = e.Next() {
fmt.Println(e.Value)
}
// --- Heap ---
// Initialize a priority queue.
pq := &PriorityQueue{3, 1, 4, 1, 5}
// Build the heap structure.
heap.Init(pq)
// Add a new item.
heap.Push(pq, 99)
// Remove the highest priority item.
fmt.Printf("Heap pop: %d\n", heap.Pop(pq))
// --- Ring ---
// Create a ring with 5 slots.
r := ring.New(5)
// Fill the ring.
// Value is any, so it holds any type.
for i := 0; i < r.Len(); i++ {
r.Value = i
r = r.Next()
}
// Iterate using Do.
fmt.Print("Ring: ")
r.Do(func(p any) {
fmt.Print(p, " ")
})
fmt.Println()
}
What happens under the hood
When you call list.New, Go allocates a sentinel element. The list uses this element to mark the boundaries. PushBack allocates a new Element struct, sets its value, and links it after the current back element. The back pointer moves to the new element. If you have a reference to an element, you can insert before or after it in constant time. The cost is the allocation. Every element requires a heap allocation for the node structure.
heap.Init rearranges the underlying slice to satisfy the heap property. It calls down on nodes starting from the middle of the slice. heap.Push appends the new item to the slice, then calls up to bubble it toward the root. heap.Pop swaps the root with the last element, removes the last element, and calls down to restore the heap property. The slice grows dynamically. The heap logic is a layer on top of slice operations.
ring.New creates n elements and links them in a circle. r.Next returns the next element. r.Do iterates until it returns to the starting element. The ring maintains a fixed number of nodes. You cannot change the size after creation. If you need a dynamic size, use a list or slice.
Realistic example: LRU cache with list
Linked lists shine when you need to reorder elements efficiently. A Least Recently Used cache is a classic use case. You need to access items by key and move accessed items to the front. When the cache is full, you remove the item at the back. A map provides fast lookup. A list maintains the order.
package main
import (
"container/list"
"fmt"
)
// CacheEntry holds the key and value.
// Storing the key allows removal from the list.
type CacheEntry struct {
Key string
Value any
}
// LRUCache manages a fixed-size cache.
type LRUCache struct {
capacity int
items map[string]*list.Element
order *list.List
}
// NewLRUCache creates a cache with the given capacity.
func NewLRUCache(capacity int) *LRUCache {
return &LRUCache{
capacity: capacity,
items: make(map[string]*list.Element),
order: list.New(),
}
}
// Get retrieves a value and marks it as recently used.
func (c *LRUCache) Get(key string) (any, bool) {
// Check if key exists.
elem, ok := c.items[key]
if !ok {
return nil, false
}
// Move element to front to mark as recent.
// MoveToFront is O(1) because it just updates pointers.
c.order.MoveToFront(elem)
return elem.Value.(*CacheEntry).Value, true
}
// Put adds or updates a value.
// Removes the least recently used item if full.
func (c *LRUCache) Put(key string, value any) {
// If key exists, update and move to front.
if elem, ok := c.items[key]; ok {
elem.Value.(*CacheEntry).Value = value
c.order.MoveToFront(elem)
return
}
// If cache is full, remove the back element.
if c.order.Len() >= c.capacity {
// Back is the least recently used.
oldElem := c.order.Back()
oldEntry := oldElem.Value.(*CacheEntry)
delete(c.items, oldEntry.Key)
c.order.Remove(oldElem)
}
// Add new entry to front.
entry := &CacheEntry{Key: key, Value: value}
elem := c.order.PushFront(entry)
c.items[key] = elem
}
func main() {
cache := NewLRUCache(3)
cache.Put("a", 1)
cache.Put("b", 2)
cache.Put("c", 3)
// Access "a" to make it recent.
cache.Get("a")
// Add "d". Cache is full.
// "b" is least recently used and gets evicted.
cache.Put("d", 4)
val, ok := cache.Get("b")
fmt.Printf("Get b: %v, %v\n", val, ok) // Output: Get b: <nil>, false
val, ok = cache.Get("a")
fmt.Printf("Get a: %v, %v\n", val, ok) // Output: Get a: 1, true
}
The map gives O(1) lookup. The list gives O(1) reordering. Without the list, you would need to scan the map to find the least recently used item, which is slow. The list stores pointers to elements, so the map can reference the list nodes directly. This combination is efficient and idiomatic.
Pitfalls and errors
Containers have quirks. Knowing them prevents runtime panics.
container/list is not thread-safe. Concurrent access causes data races. Protect the list with a mutex if multiple goroutines use it. The compiler does not catch this. The race detector will flag it.
list.Element.Value is any. You must type assert when reading. If you assert the wrong type, the runtime panics with interface conversion: interface {} is string, not int. The compiler allows the assertion because any can hold anything. Write defensive code or wrap the list in a generic type to enforce safety at compile time.
container/heap requires the interface methods. If you miss one, the compiler complains with does not implement heap.Interface (missing method X). Call heap.Push before heap.Init and the runtime panics with heap: Push called on non-heap. The heap structure must be initialized before operations.
container/ring requires a positive size. ring.New(0) panics with panic: ring: size must be > 0. The ring cannot be empty. If you need a dynamic buffer, use a slice or list.
Go 1.18 introduced generics. The container packages are not generic. You will see any everywhere. The community often wraps these in generic types to avoid type assertions. list is the most common victim of this pattern. Wrapping a list in a generic struct adds type safety without changing the underlying logic.
Decision matrix
Choose the right tool for the access pattern. Slices win most of the time. Containers are the exception.
Use container/list when you need frequent insertions and deletions in the middle of a sequence and you already have a reference to the element. Use a slice when you mostly append to the end or access elements by index; slices are faster for iteration and use less memory. Use container/heap when you need to repeatedly extract the minimum or maximum value from a growing set. Use a sorted slice when the dataset is small and static; sorting a slice is simpler than maintaining a heap interface. Use container/ring when you need a fixed-size buffer where the oldest item is automatically discarded when the buffer fills. Use a slice with modulo arithmetic when you need random access to the buffer elements; rings only support sequential traversal.
Where to go next
- How to Write Switch Statements in Go
- Common Time Formatting Mistakes in Go
- How to Use Method Sets in Go
Slices are the default. Containers are the exception. Pick the structure that matches the access pattern, not the one that feels familiar.