Data Structures

Ring

container/ring implements a circular linked list. There's no head or tail, only a current position that can move around the loop forever.

The shape

Circular doubly-linked list

Every element links to the next and back to the previous, and the last one links to the first.

Next: step one element forward.
Prev: step one element back.
Move: jump several elements in either direction.
Do: run a function over every element, starting where you stand.

Press Next(), Prev() or Move(2) to walk the loop. The green ring is where you are standing.

Purpose

Cycle through a fixed set of elements with no end to fall off.

Input

ring.New(n), then a value written into each element in turn.

Output

A *ring.Ring pointing at whichever element you last stepped to.

Constraints

The length is fixed when the ring is created.
There is no first element. Any element can act as the starting point.
Walking with Next comes back around forever, so count the steps yourself or use Do.

ring.New(n int) *Ring builds a ring of n elements up front, already linked into a closed loop, and returns a pointer to one of them. Each element has a Value any field to fill in.

r := ring.New(5) // *ring.Ring, already linked into a loop of 5

for i := 0; i < r.Len(); i++ {
    r.Value = i * 10
    r = r.Next()
}

Next() *Ring and Prev() *Ring return the neighboring element without mutating the ring itself, so the result has to be reassigned to move. Move(n int) *Ring does the same thing n times in one call; negative n moves backward.

r = r.Next() // step one element forward
fmt.Println(r.Value)

r = r.Prev() // step back to where we started
fmt.Println(r.Value)

r = r.Move(2) // jump forward 2 elements in one call

Do(f func(any)) calls f once for every element, starting at the current position and going forward exactly Len() steps. It doesn't move the ring's own pointer.

r.Do(func(v any) {
    fmt.Print(v, " ")
})

The whole program main.go Show

package main

import (
    "container/ring"
    "fmt"
)

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

    for i := 0; i < r.Len(); i++ {
        r.Value = i * 10
        r = r.Next()
    }

    r.Do(func(v any) {
        fmt.Print(v, " ")
    })
    fmt.Println()

    r = r.Move(2)
    fmt.Println(r.Value)
}

Filling the ring by calling Next() five times lands back where it started, since Len() is 5. Do then walks the full loop once from there.

Terminal

$ go run ring.go
0 10 20 30 40 
20

Previous Queue Next Topic Set