dll

README

= A generics based Go Singly Linked List

A simple doubly linked list (DLL)  with IsEmpty, AppendSLL, HeadSLL, Length

Documentation

Index

• Variables
• type ApplyFunction
• type Dll
  • func NewDll[T comparable.Equality]() *Dll[T]
  • func (ns *Dll[T]) AppendAtTail(t *T) bool
  • func (ns *Dll[T]) Current(el *DllElement[T], pos int) *DllIter[T]
  • func (ns *Dll[T]) Delete(t *T) (err error)
  • func (ns *Dll[T]) DeleteAtHead() (err error)
  • func (ns *Dll[T]) DeleteAtTail() (err error)
  • func (ns *Dll[T]) DeleteFound(it *DllElement[T]) (err error)
  • func (tt *Dll[T]) Dump(fo io.Writer)
  • func (ns *Dll[T]) Enque(t *T)
  • func (ns *Dll[T]) Front() *DllIter[T]
  • func (ns *Dll[T]) Index(sub int) (rv *DllElement[T], err error)
  • func (ns *Dll[T]) InsertBeforeHead(t *T) bool
  • func (ns *Dll[T]) IsEmpty() bool
  • func (ns *Dll[T]) IterateOver() iter.Seq2[int, T]
  • func (ns *Dll[T]) IteratePtr() iter.Seq2[int, *T]
  • func (ns *Dll[T]) Length() int
  • func (ns *Dll[T]) Peek() (rv *T, err error)
  • func (ns *Dll[T]) PeekTail() (rv *T, err error)
  • func (ns *Dll[T]) Pop() (rv *T, err error)
  • func (ns *Dll[T]) PopTail() (rv *T, err error)
  • func (ns *Dll[T]) Push(t *T)
  • func (ns *Dll[T]) Rear() *DllIter[T]
  • func (ns *Dll[T]) Reverse()
  • func (ns *Dll[T]) ReverseList()
  • func (ns *Dll[T]) ReverseSearch(t *T) (rv *DllElement[T], pos int)
  • func (ns *Dll[T]) ReverseWalk(fx ApplyFunction[T], userData interface{}) (rv *DllElement[T], pos int)
  • func (ns *Dll[T]) Search(t *T) (rv *DllElement[T], pos int)
  • func (ns *Dll[T]) Truncate()
  • func (ns *Dll[T]) Walk(fx ApplyFunction[T], userData interface{}) (rv *DllElement[T], pos int)
• type DllElement
  • func (ee *DllElement[T]) GetData() *T
  • func (ee *DllElement[T]) SetData(d *T)
• type DllIter
  • func (iter *DllIter[T]) Done() bool
  • func (iter *DllIter[T]) Next()
  • func (iter *DllIter[T]) Pos() int
  • func (iter *DllIter[T]) Prev()
  • func (iter *DllIter[T]) Value() *T
• type DllSeq

Variables

var ErrEmptyDll = errors.New("Empty Dll")

An error to indicate that the DLL is empty

var ErrInteralDll = errors.New("Interal Dll")

var ErrOutOfRange = errors.New("Subscript Out of Range")

Types

type ApplyFunction

type ApplyFunction[T comparable.Equality] func(pos int, data T, userData interface{}) bool

type Dll

type Dll[T comparable.Equality] struct {
	// contains filtered or unexported fields
}

Dll is a generic type buildt on top of a slice

func NewDll

func NewDll[T comparable.Equality]() *Dll[T]

Create a new DLL and return it. Complexity is O(1).

func (*Dll[T]) AppendAtTail

func (ns *Dll[T]) AppendAtTail(t *T) bool

Push will append a new node to the end of the list.

func (*Dll[T]) Current

func (ns *Dll[T]) Current(el *DllElement[T], pos int) *DllIter[T]

Current will take the node returned from Search or RevrseSearch

func (ns *Dll[T]) Search( t *T ) (rv *DllElement[T], pos int) {

and allow you to start an iteration process from that point.

func (*Dll[T]) Delete

func (ns *Dll[T]) Delete(t *T) (err error)

Delete a matching element

func (*Dll[T]) DeleteAtHead

func (ns *Dll[T]) DeleteAtHead() (err error)

func (*Dll[T]) DeleteAtTail

func (ns *Dll[T]) DeleteAtTail() (err error)

func (*Dll[T]) DeleteFound

func (ns *Dll[T]) DeleteFound(it *DllElement[T]) (err error)

Delete removes a 'found' element from the DLL, the next/prev pointers must be in this list.

func (*Dll[T]) Dump

func (tt *Dll[T]) Dump(fo io.Writer)

func (*Dll[T]) Enque

func (ns *Dll[T]) Enque(t *T)

func (*Dll[T]) Front

func (ns *Dll[T]) Front() *DllIter[T]

Front will start at the beginning of a list for iteration over list.

func (*Dll[T]) Index

func (ns *Dll[T]) Index(sub int) (rv *DllElement[T], err error)

Index will return the Nth item from the list.

func (*Dll[T]) InsertBeforeHead

func (ns *Dll[T]) InsertBeforeHead(t *T) bool

Push will append a new node to the end of the list.

func (*Dll[T]) IsEmpty

func (ns *Dll[T]) IsEmpty() bool

IsEmpty will return true if the DLL (queue or stack) is empty

func (*Dll[T]) IterateOver

func (ns *Dll[T]) IterateOver() iter.Seq2[int, T]

func (*Dll[T]) IteratePtr

func (ns *Dll[T]) IteratePtr() iter.Seq2[int, *T]

func (*Dll[T]) Length

func (ns *Dll[T]) Length() int

Length returns the number of elements in the list.

func (*Dll[T]) Peek

func (ns *Dll[T]) Peek() (rv *T, err error)

Peek returns the top element of the DLL (like a Stack) or an error indicating that the stack is empty.

func (*Dll[T]) PeekTail

func (ns *Dll[T]) PeekTail() (rv *T, err error)

Peek returns the last element of the DLL (like a Queue) or an error indicating that the stack is empty.

func (*Dll[T]) Pop

func (ns *Dll[T]) Pop() (rv *T, err error)

Pop will remove the top element from the DLL. An error is returned if the stack is empty.

func (*Dll[T]) PopTail

func (ns *Dll[T]) PopTail() (rv *T, err error)

PopTail will remove the top element from the DLL. An error is returned if the stack is empty.

func (*Dll[T]) Push

func (ns *Dll[T]) Push(t *T)

func (*Dll[T]) Rear

func (ns *Dll[T]) Rear() *DllIter[T]

Rear will start at the end of a list for iteration over list.

func (*Dll[T]) Reverse

func (ns *Dll[T]) Reverse()

Reverse - effeciently reverse direciotn on a list. O(n) with storage O(1)

func (*Dll[T]) ReverseList

func (ns *Dll[T]) ReverseList()

ReverseList - Reverse all the nodes in list. O(n)

func (*Dll[T]) ReverseSearch

func (ns *Dll[T]) ReverseSearch(t *T) (rv *DllElement[T], pos int)

ReverseSearch — Returns the given element from a linked list searching from tail to head. O(n)

func (*Dll[T]) ReverseWalk

func (ns *Dll[T]) ReverseWalk(fx ApplyFunction[T], userData interface{}) (rv *DllElement[T], pos int)

ReverseWalk - Iterate from tail to head of list. O(n)

func (*Dll[T]) Search

func (ns *Dll[T]) Search(t *T) (rv *DllElement[T], pos int)

Walk - Iterate from head to tail of list. O(n) Search — Returns the given element from a linked list. Search is from head to tail. O(n) If the item is not found then a position of -1 is returned.

func (*Dll[T]) Truncate

func (ns *Dll[T]) Truncate()

Truncate removes all data from the list.

func (*Dll[T]) Walk

func (ns *Dll[T]) Walk(fx ApplyFunction[T], userData interface{}) (rv *DllElement[T], pos int)

Walk - Iterate from head to tail of list. O(n)

type DllElement

type DllElement[T comparable.Equality] struct {
	Data *T
	// contains filtered or unexported fields
}

An element in the doubly linked list.

func (*DllElement[T]) GetData

func (ee *DllElement[T]) GetData() *T

Complexity is O(1).

func (*DllElement[T]) SetData

func (ee *DllElement[T]) SetData(d *T)

Complexity is O(1).

type DllIter

type DllIter[T comparable.Equality] struct {
	// contains filtered or unexported fields
}

An iteration type that allows a for loop to walk the list.

func (*DllIter[T]) Done

func (iter *DllIter[T]) Done() bool

Done returns true if the end of the list has been reached.

func (*DllIter[T]) Next

func (iter *DllIter[T]) Next()

Next advances to the next element in the list.

func (*DllIter[T]) Pos

func (iter *DllIter[T]) Pos() int

Pos returns the current "index" of the elemnt being iterated on. So if the list has 3 elements, a, b, c and we start at the head of the list 'a' will have a Pos() of 0, 'b' will have a Pos() of 1 etc.

func (*DllIter[T]) Prev

func (iter *DllIter[T]) Prev()

Prev moves back to the previous element in the list.

func (*DllIter[T]) Value

func (iter *DllIter[T]) Value() *T

Value returns the current data for this element in the list.

type DllSeq

type DllSeq[V comparable.Equality] func(yield func(V) bool)