Containers in Golang

Go’s standard library includes three powerful data structures under the container package: container/heap, container/list, and container/ring. While slices and maps cover most use cases, these specialized containers solve problems where ordering, priority, or circular traversal matters. Understanding when and how to use them can significantly improve the efficiency and clarity of your code.

Overview

Package	Data Structure	Best For
`container/heap`	Binary min-heap	Priority queues, scheduling, top-K problems
`container/list`	Doubly-linked list	Frequent insertions/removals in the middle, LRU caches
`container/ring`	Circular buffer	Fixed-size rotating buffers, round-robin scheduling

container/heap

The container/heap package provides a binary min-heap implementation. Rather than being a standalone container, it operates on any type that implements the heap.Interface. This design gives you full control over the element type and ordering logic.

How a Heap Works

A binary heap is a complete binary tree where each parent node is smaller than or equal to its children (for a min-heap). This guarantees the smallest element is always at the root.

flowchart TB
    A["1"] --> B["3"]
    A --> C["2"]
    B --> D["7"]
    B --> E["5"]
    C --> F["4"]
    C --> G["6"]

    style A fill:#d4edda,stroke:#28a745,stroke-width:2px

The tree is stored as a flat slice, where for element at index i:

Parent is at index (i - 1) / 2
Left child is at index 2*i + 1
Right child is at index 2*i + 2

Implementing a Priority Queue

To use container/heap, you need to implement the heap.Interface:

type Interface interface {
    sort.Interface          // Len, Less, Swap
    Push(x any)
    Pop() any
}

Here is a practical priority queue implementation:

package main

import (
    "container/heap"
    "fmt"
)

type Task struct {
    Name     string
    Priority int
}

type TaskQueue []*Task

func (tq TaskQueue) Len() int           { return len(tq) }
func (tq TaskQueue) Less(i, j int) bool { return tq[i].Priority < tq[j].Priority }
func (tq TaskQueue) Swap(i, j int)      { tq[i], tq[j] = tq[j], tq[i] }

func (tq *TaskQueue) Push(x any) {
    *tq = append(*tq, x.(*Task))
}

func (tq *TaskQueue) Pop() any {
    old := *tq
    n := len(old)
    task := old[n-1]
    old[n-1] = nil // avoid memory leak
    *tq = old[:n-1]
    return task
}

func main() {
    tq := &TaskQueue{}
    heap.Init(tq)

    heap.Push(tq, &Task{Name: "Send report", Priority: 3})
    heap.Push(tq, &Task{Name: "Fix critical bug", Priority: 1})
    heap.Push(tq, &Task{Name: "Code review", Priority: 2})

    for tq.Len() > 0 {
        task := heap.Pop(tq).(*Task)
        fmt.Printf("Processing: %s (priority %d)\n", task.Name, task.Priority)
    }
}

Output:

Processing: Fix critical bug (priority 1)
Processing: Code review (priority 2)
Processing: Send report (priority 3)

Heap Operations Complexity

Operation	Time Complexity
`heap.Init`	O(n)
`heap.Push`	O(log n)
`heap.Pop`	O(log n)
`heap.Fix`	O(log n)
`heap.Remove`	O(log n)

Tip

Use heap.Fix instead of removing and re-adding an element when its priority changes. It is more efficient because it performs a single re-heapification.

container/list

The container/list package implements a doubly-linked list. Each element holds a reference to both its previous and next neighbors, enabling O(1) insertions and removals at any position once you have a pointer to the element.

Linked List Structure

flowchart LR
    H["List (root)"] --> A["Element A"]
    A <--> B["Element B"]
    B <--> C["Element C"]
    C --> H

    style H fill:#d4edda,stroke:#28a745,stroke-width:2px

The list is internally implemented as a circular doubly-linked list with a sentinel root element. This simplifies boundary conditions since you never have to check for nil pointers at the head or tail.

Basic Usage

package main

import (
    "container/list"
    "fmt"
)

func main() {
    l := list.New()

    // Add elements
    l.PushBack("B")
    l.PushBack("D")
    front := l.PushFront("A")
    l.InsertAfter("C", l.Front().Next()) // Insert C after B

    // Traverse forward
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Print(e.Value, " ")
    }
    fmt.Println()

    // Move front element to back
    l.MoveToBack(front)

    // Traverse again
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Print(e.Value, " ")
    }
    fmt.Println()
}

Output:

A B C D
B C D A

Building an LRU Cache

A common real-world use of container/list is building an LRU (Least Recently Used) cache. The linked list tracks access order, while a map provides O(1) key lookups.

package main

import (
    "container/list"
    "fmt"
)

type LRUCache struct {
    capacity int
    items    map[string]*list.Element
    order    *list.List
}

type entry struct {
    key   string
    value string
}

func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        capacity: capacity,
        items:    make(map[string]*list.Element),
        order:    list.New(),
    }
}

func (c *LRUCache) Get(key string) (string, bool) {
    if elem, ok := c.items[key]; ok {
        c.order.MoveToFront(elem)
        return elem.Value.(*entry).value, true
    }
    return "", false
}

func (c *LRUCache) Put(key, value string) {
    if elem, ok := c.items[key]; ok {
        c.order.MoveToFront(elem)
        elem.Value.(*entry).value = value
        return
    }

    if c.order.Len() >= c.capacity {
        oldest := c.order.Back()
        c.order.Remove(oldest)
        delete(c.items, oldest.Value.(*entry).key)
    }

    elem := c.order.PushFront(&entry{key: key, value: value})
    c.items[key] = elem
}

func main() {
    cache := NewLRUCache(3)

    cache.Put("a", "alpha")
    cache.Put("b", "beta")
    cache.Put("c", "gamma")

    cache.Get("a") // "a" moves to front

    cache.Put("d", "delta") // evicts "b" (least recently used)

    for e := cache.order.Front(); e != nil; e = e.Next() {
        ent := e.Value.(*entry)
        fmt.Printf("%s: %s\n", ent.key, ent.value)
    }
}

Output:

d: delta
a: alpha
c: gamma

List Operations Complexity

Operation	Time Complexity
`PushFront` / `PushBack`	O(1)
`InsertBefore` / `InsertAfter`	O(1)
`Remove`	O(1)
`MoveToFront` / `MoveToBack`	O(1)
Search (by value)	O(n)

container/ring

The container/ring package implements a circular linked list, or ring buffer. Unlike container/list, a ring has no beginning or end, and every element is connected to its neighbors in a continuous loop.

Ring Structure

flowchart LR
    A["Element 1"] --> B["Element 2"]
    B --> C["Element 3"]
    C --> D["Element 4"]
    D --> A

    style A fill:#d4edda,stroke:#28a745,stroke-width:2px

A ring is particularly useful when you need a fixed-size buffer where new data overwrites the oldest entries.

Basic Usage

package main

import (
    "container/ring"
    "fmt"
)

func main() {
    // Create a ring of size 4
    r := ring.New(4)

    // Fill the ring
    for i := 1; i <= 4; i++ {
        r.Value = i
        r = r.Next()
    }

    // Traverse the ring
    r.Do(func(v any) {
        fmt.Print(v, " ")
    })
    fmt.Println()

    // Move forward by 2 positions
    r = r.Move(2)
    fmt.Printf("Current: %v\n", r.Value)
}

Output:

1 2 3 4
Current: 3

Rolling Average Calculator

A practical use of container/ring is computing rolling statistics over a fixed window:

package main

import (
    "container/ring"
    "fmt"
)

type RollingAverage struct {
    ring  *ring.Ring
    size  int
    count int
}

func NewRollingAverage(windowSize int) *RollingAverage {
    return &RollingAverage{
        ring: ring.New(windowSize),
        size: windowSize,
    }
}

func (ra *RollingAverage) Add(value float64) {
    ra.ring.Value = value
    ra.ring = ra.ring.Next()
    if ra.count < ra.size {
        ra.count++
    }
}

func (ra *RollingAverage) Average() float64 {
    if ra.count == 0 {
        return 0
    }
    var sum float64
    ra.ring.Do(func(v any) {
        if v != nil {
            sum += v.(float64)
        }
    })
    return sum / float64(ra.count)
}

func main() {
    avg := NewRollingAverage(3)

    values := []float64{10, 20, 30, 40, 50}
    for _, v := range values {
        avg.Add(v)
        fmt.Printf("Added %.0f -> Rolling average: %.2f\n", v, avg.Average())
    }
}

Output:

Added 10 -> Rolling average: 10.00
Added 20 -> Rolling average: 15.00
Added 30 -> Rolling average: 20.00
Added 40 -> Rolling average: 30.00
Added 50 -> Rolling average: 40.00

Ring Operations Complexity

Operation	Time Complexity
`New`	O(n)
`Next` / `Prev`	O(1)
`Move(n)`	O(n)
`Do`	O(n)
`Link` / `Unlink`	O(1)
`Len`	O(n)

Warning

ring.Len() traverses the entire ring to count elements. If you need frequent length checks, track the count separately.

Choosing the Right Container

flowchart TD
    Start["Need a specialized container?"] --> Q1{"Need elements\nordered by priority?"}
    Q1 -->|Yes| Heap["container/heap"]
    Q1 -->|No| Q2{"Need frequent\ninsert/remove\nin the middle?"}
    Q2 -->|Yes| List["container/list"]
    Q2 -->|No| Q3{"Need a fixed-size\ncircular buffer?"}
    Q3 -->|Yes| Ring["container/ring"]
    Q3 -->|No| Slice["Use a slice or map"]

    style Heap fill:#d4edda,stroke:#28a745,stroke-width:1px
    style List fill:#d4edda,stroke:#28a745,stroke-width:1px
    style Ring fill:#d4edda,stroke:#28a745,stroke-width:1px
    style Slice fill:#fff3cd,stroke:#ffc107,stroke-width:1px

Criteria	`heap`	`list`	`ring`
Access pattern	By priority	Sequential / positional	Circular / rotating
Size	Dynamic	Dynamic	Fixed
Memory overhead	Low (backed by slice)	Higher (per-element pointers)	Fixed (per-element pointers)
Thread-safe	No	No	No
Common use cases	Priority queues, schedulers, top-K	LRU caches, ordered queues, undo history	Rolling metrics, round-robin, log buffers

Note

None of the container packages are safe for concurrent use. If multiple goroutines need to access a container simultaneously, protect it with a sync.Mutex or sync.RWMutex.

Overview

container/heap

How a Heap Works

Implementing a Priority Queue

Heap Operations Complexity

container/list

Linked List Structure

Basic Usage

Building an LRU Cache

List Operations Complexity

container/ring

Ring Structure

Basic Usage

Rolling Average Calculator

Ring Operations Complexity

Choosing the Right Container

Further Reading