list

Documentation

Overview

Package list contains the implementation of a type-safe, intrusive, doubly-linked list.

The standard library provides an implementation of a non-intrusive doubly-linked list in the container/list package. Non-intrusive means that the list tracks values via an intermediary object, which carries a reference to the actual values. This double indirection level often impacts usability of the code, and requires programs to maintain more (often circular) references, which are error prone and make the code harder to read. The indirections also increase the number of objects allocated on the heap, and the chances of CPU cache misses by requiring more pointer lookups to access the data.

The linked list implementation in this package adopts a different approach to enable programs to use lists without the hassle of managing an indirection layer. Values inserted in the list must be struct types which contain a field of type list.Node, that the list uses to link the values together without requiring an extra object.

The list.List type also implements a type-checking mechanism to guarantee that all values inserted in the list are of the same type. Programs that attempt to insert values of different types in the list will receive panics.

Index

• type List
  • func (list *List) Back() interface{}
  • func (list *List) Front() interface{}
  • func (list *List) Len() int
  • func (list *List) MoveToBack(elem interface{})
  • func (list *List) MoveToFront(elem interface{})
  • func (list *List) Next(elem interface{}) interface{}
  • func (list *List) Prev(elem interface{}) interface{}
  • func (list *List) PushBack(elem interface{})
  • func (list *List) PushBackList(other *List)
  • func (list *List) PushFront(elem interface{})
  • func (list *List) PushFrontList(other *List)
  • func (list *List) Remove(elem interface{})
  • func (list *List) RemoveAll()
  • func (list *List) RemoveBack() interface{}
  • func (list *List) RemoveFront() interface{}
• type Node

Types

type List

type List struct {
	// contains filtered or unexported fields
}

List values are containers of objects which support insertion and removal at the front and back of the list, as well as removal of elements at any position in O(1).

The values inserted in the list must be passed as pointers to struct values of types that contain a list.Node field.

func (*List) Back

func (list *List) Back() interface{}

Back returns the element at the back of the list, or nil if the list is empty.

func (*List) Front

func (list *List) Front() interface{}

Front returns the element at the front of the list, or nil if the list is empty.

func (*List) Len

func (list *List) Len() int

Len returns the number of elements in the list.

func (*List) MoveToBack

func (list *List) MoveToBack(elem interface{})

MoveToBack moves elem at the back of the list.

The operation is idempotent, it does nothing if elem is already at the back of the list. If elem is not part of the list, it is simply inserted at the back.

The method panics the type of elem doesn't match the type of other values in the list.

func (*List) MoveToFront

func (list *List) MoveToFront(elem interface{})

MoveToFront moves elem at the front of the list.

The operation is idempotent, it does nothing if elem is already at the front of the list. If elem is not part of the list, it is simply inserted at the front.

The method panics the type of elem doesn't match the type of other values in the list.

func (*List) Next

func (list *List) Next(elem interface{}) interface{}

Next returns the element right after elem in the list, or nil if the list is empty.

Next can be used to iterate forward through the list:

for elem := list.Front(); elem != nil; elem = list.Next(elem) {
	...
}

The method panics the type of elem doesn't match the type of other values in the list.

func (*List) Prev

func (list *List) Prev(elem interface{}) interface{}

Prev returns the element right before elem in the list, or nil if the list is empty.

Prev can be used to iterate backward through the list:

for elem := list.Back(); elem != nil; elem = list.Prev(elem) {
	...
}

The method panics the type of elem doesn't match the type of other values in the list.

func (*List) PushBack

func (list *List) PushBack(elem interface{})

PushBack inserts elem at the back of the list.

The method panics if elem is already part of a list, or if its type doesn't match the type of other values in the list.

func (*List) PushBackList

func (list *List) PushBackList(other *List)

PushBackList inserts other at the front of the list. The operation runs in constant time.

The method panics if the type of values in other differs from the type of values in list.

func (*List) PushFront

func (list *List) PushFront(elem interface{})

PushFront inserts elem at the front of the list.

The method panics if elem is already part of a list, or if its type doesn't match the type of other values in the list.

func (*List) PushFrontList

func (list *List) PushFrontList(other *List)

PushFrontList inserts other at the front of the list. The operation runs in constant time.

The method panics if the type of values in other differs from the type of values in list.

func (*List) Remove

func (list *List) Remove(elem interface{})

Remove removes elem from the list.

If elem is nil, the method does nothing.

The method panics the type of elem doesn't match the type of other values in the list.

func (*List) RemoveAll

func (list *List) RemoveAll()

Removeall removes all elements from the list. The operation runs in constant time.

func (*List) RemoveBack

func (list *List) RemoveBack() interface{}

RemoveBack removes the element at the back of the list and returns it, or returns nil if the list was empty.

This method is a more efficient equivalent to:

list.Remove(list.Back())

func (*List) RemoveFront

func (list *List) RemoveFront() interface{}

RemoveFront removes the element at the front of the list and returns it, or returns nil if the list was empty.

This method is a more efficient equivalent to:

list.Remove(list.Front())

type Node

type Node struct {
	// contains filtered or unexported fields
}

Node values must be embedded as a struct field in the values inserted in a list.

Typically, an unnamed field would be used to embed the list.Node value:

type Person struct {
	FirstName string
	LastName  string
	// Declaring this field allows values of the Person type to be
	// inserted in linked lists.
	_ list.Node
}

Note that the list.Node field does not have to be at a specific position in the struct, and may also be part of an embedded struct field. In this example, the type T can be inserted in a list because its embedded value of type S which has a list.Node field:

type S struct {
	Name string
	node list.Node
}

type T struct {
	Time time.Time
	S
}

If multiple fields of type list.Node are declared in the struct, the first one is always used and the other ones are ignored.