Skip to main content
The container package provides implementations of common data structures.

​
Heap

Package heap provides heap operations for any type that implements heap.Interface. A heap is a tree with the property that each node is the minimum-valued node in its subtree.

​
Interface

The Interface type describes the requirements for a type using the routines in this package. 
type Interface interface {
    sort.Interface
    Push(x any) // add x as element Len()
    Pop() any   // remove and return element Len() - 1
}
​
sort.Interface
interface
Embedded interface requiring Len(), Less(i, j int), and Swap(i, j int) methods
​
Push
func(x any)
Add x as element at index Len()
​
Pop
func() any
Remove and return element at index Len() - 1

​
Functions

​
Init

func Init(h Interface)
Establishes the heap invariants required by the other routines in this package. Init is idempotent and may be called whenever the heap invariants may have been invalidated.
​
h
Interface
required
The heap to initialize
​
complexity
string
O(n) where n = h.Len()

​
Push

func Push(h Interface, x any)
Pushes the element x onto the heap.
​
h
Interface
required
The heap to push onto
​
x
any
required
The element to push
​
complexity
string
O(log n) where n = h.Len()

​
Pop

func Pop(h Interface) any
Removes and returns the minimum element (according to Less) from the heap.
​
h
Interface
required
The heap to pop from
​
return
any
The minimum element from the heap
​
complexity
string
O(log n) where n = h.Len()

​
Remove

func Remove(h Interface, i int) any
Removes and returns the element at index i from the heap.
​
h
Interface
required
The heap to remove from
​
i
int
required
The index of the element to remove
​
return
any
The removed element
​
complexity
string
O(log n) where n = h.Len()

​
Fix

func Fix(h Interface, i int)
Re-establishes the heap ordering after the element at index i has changed its value. Changing the value of the element at index i and then calling Fix is equivalent to, but less expensive than, calling Remove(h, i) followed by a Push of the new value.
​
h
Interface
required
The heap to fix
​
i
int
required
The index of the changed element
​
complexity
string
O(log n) where n = h.Len()

​
Example: Priority Queue

package main

import (
    "container/heap"
    "fmt"
)

type Item struct {
    value    string
    priority int
    index    int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority > pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}

func (pq *PriorityQueue) Push(x any) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() any {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil
    item.index = -1
    *pq = old[0 : n-1]
    return item
}

func main() {
    items := map[string]int{
        "banana": 3, "apple": 2, "pear": 4,
    }

    pq := make(PriorityQueue, len(items))
    i := 0
    for value, priority := range items {
        pq[i] = &Item{
            value:    value,
            priority: priority,
            index:    i,
        }
        i++
    }
    heap.Init(&pq)

    item := &Item{value: "orange", priority: 1}
    heap.Push(&pq, item)

    for pq.Len() > 0 {
        item := heap.Pop(&pq).(*Item)
        fmt.Printf("%d:%s ", item.priority, item.value)
    }
    // Output: 4:pear 3:banana 2:apple 1:orange
}

​
List

Package list implements a doubly linked list.

​
Types

​
Element

type Element struct {
    Value any
}
An element of a linked list.
​
Value
any
The value stored with this element
Methods
Next 
func (e *Element) Next() *Element
Returns the next list element or nil. Prev 
func (e *Element) Prev() *Element
Returns the previous list element or nil.

​
List

type List struct {}
Represents a doubly linked list. The zero value for List is an empty list ready to use.

​
Functions

​
New

func New() *List
Returns an initialized list.
​
return
*List
A new initialized list

​
List Methods

​
Init

func (l *List) Init() *List
Initializes or clears list l.

​
Len

func (l *List) Len() int
Returns the number of elements of list l. Complexity is O(1).

​
Front

func (l *List) Front() *Element
Returns the first element of list l or nil if the list is empty.

​
Back

func (l *List) Back() *Element
Returns the last element of list l or nil if the list is empty.

​
PushFront

func (l *List) PushFront(v any) *Element
Inserts a new element e with value v at the front of list l and returns e.
​
v
any
required
The value to insert
​
return
*Element
The newly inserted element

​
PushBack

func (l *List) PushBack(v any) *Element
Inserts a new element e with value v at the back of list l and returns e.
​
v
any
required
The value to insert
​
return
*Element
The newly inserted element

​
InsertBefore

func (l *List) InsertBefore(v any, mark *Element) *Element
Inserts a new element e with value v immediately before mark and returns e. If mark is not an element of l, the list is not modified.
​
v
any
required
The value to insert
​
mark
*Element
required
The element to insert before

​
InsertAfter

func (l *List) InsertAfter(v any, mark *Element) *Element
Inserts a new element e with value v immediately after mark and returns e. If mark is not an element of l, the list is not modified.
​
v
any
required
The value to insert
​
mark
*Element
required
The element to insert after

​
Remove

func (l *List) Remove(e *Element) any
Removes e from l if e is an element of list l. It returns the element value e.Value.
​
e
*Element
required
The element to remove
​
return
any
The value of the removed element

​
MoveToFront

func (l *List) MoveToFront(e *Element)
Moves element e to the front of list l. If e is not an element of l, the list is not modified.

​
MoveToBack

func (l *List) MoveToBack(e *Element)
Moves element e to the back of list l. If e is not an element of l, the list is not modified.

​
MoveBefore

func (l *List) MoveBefore(e, mark *Element)
Moves element e to its new position before mark. If e or mark is not an element of l, or e == mark, the list is not modified.

​
MoveAfter

func (l *List) MoveAfter(e, mark *Element)
Moves element e to its new position after mark. If e or mark is not an element of l, or e == mark, the list is not modified.

​
PushBackList

func (l *List) PushBackList(other *List)
Inserts a copy of another list at the back of list l. The lists l and other may be the same.

​
PushFrontList

func (l *List) PushFrontList(other *List)
Inserts a copy of another list at the front of list l. The lists l and other may be the same.

​
Example

package main

import (
    "container/list"
    "fmt"
)

func main() {
    l := list.New()
    e4 := l.PushBack(4)
    e1 := l.PushFront(1)
    l.InsertBefore(3, e4)
    l.InsertAfter(2, e1)

    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Println(e.Value)
    }
    // Output:
    // 1
    // 2
    // 3
    // 4
}

​
Ring

Package ring implements operations on circular lists.

​
Type

​
Ring

type Ring struct {
    Value any // for use by client
}
A Ring is an element of a circular list, or ring. Rings do not have a beginning or end; a pointer to any ring element serves as reference to the entire ring. Empty rings are represented as nil Ring pointers. The zero value for a Ring is a one-element ring with a nil Value.
​
Value
any
Value stored in this ring element

​
Functions

​
New

func New(n int) *Ring
Creates a ring of n elements.
​
n
int
required
The number of elements in the ring
​
return
*Ring
A pointer to the created ring, or nil if n is less than or equal to 0

​
Ring Methods

​
Next

func (r *Ring) Next() *Ring
Returns the next ring element. r must not be empty.

​
Prev

func (r *Ring) Prev() *Ring
Returns the previous ring element. r must not be empty.

​
Move

func (r *Ring) Move(n int) *Ring
Moves n % r.Len() elements backward (n < 0) or forward (n >= 0) in the ring and returns that ring element. r must not be empty.
​
n
int
required
Number of elements to move (negative for backward, positive for forward)
​
return
*Ring
The ring element after moving n positions

​
Len

func (r *Ring) Len() int
Computes the number of elements in ring r. It executes in time proportional to the number of elements. 
func (r *Ring) Link(s *Ring) *Ring
Connects ring r with ring s such that r.Next() becomes s and returns the original value for r.Next(). r must not be empty. If r and s point to the same ring, linking them removes the elements between r and s from the ring. If r and s point to different rings, linking them creates a single ring with the elements of s inserted after r.
​
s
*Ring
required
The ring to link with
​
return
*Ring
The original value for r.Next()
func (r *Ring) Unlink(n int) *Ring
Removes n % r.Len() elements from the ring r, starting at r.Next(). If n % r.Len() == 0, r remains unchanged. The result is the removed subring. r must not be empty.
​
n
int
required
Number of elements to unlink
​
return
*Ring
The removed subring, or nil if n is less than or equal to 0

​
Do

func (r *Ring) Do(f func(any))
Calls function f on each element of the ring, in forward order. The behavior of Do is undefined if f changes *r.
​
f
func(any)
required
Function to call on each element

​
Example

package main

import (
    "container/ring"
    "fmt"
)

func main() {
    r := ring.New(5)

    n := r.Len()

    // Initialize the ring with integers
    for i := 0; i < n; i++ {
        r.Value = i
        r = r.Next()
    }

    // Iterate and print
    r.Do(func(p any) {
        fmt.Println(p.(int))
    })
    // Output:
    // 0
    // 1
    // 2
    // 3
    // 4
}

Build docs developers (and LLMs) love

Get started for freeTalk to us