list

Documentation

Overview

Package list provides an intrusive circular double linked list. The most useful property is that a list node can remove itself from any list without having a reference to one. This is useful to implement certain algorithms such as timers or priority queues where the list a list node is stored in may be unknown.

Illustration of element nodes forming a circular list. One of the elements is dedicated to the role of list head and does not carry any valid data.

+------------------------------------+
|                                    |
+--> +----+ --> +----+ --> +----+ -->+
     |Elem|     |Elem|     |Elem|
+<-- +----+ <-- +----+ <-- +----+ <--+
|                                    |
+------------------------------------+

Index

• type Node
  • func New[T any]() *Node[T]
  • func (node *Node[T]) InitLinks() *Node[T]
  • func (node *Node[T]) IsLinked() bool
  • func (node *Node[T]) LinkNext(other *Node[T])
  • func (node *Node[T]) LinkPrev(other *Node[T])
  • func (node *Node[T]) Next() *Node[T]
  • func (node *Node[T]) Prev() *Node[T]
  • func (node *Node[T]) Unlink()

Types

type Node

type Node[T any] struct {
	Value T // Value carried by the node that may be accessed directly.
	// contains filtered or unexported fields
}

Node is a list node carrying a value of type T. A sentinel node is used to represent the list head. The zero value is not a valid node as its prev and next pointers must be initialized.

func New

func New[T any]() *Node[T]

New returns a node on which list operations may be performed.

func (*Node[T]) InitLinks

func (node *Node[T]) InitLinks() *Node[T]

InitLinks initializes a node so that list operations may be performed on it. This method should be used to initialize list nodes for which the user manages memory. It should not be used when New was used to allocate a node

func (*Node[T]) IsLinked

func (node *Node[T]) IsLinked() bool

IsLinked reports whether node is linked to another node. The method reports if a list is non-empty when applied to a list head node.

func (*Node[T]) LinkNext

func (node *Node[T]) LinkNext(other *Node[T])

LinkNext links other next to node.

func (*Node[T]) LinkPrev

func (node *Node[T]) LinkPrev(other *Node[T])

LinkPrev links other previous to node.

func (*Node[T]) Next

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

Next returns the node next to node. This may be node itself if unlinked and pointing to itself.

func (*Node[T]) Prev

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

Prev returns the node previous to node. This may be node itself if unlinked and pointing to itself.

func (*Node[T]) Unlink

func (node *Node[T]) Unlink()

Unlink removes node from its list. It's safe to unlink unlinked nodes.