Documentation
¶
Overview ¶
Package lists contains a linked list implementation and common list-like data structures, such as a Queue, a Stack, and a Ring type.
Index ¶
- type Element
- type List
- func (l *List[T]) Back() *Element[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]) 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
- type Queue
- type Ring
- type Stack
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Element ¶
type Element[T any] struct { // The value stored with this element. 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.
This list is a fork of the official Go implementation, with the change of making it generic.
Example ¶
package main
import (
"fmt"
"gopkg.in/typ.v4/lists"
)
func main() {
// Create a new list and put some numbers in it.
l := lists.New[int]()
e4 := l.PushBack(4)
e1 := l.PushFront(1)
l.InsertBefore(3, e4)
l.InsertAfter(2, e1)
// Iterate through list and print its contents.
for e := l.Front(); e != nil; e = e.Next() {
fmt.Println(e.Value)
}
}
Output: 1 2 3 4
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]) 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 ¶
PushBack inserts a new element e with value v at the back 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.
type Queue ¶
type Queue[T any] struct { // contains filtered or unexported fields }
Queue is a first-in-first-out collection.
The implementation is done via a linked-list.
Example ¶
package main
import (
"fmt"
"gopkg.in/typ.v4/lists"
)
func main() {
var q lists.Queue[string]
q.Enqueue("tripp")
q.Enqueue("trapp")
q.Enqueue("trull")
fmt.Println(q.Len()) // 3
fmt.Println(q.Dequeue()) // tripp, true
fmt.Println(q.Dequeue()) // trapp, true
fmt.Println(q.Dequeue()) // trull, true
fmt.Println(q.Dequeue()) // "", false
}
Output: 3 tripp true trapp true trull true false
func (*Queue[T]) Enqueue ¶
func (q *Queue[T]) Enqueue(value T)
Enqueue adds a value to the start of the queue.
type Ring ¶
type Ring[T any] struct { Value T // for use by client; untouched by this library // contains filtered or unexported fields }
A Ring is an element of a circular list, or ring. Rings do not have a beginning or end; a pointer to any ring element serves as reference to the entire ring. Empty rings are represented as nil Ring pointers. The zero value for a Ring is a one-element ring with a nil Value.
This list is a fork of the official Go implementation, with the change of making it generic.
func (*Ring[T]) Do ¶
func (r *Ring[T]) Do(f func(T))
Do calls function f on each element of the ring, in forward order. The behavior of Do is undefined if f changes *r.
Example ¶
package main
import (
"fmt"
"gopkg.in/typ.v4/lists"
)
func main() {
// Create a new ring of size 5
r := lists.NewRing[int](5)
// Get the length of the ring
n := r.Len()
// Initialize the ring with some integer values
for i := 0; i < n; i++ {
r.Value = i
r = r.Next()
}
// Iterate through the ring and print its contents
r.Do(func(p int) {
fmt.Println(p)
})
}
Output: 0 1 2 3 4
func (*Ring[T]) Len ¶
Len computes the number of elements in ring r. It executes in time proportional to the number of elements.
Example ¶
package main
import (
"fmt"
"gopkg.in/typ.v4/lists"
)
func main() {
// Create a new ring of size 4
r := lists.NewRing[int](4)
// Print out its length
fmt.Println(r.Len())
}
Output: 4
func (*Ring[T]) Link ¶
Link connects ring r with ring s such that r.Next() becomes s and returns the original value for r.Next(). r must not be empty.
If r and s point to the same ring, linking them removes the elements between r and s from the ring. The removed elements form a subring and the result is a reference to that subring (if no elements were removed, the result is still the original value for r.Next(), and not nil).
If r and s point to different rings, linking them creates a single ring with the elements of s inserted after r. The result points to the element following the last element of s after insertion.
Example ¶
package main
import (
"fmt"
"gopkg.in/typ.v4/lists"
)
func main() {
// Create two rings, r and s, of size 2
r := lists.NewRing[int](2)
s := lists.NewRing[int](2)
// Get the length of the ring
lr := r.Len()
ls := s.Len()
// Initialize r with 0s
for i := 0; i < lr; i++ {
r.Value = 0
r = r.Next()
}
// Initialize s with 1s
for j := 0; j < ls; j++ {
s.Value = 1
s = s.Next()
}
// Link ring r and ring s
rs := r.Link(s)
// Iterate through the combined ring and print its contents
rs.Do(func(p int) {
fmt.Println(p)
})
}
Output: 0 0 1 1
func (*Ring[T]) Move ¶
Move moves n % r.Len() elements backward (n < 0) or forward (n >= 0) in the ring and returns that ring element. r must not be empty.
Example ¶
package main
import (
"fmt"
"gopkg.in/typ.v4/lists"
)
func main() {
// Create a new ring of size 5
r := lists.NewRing[int](5)
// Get the length of the ring
n := r.Len()
// Initialize the ring with some integer values
for i := 0; i < n; i++ {
r.Value = i
r = r.Next()
}
// Move the pointer forward by three steps
r = r.Move(3)
// Iterate through the ring and print its contents
r.Do(func(p int) {
fmt.Println(p)
})
}
Output: 3 4 0 1 2
func (*Ring[T]) Next ¶
Next returns the next ring element. r must not be empty.
Example ¶
package main
import (
"fmt"
"gopkg.in/typ.v4/lists"
)
func main() {
// Create a new ring of size 5
r := lists.NewRing[int](5)
// Get the length of the ring
n := r.Len()
// Initialize the ring with some integer values
for i := 0; i < n; i++ {
r.Value = i
r = r.Next()
}
// Iterate through the ring and print its contents
for j := 0; j < n; j++ {
fmt.Println(r.Value)
r = r.Next()
}
}
Output: 0 1 2 3 4
func (*Ring[T]) Prev ¶
Prev returns the previous ring element. r must not be empty.
Example ¶
package main
import (
"fmt"
"gopkg.in/typ.v4/lists"
)
func main() {
// Create a new ring of size 5
r := lists.NewRing[int](5)
// Get the length of the ring
n := r.Len()
// Initialize the ring with some integer values
for i := 0; i < n; i++ {
r.Value = i
r = r.Next()
}
// Iterate through the ring backwards and print its contents
for j := 0; j < n; j++ {
r = r.Prev()
fmt.Println(r.Value)
}
}
Output: 4 3 2 1 0
func (*Ring[T]) Unlink ¶
Unlink removes n % r.Len() elements from the ring r, starting at r.Next(). If n % r.Len() == 0, r remains unchanged. The result is the removed subring. r must not be empty.
Example ¶
package main
import (
"fmt"
"gopkg.in/typ.v4/lists"
)
func main() {
// Create a new ring of size 6
r := lists.NewRing[int](6)
// Get the length of the ring
n := r.Len()
// Initialize the ring with some integer values
for i := 0; i < n; i++ {
r.Value = i
r = r.Next()
}
// Unlink three elements from r, starting from r.Next()
r.Unlink(3)
// Iterate through the remaining ring and print its contents
r.Do(func(p int) {
fmt.Println(p)
})
}
Output: 0 4 5
type Stack ¶
type Stack[T any] []T
Stack is a first-in-last-out collection.
Example ¶
package main
import (
"fmt"
"gopkg.in/typ.v4/lists"
)
func main() {
var s lists.Stack[string]
s.Push("tripp")
s.Push("trapp")
s.Push("trull")
fmt.Println(len(s)) // 3
fmt.Println(s.Pop()) // trull, true
fmt.Println(s.Pop()) // trapp, true
fmt.Println(s.Pop()) // tripp, true
fmt.Println(s.Pop()) // "", false
}
Output: 3 trull true trapp true tripp true false
func (*Stack[T]) Peek ¶
Peek returns (but does not remove) the value on top of the stack, or false if the stack is empty.
Source Files