Skip to content
Tutorials Center
My learning

Topics

Lesson 90 of 147 ยท Standard Library

container/heap, list and ring

Use Go's container packages - build priority queues with container/heap, linked lists with container/list and circular lists with container/ring, with runnable examples.

Go has built-in slices and maps, but no built-in priority queue or linked list. The standard library fills the gap with three small packages under container/: heap (a priority queue on top of any slice), list (a doubly linked list) and ring (a circular list). They were written before generics existed, so they store values of type any, and heap works through an interface that you implement.

You will use container/heap the most. It powers schedulers, "top K" problems and shortest-path algorithms. container/list shines when you need constant-time removal from the middle, such as in an LRU cache. container/ring is rare but neat for fixed-size rotating data.

container/heap: a priority queue

A heap keeps the smallest (or largest) element easy to reach. The package does not give you a ready-made type. Instead, you define a type that satisfies heap.Interface, and the package supplies the algorithms:

Go
type Interface interface {
	sort.Interface            // Len, Less, Swap
	Push(x any)               // add x as element Len()
	Pop() any                 // remove and return element Len()-1
}

Your type is usually a slice. Less(i, j) decides the order: if it says element i is "less" than j, i comes out first. Use < for a min-heap and > for a max-heap. See Sorting for the Len/Less/Swap trio.

Go A min-heap of integers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with bufio.Scanner or fmt.Scan), it gets the next line from this box.

There is one trap here. The Push and Pop methods on your type are low-level: they only append to, or shrink, the slice. You must never call h.Push(x) directly. Call heap.Push(h, x) and heap.Pop(h) instead, because those functions also restore the heap order by moving elements up or down.

flowchart TD
    A["heap.Push(h, x)"] --> B["h.Push(x): append to slice"]
    B --> C["heap moves x up<br/>while it is smaller than its parent"]
    D["heap.Pop(h)"] --> E["swap first and last"]
    E --> F["heap moves the new root down"]
    F --> G["h.Pop(): remove last element"]

The functions in the heap package wrap your Push and Pop methods and repair the ordering.

Both operations take O(log n) time, peeking at (*h)[0] is O(1), and heap.Init builds a heap from existing data in O(n).

A priority queue with updates

Real priority queues hold structs. If priorities change after insertion, store each item's current index and call heap.Fix after changing it. heap.Remove(h, i) removes an element from any position.

Go Tasks ordered by priority, with an update

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with bufio.Scanner or fmt.Scan), it gets the next line from this box.

Setting old[n-1] = nil in Pop matters for slices of pointers: otherwise the hidden slot beyond the new length keeps the object alive. The same trick appears in Slices.

Priority queues are the heart of Dijkstra's shortest-path algorithm and of "merge k sorted lists". A common "top K" pattern keeps a min-heap of size K: push each new value, and when the heap grows beyond K, pop the smallest.

Go Top 3 largest values with a size-limited min-heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with bufio.Scanner or fmt.Scan), it gets the next line from this box.

container/list: a doubly linked list

container/list is a doubly linked list of *list.Element values. Each element has a Value field of type any, plus Next() and Prev(). Adding or removing at either end, or next to an element you already hold, takes O(1) time. Finding the nth element, however, is O(n), so a slice is usually better for plain sequences.

Go Building and walking a list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with bufio.Scanner or fmt.Scan), it gets the next line from this box.

The zero value of list.List is ready to use too: var l list.List. Because values are any, the compiler cannot check what you store, so you need a type assertion when reading (see Type Assertions and Switches). Generic third-party lists exist, but for most programs a slice or a small custom type is enough.

Example: an LRU cache

A least-recently-used cache needs two things: look up by key quickly (a map) and move an entry to the "most recent" end in O(1) (a linked list). Combine them: the map stores *list.Element pointers.

Go A small LRU cache

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with bufio.Scanner or fmt.Scan), it gets the next line from this box.

This cache is not safe for concurrent use. To share it between goroutines, guard it with a mutex from the sync package.

container/ring: a circular list

A container/ring Ring has no beginning or end: every element points to the next one, and the last points back to the first. A *ring.Ring is itself one element, and you can start from any of them. Typical uses are round-robin selection and a fixed-size window of recent values.

Go Walking and rotating a ring

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with bufio.Scanner or fmt.Scan), it gets the next line from this box.

Len is O(n) on a ring, because it has to walk around once. Link joins two rings and Unlink(n) removes n elements after the current one.

Choosing the right structure

Need Use
Ordered sequence, index access a slice
Smallest or largest item first container/heap
O(1) insert and remove in the middle, given an element container/list
Rotating, fixed-size data container/ring or a slice with an index
Key lookup a map (often combined with the above)

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. To add an item to a heap you defined, which call is correct?

    heap.Push calls your Push method and then restores the heap order. Calling your method directly would break the ordering.
  2. 2. How do you turn IntHeap into a max-heap?

    The element for which Less returns true comes out first, so flipping the comparison flips the order.
  3. 3. What must you call after changing the priority of an item already in the heap?

    heap.Fix restores the ordering for one element whose value changed; it needs the element's current index.
  4. 4. What is the type of list.Element.Value?

    container/list predates generics and stores any, so reading a value back requires an assertion such as e.Value.(int).
  5. 5. Why does an LRU cache combine a map and a linked list?

    The map finds the element in O(1); MoveToFront and Remove on the list are also O(1), so both get and put stay fast.

Summary

  • container/heap turns any type implementing heap.Interface (sort methods plus Push and Pop) into a priority queue; use heap.Push, heap.Pop, heap.Fix, heap.Remove and heap.Init.
  • Less decides the order: < gives a min-heap, > a max-heap. Push and pop cost O(log n); peeking at index 0 is O(1).
  • container/list is a doubly linked list with O(1) insertion and removal around an element; values are any.
  • An LRU cache is a map of keys to list elements plus a list ordered by recent use.
  • container/ring is a circular list for round-robin and fixed windows.
  • For simple ordered data, a slice is almost always the better choice.

Next: Embedding Files with go:embed shows how to ship templates and assets inside your binary.