Documentation
¶
Overview ¶
Package list reimplements the double linked list of Go's standard library using generics. It's API compatible with the original list.List and list.Element and it also has some extra quality of life methods (eg: 2 iterators). Using a generic type T instead of the type any avoids unconvinient type casts every time an element from the list is retrieved.
Why? ¶
I needed a linked list for another project and the implementation in Go standard library holds values of type any. This means any time I'm traversing the list I have to type cast each node when retrieved. This was the only way of implementing a list before addition of generics. I find far more convenient if this data structures held values of a generic type instead of type any but I guess this part of the standard library is not relevant enough to receive an update. So, since I needed it I did it myself.
API Compatible ¶
Both List[T] and Element[T] implement the same methods with an almost identical type signature (replacing type any with the generic T). Thus, 99.9% of the Go code that uses container/list types is reusable. The only exception is the list.New() func. It creates and returns a new empty list, with this implementation it's required to declare which type will T adopt.
// Standard library implementation l := list.New() // Own implementation l := list.New[string]()
Since it's impossible to reimplement the list in a way where this function call didn't need to be changed I took the opportunity to add the possibility of initializing a list with some elements. The original New() func takes no args but this implentation takes a variadic number of args of type T:
// Initialize an empty list.
l := list.New[string]()
// Initialize a list with some elements, notice that in this case it's not necessary to specify
// the string type since it's inferred from the args.
l := list.New("A", "B", "C")
Extra methods ¶
Apart from the methods of the standard library version, these other ones were created to add some quality of life improvements:
// Regular iterator:
for i := range list.Iterator() {
fmt.Println(i) // i is of type T
}
// Backwards iterator, useful to traverse a regular list as a FILO data structure:
for i := range list.BackwardsIterator() {
fmt.Println(i) // i is of type T
}
// Get a slice of type T holding a copy af all list elements:
s := list.ToSlice()
// Finally, both List and Element types have a string representation:
listRep := list.String()
elemRep := elem.String()
Index ¶
- type Element
- type List
- func (l *List[T]) Back() *Element[T]
- func (l List[T]) BackwardsIterator() iter.Seq[T]
- func (l *List[T]) Front() *Element[T]
- func (l *List[T]) Init() *List[T]
- func (l *List[T]) InsertAfter(v T, mark *Element[T]) *Element[T]
- func (l *List[T]) InsertBefore(v T, mark *Element[T]) *Element[T]
- func (l List[T]) Iterator() iter.Seq[T]
- func (l *List[T]) Len() int
- func (l *List[T]) MoveAfter(e, mark *Element[T])
- func (l *List[T]) MoveBefore(e, mark *Element[T])
- func (l *List[T]) MoveToBack(e *Element[T])
- func (l *List[T]) MoveToFront(e *Element[T])
- func (l *List[T]) PushBack(v T) *Element[T]
- func (l *List[T]) PushBackList(other *List[T])
- func (l *List[T]) PushFront(v T) *Element[T]
- func (l *List[T]) PushFrontList(other *List[T])
- func (l *List[T]) Remove(e *Element[T]) T
- func (l List[T]) String() string
- func (l List[T]) ToSlice() []T
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Element ¶
type Element[T any] struct { Value T // contains filtered or unexported fields }
Element is an element of a linked list.
type List ¶
type List[T any] struct { // contains filtered or unexported fields }
List represents a doubly linked list. The zero value for List is an empty list ready to use.
func (List[T]) BackwardsIterator ¶
BackwardsIterator returns an iterator that traverses all list elements from last to first that can be used in the for loop.
Example ¶
package main
import (
"fmt"
"github.com/n-mou/yagul/list"
)
func main() {
l := list.New("A", "B", "C", "D")
for i := range l.BackwardsIterator() {
fmt.Println(i)
}
}
Output: D C B A
func (*List[T]) InsertAfter ¶
InsertAfter inserts a new element e with value v immediately after mark and returns e. If mark is not an element of l, the list is not modified. The mark must not be nil.
func (*List[T]) InsertBefore ¶
InsertBefore inserts a new element e with value v immediately before mark and returns e. If mark is not an element of l, the list is not modified. The mark must not be nil.
func (List[T]) Iterator ¶
Iterator returns an iterator that traverses all list elements from first to last that can be used in the for loop.
Example ¶
package main
import (
"fmt"
"github.com/n-mou/yagul/list"
)
func main() {
l := list.New("A", "B", "C", "D")
for i := range l.Iterator() {
fmt.Println(i)
}
}
Output: A B C D
func (*List[T]) MoveAfter ¶
MoveAfter moves element e to its new position after mark. If e or mark is not an element of l, or e == mark, the list is not modified. The element and mark must not be nil.
func (*List[T]) MoveBefore ¶
MoveBefore moves element e to its new position before mark. If e or mark is not an element of l, or e == mark, the list is not modified. The element and mark must not be nil.
func (*List[T]) MoveToBack ¶
MoveToBack moves element e to the back of list l. If e is not an element of l, the list is not modified. The element must not be nil.
func (*List[T]) MoveToFront ¶
MoveToFront moves element e to the front of list l. If e is not an element of l, the list is not modified. The element must not be nil.
func (*List[T]) PushBack ¶
PushFront inserts a new element e with value v at the front of list l and returns e.
func (*List[T]) PushBackList ¶
PushBackList inserts a copy of another list at the back of list l. The lists l and other may be the same. They must not be nil.
func (*List[T]) PushFront ¶
PushFront inserts a new element e with value v at the front of list l and returns e.
func (*List[T]) PushFrontList ¶
PushFrontList inserts a copy of another list at the front of list l. The lists l and other may be the same. They must not be nil.
func (*List[T]) Remove ¶
Remove removes e from l if e is an element of list l. It returns the element value e.Value. The element must not be nil.
Source Files