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.
l := list.New() l.PushBack("a") l.PushFront("b") for e := l.Front(); e != nil; e = e.Next() { fmt.Println(e.Value) }
Try it
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.
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:
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:
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:
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.Listis ready to use, sovar l list.Listworks withoutlist.New(). - Call
heap.Pushandheap.Pop, not your own methods. The package functions move the element into the right place; callingq.Pushdirectly breaks the heap order. Lessdecides 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:
listinsert/remove is O(1) with an element handle;heap.Push/Popare O(log n);heap.Initis 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.
Related
sort,sort.Interface,slices, Slices- Lessons: container/heap, list and ring, Sorting