list

package
v0.1.1 Latest Latest
Warning

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

 Go to latest Published: Sep 10, 2022 License: MIT Imports: 6 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type LinkedListDescendingIterator 

type LinkedListDescendingIterator[V any] struct {
	// contains filtered or unexported fields
}

func (*LinkedListDescendingIterator[V]) HasNext 

func (i *LinkedListDescendingIterator[V]) HasNext() bool

func (*LinkedListDescendingIterator[V]) HasPrevious 

func (i *LinkedListDescendingIterator[V]) HasPrevious() bool

func (*LinkedListDescendingIterator[V]) Next 

func (i *LinkedListDescendingIterator[V]) Next() V

func (*LinkedListDescendingIterator[V]) NextIndex 

func (i *LinkedListDescendingIterator[V]) NextIndex() int

func (*LinkedListDescendingIterator[V]) Previous 

func (i *LinkedListDescendingIterator[V]) Previous() V

func (*LinkedListDescendingIterator[V]) PreviousIndex 

func (i *LinkedListDescendingIterator[V]) PreviousIndex() int

func (*LinkedListDescendingIterator[V]) Remove 

func (i *LinkedListDescendingIterator[V]) Remove()

func (*LinkedListDescendingIterator[V]) Set 

func (i *LinkedListDescendingIterator[V]) Set(value V)

type LinkedListIterator 

type LinkedListIterator[V any] struct {
	// contains filtered or unexported fields
}

func (*LinkedListIterator[V]) HasNext 

func (i *LinkedListIterator[V]) HasNext() bool

func (*LinkedListIterator[V]) HasPrevious 

func (i *LinkedListIterator[V]) HasPrevious() bool

func (*LinkedListIterator[V]) Next 

func (i *LinkedListIterator[V]) Next() V

func (*LinkedListIterator[V]) NextIndex 

func (i *LinkedListIterator[V]) NextIndex() int

func (*LinkedListIterator[V]) Previous 

func (i *LinkedListIterator[V]) Previous() V

func (*LinkedListIterator[V]) PreviousIndex 

func (i *LinkedListIterator[V]) PreviousIndex() int

func (*LinkedListIterator[V]) Remove 

func (i *LinkedListIterator[V]) Remove()

func (*LinkedListIterator[V]) Set 

func (i *LinkedListIterator[V]) Set(value V)

type List 

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

List is an implementation of a doubly-linked list.

Removal operations: removed node's pointers remain intact unless the node is re-inserted into a list.

func From 

func From[V any](equal structs.EqualFunc[V], other structs.Collection[V]) *List[V]

From creates a List from an existing collection.

func FromOrdered 

func FromOrdered[V constraints.Ordered](other structs.Collection[V]) *List[V]

FromOrdered creates a List from an existing collection of a type that implements constraints.Ordered.

func New 

func New[V any](equal structs.EqualFunc[V]) *List[V]

New creates an empty List.

func NewOrdered 

func NewOrdered[V constraints.Ordered]() *List[V]

NewOrdered creates an empty List from a type that implements constraints.Ordered.

func Of 

func Of[V any](equal structs.EqualFunc[V], values ...V) *List[V]

Of creates a List from an existing slice.

func OfOrdered 

func OfOrdered[V constraints.Ordered](values ...V) *List[V]

OfOrdered creates a List from an existing slice of a type that implements constraints.Ordered.

func (*List[V]) Add 

func (l *List[V]) Add(value V) bool

Add adds a value to the end of the list.

Time Complexity: O(1)

func (*List[V]) AddAll 

func (l *List[V]) AddAll(other structs.Collection[V]) bool

AddAll adds all the values in the other collection to the end of the list.

Time Complexity: O(n)

func (*List[V]) AddFirst 

func (l *List[V]) AddFirst(value V) bool

AddFirst adds a value to the front of the list.

Time Complexity: O(1)

func (*List[V]) AddFirstNode 

func (l *List[V]) AddFirstNode(node *Node[V])

AddFirstNode adds a node to the front of the list.

Time Complexity: O(1)

func (*List[V]) AddIndex 

func (l *List[V]) AddIndex(index int, value V)

AddIndex adds a value at the specified index in the list.

Time Complexity: O(n)

func (*List[V]) AddIndexNode 

func (l *List[V]) AddIndexNode(index int, node *Node[V])

AddIndexNode adds a node at the specified index in the list.

Time Complexity: O(n)

func (*List[V]) AddIterator 

func (l *List[V]) AddIterator(iter structs.Iterator[V]) bool

AddIterator adds all the values in the iterator to the list.

Time Complexity: O(n)

func (*List[V]) AddLast 

func (l *List[V]) AddLast(value V) bool

AddLast adds a value to the end of the list.

Time Complexity: O(1)

func (*List[V]) AddLastNode 

func (l *List[V]) AddLastNode(node *Node[V])

AddLastNode adds a node to the end of the list.

Time Complexity: O(1)

func (*List[V]) AddNode 

func (l *List[V]) AddNode(node *Node[V])

AddNode adds a node to the end of the list.

Time Complexity: O(1)

func (*List[V]) Clear 

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

Clear clears the list.

Time Complexity: O(1)

func (*List[V]) Clone 

func (l *List[V]) Clone() *List[V]

Clone creates a new list with the same values, starting at the front.

Time Complexity: O(n)

Space Complexity: O(n)

func (*List[V]) CloneBack 

func (l *List[V]) CloneBack() *List[V]

CloneBack creates a new list with the same values, starting at the back.

Time Complexity: O(n)

Space Complexity: O(n)

func (*List[V]) Contains 

func (l *List[V]) Contains(value V) bool

Contains returns whether the value is present the list.

Time Complexity: O(n)

func (*List[V]) ContainsAll 

func (l *List[V]) ContainsAll(other structs.Collection[V]) bool

ContainsAll returns whether all the values in the other collection are present the list.

Time Complexity: O(nm) 

n = size of the current list
m = size of the other collection

func (*List[V]) ContainsIterator 

func (l *List[V]) ContainsIterator(iter structs.Iterator[V]) bool

ContainsIterator returns whether all the values in the iterator are present the list.

Time Complexity: O(nm) 

n = size of the current list
m = number of values in the iterator

func (*List[V]) DescendingIterator 

func (l *List[V]) DescendingIterator() structs.Iterator[V]

DescendingIterator returns a LinkedListDescendingIterator for the list.

func (*List[V]) Each 

func (l *List[V]) Each(f func(value V))

Each calls a function for each value in the list, starting at the front.

func (*List[V]) EachBack 

func (l *List[V]) EachBack(f func(value V))

EachBack calls a function for each value in the list, starting at the end.

func (*List[V]) EachNode 

func (l *List[V]) EachNode(f func(node *Node[V]))

EachNode calls a function for each element in the list, starting at the front.

func (*List[V]) EachNodeBack 

func (l *List[V]) EachNodeBack(f func(node *Node[V]))

EachNodeBack calls a function for each element in the list, starting at the end.

func (*List[V]) FindLastNode 

func (l *List[V]) FindLastNode(value V) *Node[V]

FindLastNode attempts to find and return the last node with the specified value.

Time Complexity: O(n)

func (*List[V]) FindNode 

func (l *List[V]) FindNode(value V) *Node[V]

FindNode attempts to find and return the first node with the specified value.

Time Complexity: O(n)

func (*List[V]) Get 

func (l *List[V]) Get(index int) V

Get returns the value at the specified index.

Time Complexity: O(n)

func (*List[V]) GetFirst 

func (l *List[V]) GetFirst() V

GetFirst returns the value at the front of the list.

Time Complexity: O(1)

func (*List[V]) GetFirstNode 

func (l *List[V]) GetFirstNode() *Node[V]

GetFirstNode returns the node at the front of the list.

Time Complexity: O(1)

func (*List[V]) GetLast 

func (l *List[V]) GetLast() V

GetLast returns the value at the end of the list.

Time Complexity: O(1)

func (*List[V]) GetLastNode 

func (l *List[V]) GetLastNode() *Node[V]

GetLastNode returns the node at the head of the list.

Time Complexity: O(1)

func (*List[V]) GetNode 

func (l *List[V]) GetNode(index int) *Node[V]

GetNode returns the node at the specified index.

Time Complexity: O(n)

func (*List[V]) IndexOf 

func (l *List[V]) IndexOf(value V) int

IndexOf returns the first index of a value in the list, otherwise -1.

Time Complexity: O(n)

func (*List[V]) IndexOfNode 

func (l *List[V]) IndexOfNode(node *Node[V]) int

IndexOfNode returns the index of a node in the list, otherwise -1.

Time Complexity: O(n)

func (*List[V]) InsertAfter 

func (l *List[V]) InsertAfter(before, value V) bool

InsertAfter inserts a node after the first occurrence of an existing value in the list.

Time Complexity: O(n)

func (*List[V]) InsertAfterNode 

func (l *List[V]) InsertAfterNode(target *Node[V], value V) bool

InsertAfterNode inserts a value after an existing node in the list.

Time Complexity: O(1)

func (*List[V]) InsertBefore 

func (l *List[V]) InsertBefore(before, value V) bool

InsertBefore inserts a node before the first occurrence of an existing value in the list.

Time Complexity: O(n)

func (*List[V]) InsertBeforeNode 

func (l *List[V]) InsertBeforeNode(target *Node[V], value V) bool

InsertBeforeNode inserts a value before an existing node in the list.

Time Complexity: O(1)

func (*List[V]) InsertNodeAfterNode 

func (l *List[V]) InsertNodeAfterNode(target *Node[V], node *Node[V]) bool

InsertNodeAfterNode inserts a node after an existing node in the list.

Time Complexity: O(1)

func (*List[V]) InsertNodeBeforeNode 

func (l *List[V]) InsertNodeBeforeNode(target *Node[V], node *Node[V]) bool

InsertNodeBeforeNode inserts a node before an existing node in the list.

Time Complexity: O(1)

func (*List[V]) IsEmpty 

func (l *List[V]) IsEmpty() bool

IsEmpty returns whether this list is empty.

func (*List[V]) Iterator 

func (l *List[V]) Iterator() structs.Iterator[V]

Iterator returns a LinkedListIterator for the list.

func (*List[V]) LastIndexOf 

func (l *List[V]) LastIndexOf(value V) int

LastIndexOf returns the last index of a value in the list, otherwise -1.

Time Complexity: O(n)

func (*List[V]) Offer 

func (l *List[V]) Offer(value V) bool

Offer offers a value to the linked list, adding it to the end of the list.

Time Complexity: O(1)

func (*List[V]) OfferFirst 

func (l *List[V]) OfferFirst(value V) bool

OfferFirst offers a value to the linked list, adding it to the front of the list.

Time Complexity: O(1)

func (*List[V]) OfferLast 

func (l *List[V]) OfferLast(value V) bool

OfferLast offers a value to the linked list, adding it to the end of the list.

Time Complexity: O(1)

func (*List[V]) Peek 

func (l *List[V]) Peek() V

Peek returns the first value in the list, or the zero value of the type if the list is empty.

Time Complexity: O(1)

func (*List[V]) PeekFirst 

func (l *List[V]) PeekFirst() V

PeekFirst returns the first value in the list, or the zero value of the type if the list is empty.

Time Complexity: O(1)

func (*List[V]) PeekLast 

func (l *List[V]) PeekLast() V

PeekLast returns the last value in the list, or the zero value of the type if the list is empty.

Time Complexity: O(1)

func (*List[V]) Poll 

func (l *List[V]) Poll() V

Poll removes and returns the first value in the list, or returns the zero value of the type if the list is empty.

Time Complexity: O(1)

func (*List[V]) PollFirst 

func (l *List[V]) PollFirst() V

PollFirst removes and returns the first value in the list, or returns the zero value of the type if the list is empty.

Time Complexity: O(1)

func (*List[V]) PollLast 

func (l *List[V]) PollLast() V

PollLast removes and returns the last value in the list, or returns the zero value of the type if the list is empty.

Time Complexity: O(1)

func (*List[V]) Pop 

func (l *List[V]) Pop() V

Pop removes and returns the first value in the list.

Time Complexity: O(1)

func (*List[V]) Push 

func (l *List[V]) Push(value V)

Push appends a value to the front of the list.

Time Complexity: O(1)

func (*List[V]) Remove 

func (l *List[V]) Remove(value V) bool

Remove removes a value from the list.

Time Complexity: O(n)

func (*List[V]) RemoveAll 

func (l *List[V]) RemoveAll(other structs.Collection[V]) bool

RemoveAll removes all the values in the other collection from the list.

Time Complexity: O(nm) 

n = size of the current list
m = size of the other collection

func (*List[V]) RemoveFirst 

func (l *List[V]) RemoveFirst() V

RemoveFirst removes and returns the first value in the list.

Time Complexity: O(1)

func (*List[V]) RemoveFirstOccurrence 

func (l *List[V]) RemoveFirstOccurrence(value V) bool

RemoveFirstOccurrence removes the first occurrence of a value from the list.

Time Complexity: O(n)

func (*List[V]) RemoveHead 

func (l *List[V]) RemoveHead() V

RemoveHead removes and returns the first value in the list.

Time Complexity: O(1)

func (*List[V]) RemoveIndex 

func (l *List[V]) RemoveIndex(index int) V

RemoveIndex removes the element at the specified index from the list and returns its value.

Time Complexity: O(n)

func (*List[V]) RemoveIndexNode 

func (l *List[V]) RemoveIndexNode(index int) *Node[V]

RemoveIndexNode removes the node at the specified index from the list and returns it.

Time Complexity: O(n)

func (*List[V]) RemoveIterator 

func (l *List[V]) RemoveIterator(iter structs.Iterator[V]) bool

RemoveIterator removes all the values in the iterator from the list.

Time Complexity: O(nm) 

n = size of the current list
m = number of values in the iterator

func (*List[V]) RemoveLast 

func (l *List[V]) RemoveLast() V

RemoveLast removes and returns the last value in the list.

Time Complexity: O(1)

func (*List[V]) RemoveLastOccurrence 

func (l *List[V]) RemoveLastOccurrence(value V) bool

RemoveLastOccurrence removes the last occurrence of a value from the list.

Time Complexity: O(n)

func (*List[V]) RemoveNode 

func (l *List[V]) RemoveNode(node *Node[V])

RemoveNode removes a node from the list.

Time Complexity: O(1)

func (*List[V]) RetainAll 

func (l *List[V]) RetainAll(other structs.Collection[V]) bool

RetainAll removes all the values not present in the other collection from the list.

Time Complexity: O(nm) 

n = size of the current list
m = time complexity of Contains on the other collection

func (*List[V]) Reverse 

func (l *List[V]) Reverse()

Reverse reverses the list.

Time Complexity: O(n)

func (*List[V]) Set 

func (l *List[V]) Set(index int, value V) V

Set sets the value at the specified index, returning the old value.

Time Complexity: O(n)

func (*List[V]) Size 

func (l *List[V]) Size() int

Size returns the length of the list.

Time Complexity: O(1)

func (*List[V]) Sort 

func (l *List[V]) Sort(cmp structs.LessFunc[V])

Sort sorts the list based on a comparator.

Time Complexity: best case O(nlogn), worst case O(n^2). See slices.SortFunc (algorithm: pattern-defeating quicksort).

func (*List[V]) String 

func (l *List[V]) String() string

String returns a string representation of the list, with brackets and comma separated.

func (*List[V]) Values 

func (l *List[V]) Values() []V

Values return a slice of the values in the list.

Time Complexity: O(n)

Space Complexity: O(n)

type Node 

type Node[V any] struct {
	Value V
	Next  *Node[V]
	Prev  *Node[V]
}

Node is a linked list node.

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.