Skip to content
Tutorials Center
My learning

Topics

Go Reference ยท Collections: sort, slices, maps

Go container/list, heap and ring packages

Reference for Go's container packages: container/list doubly linked lists, container/heap priority queues and container/ring circular lists, with examples.

The standard library has three small data-structure packages under container/. container/list is a doubly linked list, container/heap turns any type with a few methods into a priority queue, and container/ring is a circular list with no beginning or end.

They predate generics, so list and ring store values of type any and you need a type assertion when you read an element back. In everyday code a slice or a map is usually the better choice; reach for these packages when you need cheap removal from the middle of a sequence, a priority queue, or a rotating window.

Go
l := list.New()
l.PushBack("a")
l.PushFront("b")
for e := l.Front(); e != nil; e = e.Next() {
	fmt.Println(e.Value)
}

Try it

Go container/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.

Go container/heap and container/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.

Syntax

container/list:

Go
func New() *List
func (l *List) PushFront(v any) *Element
func (l *List) PushBack(v any) *Element
func (l *List) InsertBefore(v any, mark *Element) *Element
func (l *List) InsertAfter(v any, mark *Element) *Element
func (l *List) Remove(e *Element) any
func (l *List) MoveToFront(e *Element)
func (l *List) Front() *Element
func (l *List) Back() *Element
func (l *List) Len() int

container/heap works on any type that implements this interface, where Push and Pop change the length of the underlying slice:

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

func Init(h Interface)
func Push(h Interface, x any)
func Pop(h Interface) any
func Remove(h Interface, i int) any
func Fix(h Interface, i int)

container/ring:

Go
func New(n int) *Ring
func (r *Ring) Next() *Ring
func (r *Ring) Prev() *Ring
func (r *Ring) Move(n int) *Ring
func (r *Ring) Link(s *Ring) *Ring
func (r *Ring) Unlink(n int) *Ring
func (r *Ring) Len() int
func (r *Ring) Do(f func(any))
Name Description
Element.Value The stored value (any). Next() and Prev() return the neighbors or nil at the ends.
heap.Init Builds a heap from an unordered slice in O(n).
heap.Fix(h, i) Restores the order after the element at index i changed its priority.
ring.Value The value of one ring element; a ring is itself one of its elements.

Edge cases: removing an element that belongs to another list does nothing; ring.Len is O(n); the heap Pop method you write removes the last element, and heap.Pop is what returns the smallest (by Less).

Usage notes

  • A zero list.List is ready to use, so var l list.List works without list.New().
  • Call heap.Push and heap.Pop, not your own methods. The package functions move the element into the right place; calling q.Push directly breaks the heap order.
  • Less decides the kind of heap. < gives a min-heap; > a max-heap, as in the priority queue above.
  • Iterating a heap slice is not sorted. Only the first element is guaranteed to be the best; pop repeatedly to get sorted order.
  • Complexity: list insert/remove is O(1) with an element handle; heap.Push/Pop are O(log n); heap.Init is O(n).
  • No typed values. You need e.Value.(string); wrap a list in your own generic type if you want compile-time safety.
  • Linked lists are slow in practice because of pointer chasing and allocations. Benchmark before choosing one over a slice.