linked

package module
v0.1.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Aug 11, 2025 License: MIT Imports: 3 Imported by: 0

README

linked - Generic Linked List

linked is a package implementing a doubly linked list for Go.

Coverage Docs

Features

  • No dependencies: zero 3rd party dependencies.
  • Generics: no need to use any or interface{} (unless you really want to).
  • Iterators: provides both range (as in iter.Seq) and object-based iterators.
  • ...and more: this package provides plenty in the way of features/ergonomics, but enumerating them is currently a TODO item 🙂

Getting Started

Install:

go get github.com/sbueschel/go-linked

Usage:

package main

import (
    "fmt"

    "github.com/sbueschel/go-linked"
)

func main() {
    var list linked.List[int]

    for n := range 10 {
        list.PushFront(n)
    }

    list.ForEach(func(v int) { fmt.Printf("%d\n", v) })
}

Documentation

Overview

Package linked provides a doubly-linked list implementation with support for generics.

Index

Examples

Constants

View Source 
const (
	Left  = Edge(iota) // Left edge of a [List] or [Node].
	Right              // Right edge of a [List] or [Node].
)
View Source 
const (
	Before = Left
	Prev   = Left
	Front  = Left
)

Aliases for Left (for the pedantic amongst us).

View Source 
const (
	After = Right
	Next  = Right
	Back  = Right
)

Aliases for Right (for the pedantic amongst us).

Variables

This section is empty.

Functions

func NoopSeq 

func NoopSeq[T any](_ func(T) bool)

NoopSeq is a no-op iter.Seq that never yields anything.

Types

type Edge 

type Edge int

Edge is a simple enumeration type which is used to refer to a Node relative to another Node or List. It has only two concrete values: Left and Right.

func (Edge) IsValid 

func (e Edge) IsValid() bool

IsValid indicates whether the receiver is considered a valid edge.

func (Edge) List 

func (e Edge) List() string

List returns "Front" or "Back" to describe which end of a List is referred to by this Edge.

func (Edge) Must 

func (e Edge) Must() Edge

Must returns the receiver if valid, otherwise it panics.

func (Edge) Node 

func (e Edge) Node() string

Node returns "Prev" or "Next" to describe the Node associated with this Edge.

func (Edge) Opposite 

func (e Edge) Opposite() Edge

Opposite returns the opposite value of the receiver or panics if the receiver is not a valid Edge.

func (Edge) String 

func (e Edge) String() string

String implements fmt.Stringer for Edge and returns the canonical name of the receiver ("Left" or "Right") or, if invalid, a string in the form of 

"(%!BadEdge(%d))"

func (Edge) Suffix 

func (e Edge) Suffix() string

Suffix returns the method suffix typically associated with the receiver when it is used as an argument in a List operation (either "Before" or "After"). If invalid, it returns a string in the form of 

"(%!BadEdge(%d))"

type Iterator 

type Iterator[T any] struct {
	// Node is the current position of the iterator. When nil, iteration has
	// completed. For performance reasons, the field is public, rather than
	// wrapped as a method.
	//
	// It is discouraged (but not always incorrect) to assign directly to this
	// field once iteration has started.
	Node *Node[T]

	// Pos is a pseudo-index which tracks the iteration position relative to
	// the origin [Node]. For performance reasons, the field is public, rather
	// than wrapped as a method.
	//
	// It is discouraged to assign directly to this field.
	Pos int
	// contains filtered or unexported fields
}

Iterator is a simple object-based iterator that provides leftward and rightward traversal of the Node objects found in a List.

Note: this object does *NOT* track any of the [Node]s that it has visited, and is therefore sensitive to any mutations of the associated List.

func (*Iterator[T]) All 

func (it *Iterator[T]) All() iter.Seq[*Node[T]]

All consumes this Iterator to yield all remaining [Node]s.

func (*Iterator[T]) Count 

func (it *Iterator[T]) Count() (n int)

Count returns the number of times this Iterator has been successfully advanced.

func (*Iterator[T]) Gather 

func (it *Iterator[T]) Gather() (values []T)

Gather expends the remainder of this Iterator, placing the value of each remaining Node into a slice. The slice is nil if the iterator is spent.

func (*Iterator[T]) Init 

func (it *Iterator[T]) Init(node *Node[T], backward ...bool)

Init initializes the Iterator, beginning at the given Node. Iteration occurs from Left to Right unless backward is true.

func (*Iterator[T]) Into 

func (it *Iterator[T]) Into(dst []T) (n int)

Into advances the iterator up to len(dst) times, placing the value of each yielded Node into the given slice at the next position. Returns the number of values placed into the slice.

func (*Iterator[T]) IsBackward 

func (it *Iterator[T]) IsBackward() bool

IsBackward indicates if this Iterator is iterating in reverse order.

func (*Iterator[T]) Next 

func (it *Iterator[T]) Next() bool

Next advances the iterator. It returns true if the Node on the Iterator can be safely read or false if it will be nil.

func (*Iterator[T]) Version 

func (it *Iterator[T]) Version() uint

Version returns the value of List.Version at the time Iterator.Init was called, useful for detecting if the List has mutated (though it won't tell you where or how).

type List 

type List[T any] struct {
	// contains filtered or unexported fields
}

List implements a doubly-linked list. The zero value of a List is ready to use. Must not be modified concurrently.

func New 

func New[T any](values []T, backward ...bool) *List[T]

New creates a new doubly-linked List, initially populated with the values of the given slice (which may be nil). If backward is true, they are placed into the List in reverse order.

func (*List[T]) All 

func (l *List[T]) All() iter.Seq[T]

All iterates over all values in this List, from Front to Back.

func (*List[T]) Back 

func (l *List[T]) Back() *Node[T]

Back returns the last Node in this List, or nil if empty.

func (*List[T]) Backward 

func (l *List[T]) Backward() iter.Seq[T]

Backward iterates over all values in this List, from Back to Front.

func (*List[T]) Clear 

func (l *List[T]) Clear() *List[T]

Clear removes all elements in this List. Returns the receiver.

func (*List[T]) Copy 

func (l *List[T]) Copy() *List[T]

Copy creates an exact copy of this List and Node objects. The [Node]s of the new List will be allocated in contiguous memory space, if possible (OS and runtime dependent).

func (*List[T]) Edge 

func (l *List[T]) Edge(edge Edge) *Node[T]

Edge returns the Node on the Left or Right edge of this List, or panics if edge is invalid.

func (*List[T]) ForEach 

func (l *List[T]) ForEach(fn func(v T), backward ...bool)

ForEach iterates over the values of this List and executes the given function for each value. If backward is true, it iterates in reverse order.

Example 
list := linked.New([]string{"A", "B", "C", "D"})
list.ForEach(func(v string) { fmt.Println(v) })
list.ForEach(func(v string) { fmt.Println(v) }, true) // reverse order

Output:
A
B
C
D
D
C
B
A

func (*List[T]) Front 

func (l *List[T]) Front() *Node[T]

Front returns the first Node in this List, or nil if empty.

func (*List[T]) Insert 

func (l *List[T]) Insert(v T, target *Node[T], edge Edge) *Node[T]

Insert places a new value into this List on the Left or Right edge of the target Node. If the target is nil, it implies the Node on the specified Edge of this List (behaving as List.Push does).

If target does not belong to this List, this method is a no-op and returns nil to indicate failure.

The edge must be valid, otherwise this method panics.

On success returns the Node of the value that was just inserted.

func (*List[T]) InsertAfter 

func (l *List[T]) InsertAfter(v T, target *Node[T]) *Node[T]

InsertAfter inserts a new value After the target Node using List.Insert.

func (*List[T]) InsertBefore 

func (l *List[T]) InsertBefore(v T, target *Node[T]) *Node[T]

InsertBefore inserts a new value Before the target Node using List.Insert.

func (*List[T]) InsertMany 

func (l *List[T]) InsertMany(values []T, target *Node[T], edge Edge, backward ...bool) (*Node[T], *Node[T])

InsertMany efficiently inserts an entire slice of values into this List Before or After the target Node.

If backward is true, the values are inserted in reverse order.

If the target Node is nil, it implies the Node on the specified Edge of this List. Otherwise, if the target is not a member of this List, this method is a no-op and returns two nil pointers to indicate failure.

The edge must be valid, otherwise this method panics.

On success, returns the first and last [Node]s that were inserted.

func (*List[T]) InsertManyAfter 

func (l *List[T]) InsertManyAfter(values []T, target *Node[T], backward ...bool) (*Node[T], *Node[T])

InsertManyAfter inserts the slice of values After the target Node using List.InsertMany.

Example 
list := linked.New([]string{"G", "A"})

target := list.Front()
oldPeer := target.Next()

left, right := list.InsertManyAfter(
	[]string{"B", "C", "D", "E", "F"},
	target,
	true, // reverse the order when inserting
)

fmt.Printf("inserted %q after %q\n", left.Value, target.Value)
fmt.Printf("inserted %q before %q\n", right.Value, oldPeer.Value)
list.ForEach(func(v string) { fmt.Println(v) })

Output:
inserted "F" after "G"
inserted "B" before "A"
G
F
E
D
C
B
A

func (*List[T]) InsertManyBefore 

func (l *List[T]) InsertManyBefore(values []T, target *Node[T], backward ...bool) (*Node[T], *Node[T])

InsertManyBefore inserts the slice of values Before the target Node using List.InsertMany.

Example 
list := linked.New([]string{"A", "G"})

target := list.Back()
oldPeer := target.Prev()

left, right := list.InsertManyBefore([]string{"B", "C", "D", "E", "F"}, target)

fmt.Printf("inserted %q after %q\n", left.Value, oldPeer.Value)
fmt.Printf("inserted %q before %q\n", right.Value, target.Value)
list.ForEach(func(v string) { fmt.Println(v) })

Output:
inserted "B" after "A"
inserted "F" before "G"
A
B
C
D
E
F
G

func (*List[T]) IsMember 

func (l *List[T]) IsMember(node *Node[T]) bool

IsMember indicates if the given Node belongs to this List. The Node must not be nil. Always returns false if this List is nil.

func (*List[T]) Iter 

func (l *List[T]) Iter(backward ...bool) (it Iterator[T])

Iter returns an Iterator which traverses the [Node]s of this List from Front to Back, or from Back to Front if backward is true.

Example 
list := linked.New([]string{"A", "B", "C", "D", "E", "F", "G"})

for it := list.Iter(); it.Next(); {
	fmt.Printf("%q // pos=%d, count=%d\n", it.Node.Value, it.Pos, it.Count())
}

Output:
"A" // pos=0, count=1
"B" // pos=1, count=2
"C" // pos=2, count=3
"D" // pos=3, count=4
"E" // pos=4, count=5
"F" // pos=5, count=6
"G" // pos=6, count=7

func (*List[T]) Len 

func (l *List[T]) Len() int

Len returns the length of this List with O(1) time complexity.

func (*List[T]) Move 

func (l *List[T]) Move(node, target *Node[T], edge Edge) *Node[T]

Move moves the given Node so that it occurs Before or After the target Node. If the target is nil, it implies the Node on the specified Edge of this List. The node which is being moved must not be nil. The edge must also be valid, otherwise this method panics.

If either Node does not belong to this List, this method is a no-op and returns nil to indicate failure.

On success, returns the (same) Node that was moved.

func (*List[T]) MoveAfter 

func (l *List[T]) MoveAfter(node, target *Node[T]) *Node[T]

MoveAfter moves the given Node to the Right of the target Node using List.Move.

func (*List[T]) MoveBefore 

func (l *List[T]) MoveBefore(node, target *Node[T]) *Node[T]

MoveBefore moves the given Node to the Left of the target Node using List.Move.

func (*List[T]) MoveToBack 

func (l *List[T]) MoveToBack(node *Node[T]) *Node[T]

MoveToBack moves the given Node to the Back edge of this List in the same manner as described by List.MoveToEdge.

func (*List[T]) MoveToEdge 

func (l *List[T]) MoveToEdge(node *Node[T], edge Edge) *Node[T]

MoveToEdge efficiently moves the given Node to the Front or Back Edge of this List. The node must not be nil and the edge must be valid, otherwise this method panics.

If the Node doesn't belong to this List, this method is a no-op and returns nil to indicate failure.

On success, returns the same Node. See also: List.MoveToFront and List.MoveToBack, which are slightly more efficient.

func (*List[T]) MoveToFront 

func (l *List[T]) MoveToFront(node *Node[T]) *Node[T]

MoveToFront moves the given Node to the Front edge of this List in the same manner as described by List.MoveToEdge.

func (*List[T]) Pop 

func (l *List[T]) Pop(edge Edge) (node *Node[T])

Pop removes and returns the node from the Front or Back of this List, or returns nil if empty. The edge must be valid, otherwise this method panics.

func (*List[T]) PopBack 

func (l *List[T]) PopBack() (node *Node[T])

PopBack removes and returns Back Node via List.Pop.

Example 
list := linked.New([]int{1, 2, 3, 4, 5})

for list.Len() > 0 {
	fmt.Printf("%d\n", list.PopBack().Value)
}

Output:
5
4
3
2
1

func (*List[T]) PopFront 

func (l *List[T]) PopFront() (node *Node[T])

PopFront removes and returns Front Node via List.Pop.

Example 
list := linked.New([]int{1, 2, 3, 4, 5})

for list.Len() > 0 {
	fmt.Printf("%d\n", list.PopFront().Value)
}

Output:
1
2
3
4
5

func (*List[T]) Push 

func (l *List[T]) Push(v T, edge Edge) *Node[T]

Push inserts a new value at the Front or Back of this List and returns the Node that stores the value. The edge must be valid, otherwise this method panics.

func (*List[T]) PushBack 

func (l *List[T]) PushBack(v T) *Node[T]

PushBack pushes a new value to the Back of this List via List.Push.

Example 
var list linked.List[int]

for v := range 5 {
	list.PushBack(v)
}

list.ForEach(func(v int) { fmt.Printf("%d\n", v) })

Output:
0
1
2
3
4

func (*List[T]) PushFront 

func (l *List[T]) PushFront(v T) *Node[T]

PushFront pushes a new value to the Front of this List via List.Push.

Example 
var list linked.List[int]

for v := range 5 {
	list.PushFront(v)
}

list.ForEach(func(v int) { fmt.Printf("%d\n", v) })

Output:
4
3
2
1
0

func (*List[T]) Remove 

func (l *List[T]) Remove(node *Node[T]) T

Remove deletes the given Node from this List. The Node must not be nil. Does nothing if the Node does not belong to this List. Always returns the value stored on the Node.

func (*List[T]) Rotate 

func (l *List[T]) Rotate(steps int, edge Edge) *List[T]

Rotate rotates the [Node]s of this List by the specified number of steps to the Left or Right, as determined by Edge. The edge must be valid. This method is a no-op if steps is less than 1 or a multiple of List.Len. The number of steps can be greater than the list length, which reduces via: 

steps %= list.Len()

Always returns the receiver (this List).

func (*List[T]) RotateLeft 

func (l *List[T]) RotateLeft(steps int) *List[T]

RotateLeft rotates this List to the Left by the specified number of steps using List.Rotate.

func (*List[T]) RotateRight 

func (l *List[T]) RotateRight(steps int) *List[T]

RotateRight rotates this List to the Right by the specified number of steps using List.Rotate.

func (*List[T]) Take 

func (l *List[T]) Take(inherit, target *Node[T], edge Edge) *Node[T]

Take inherits a Node that does not belong to this List, placing it into the List Before or After the target Node. If the target is nil, it implies the Node on the specified Edge of this List.

If the Node to inherit already belongs to this List, or the target Node *does not* belong to this List, this method is a no-op and returns nil to indicate failure.

The Node to inherit must not be nil and the edge must be valid, otherwise this method panics.

Returns the inherited Node on success.

func (*List[T]) TakeAfter 

func (l *List[T]) TakeAfter(inherit, target *Node[T]) *Node[T]

TakeAfter inherits a Node, inserting it After the target Node using List.Take.

func (*List[T]) TakeBefore 

func (l *List[T]) TakeBefore(inherit, target *Node[T]) *Node[T]

TakeBefore inherits a Node, inserting it Before the target Node using List.Take.

func (*List[T]) Version 

func (l *List[T]) Version() uint

Version returns the current version of this List. The version is incremented each time this List is successfully mutated.

type Node 

type Node[T any] struct {
	Value T
	// contains filtered or unexported fields
}

Node represents an element of a List.

func (*Node[T]) All 

func (n *Node[T]) All() iter.Seq[T]

All yields the value stored in this Node and the value of each Node which occurs After it (i.e. iterates from Front to Back).

func (*Node[T]) Backward 

func (n *Node[T]) Backward() iter.Seq[T]

Backward yields the value stored in this Node and the value of each Node which occurs Before it (i.e. iterates from Back to Front).

func (*Node[T]) IsBack 

func (n *Node[T]) IsBack() bool

IsBack indicates if this Node is at the Back of its List using Node.IsEdge.

func (*Node[T]) IsEdge 

func (n *Node[T]) IsEdge(edge Edge) bool

IsEdge indicates if this Node is at the given Edge of its List. The edge must be valid, otherwise this method panics.

func (*Node[T]) IsFront 

func (n *Node[T]) IsFront() bool

IsFront indicates if this Node is at the Front of its List using Node.IsEdge.

func (*Node[T]) IsMember 

func (n *Node[T]) IsMember(of *List[T]) bool

IsMember indicates if this Node is a member of the given List. If the given List is nil, indicates if this Node is orphaned.

func (*Node[T]) IsOrphan 

func (n *Node[T]) IsOrphan() bool

IsOrphan indicates if this Node does not belong to a List.

func (*Node[T]) Iter 

func (n *Node[T]) Iter(backward ...bool) (it Iterator[T])

Iter returns an Iterator which begins at (and is inclusive of) this Node. Consumes up to one optional argument indicating if reverse iteration is desired. Calling this method against a nil receiver never panics.

func (*Node[T]) Move 

func (n *Node[T]) Move(target *Node[T], edge Edge) *Node[T]

Move moves this Node to the Left or Right Edge of the target Node using List.Move. On success, returns the receiver, otherwise nil.

func (*Node[T]) MoveAfter 

func (n *Node[T]) MoveAfter(target *Node[T]) *Node[T]

MoveAfter moves this Node to the Right Edge of the target Node using Node.Move.

func (*Node[T]) MoveBefore 

func (n *Node[T]) MoveBefore(target *Node[T]) *Node[T]

MoveBefore moves this Node to the Left Edge of the target Node using Node.Move.

func (*Node[T]) MoveToBack 

func (n *Node[T]) MoveToBack() *Node[T]

MoveToBack moves this Node to the Back of its List using Node.MoveToEdge.

func (*Node[T]) MoveToEdge 

func (n *Node[T]) MoveToEdge(edge Edge) *Node[T]

MoveToEdge moves this Node to the Front or Back edge of its List. Returns the receiver if this Node belongs to any List, otherwise nil. Edge must be Left, Right, or an alias thereof.

func (*Node[T]) MoveToFront 

func (n *Node[T]) MoveToFront() *Node[T]

MoveToFront moves this Node to the Front of its List using Node.MoveToEdge.

func (*Node[T]) Next 

func (n *Node[T]) Next() *Node[T]

Next returns the Node on the Right edge of the receiver, if any.

func (*Node[T]) OK 

func (n *Node[T]) OK() bool

OK returns true if the receiver is non-nil without causing a panic. This is intended for convenience as a shortcut for determining if a List operation was successful.

func (*Node[T]) Peer 

func (n *Node[T]) Peer(edge Edge) *Node[T]

Peer returns the Node to the Left or Right edge of this Node, if any. Panics if edge is invalid.

func (*Node[T]) Pop 

func (n *Node[T]) Pop() *Node[T]

Pop removes this Node from the List to which it belongs, if any. Always returns itself.

func (*Node[T]) Prev 

func (n *Node[T]) Prev() *Node[T]

Prev returns Node on the Left edge of the receiver, if any.

func (*Node[T]) Remove 

func (n *Node[T]) Remove() T

Remove removes this Node from the List to which it belongs (if any) and then returns the value it stores.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.