list

README

Doubly Linked List move function

move src before dst

src\dst	not in list	the only one	the first but not the last	the last but not the first	in middle
not in list	x	x	x	x	x
the only one	x	x	x	x	x
the first but not the last	x	x	x	root.header(src.next) root.tail(src)	root.header(src.next)
the last but not the first	x	x	root.header(src) root.tail(src.prev)	x	root.tail(src.prev)
in middle	x	x	root.header(src)	x	x

move src after dst

src\dst	not in list	the only one	the first but not the last	the last but not the first	in middle
not in list	x	x	x	x	x
the only one	x	x	x	x	x
the first but not the last	x	x	x	root.header(src.next) root.tail(src)	root.header(src.next)
the last but not the first	x	x	root.header(src) root.tail(src.prev)	x	root.tail(src.prev)
in middle	x	x	x	root.tail(src)	x

Documentation

Index

• Constants
• func MaxLevels(totalElements int64, P float64) int
• func SkipListRandomLevel(random func() uint64, maxLevel int) int
• type BasicLinkedList
  • func NewConcurrentSinglyLinkedList[T comparable]() BasicLinkedList[T]
  • func NewSinglyLinkedList[T comparable]() BasicLinkedList[T]
• type LinkedList
  • func NewLinkedList[T comparable]() LinkedList[T]
• type NodeElement
  • func NewConcurrentNodeElement[T comparable](v T) NodeElement[T]
  • func NewNodeElement[T comparable](v T) NodeElement[T]
• type SkipList
  • func NewClassicSkipList[E comparable](compareTo compareTo[E]) SkipList[E]
• type SkipListLevel
• type SkipListNodeElement

Constants

const (
	ClassicSkipListMaxLevel    = 32   // 2^32 - 1 elements
	ClassicSkipListProbability = 0.25 // P = 1/4, a skip list node element has 1/4 probability to have a level
)

Functions

func MaxLevels

func MaxLevels(totalElements int64, P float64) int

func SkipListRandomLevel

func SkipListRandomLevel(random func() uint64, maxLevel int) int

SkipListRandomLevel is the skip list level element. Dynamic level calculation.

Types

type BasicLinkedList

type BasicLinkedList[T comparable] interface {
	Len() int64
	// Append appends the elements to the list l and returns the new elements.
	Append(elements ...NodeElement[T]) []NodeElement[T]
	// AppendValue appends the values to the list l and returns the new elements.
	AppendValue(values ...T) []NodeElement[T]
	// InsertAfter inserts a value v as a new element immediately after element dstE and returns new element.
	// If e is nil, the value v will not be inserted.
	InsertAfter(v T, dstE NodeElement[T]) NodeElement[T]
	// InsertBefore inserts a value v as a new element immediately before element dstE and returns new element.
	// If e is nil, the value v will not be inserted.
	InsertBefore(v T, dstE NodeElement[T]) NodeElement[T]
	// Remove removes targetE from l if targetE is an element of list l and returns targetE or nil if list is empty.
	Remove(targetE NodeElement[T]) NodeElement[T]
	// ForEach traverses the list l and executes function fn for each element.
	ForEach(fn func(idx int64, e NodeElement[T]))
	// FindFirst finds the first element that satisfies the compareFn and returns the element and true if found.
	// If compareFn is not provided, it will use the default compare function that compares the value of element.
	FindFirst(v T, compareFn ...func(e NodeElement[T]) bool) (NodeElement[T], bool)
}

BasicLinkedList is the basic interface for linked list. Serve as the singly linked list.

func NewConcurrentSinglyLinkedList

func NewConcurrentSinglyLinkedList[T comparable]() BasicLinkedList[T]

func NewSinglyLinkedList

func NewSinglyLinkedList[T comparable]() BasicLinkedList[T]

type LinkedList

type LinkedList[T comparable] interface {
	BasicLinkedList[T]
	// ReverseForEach iterates the list in reverse order, calling fn for each element,
	// until either all elements have been visited.
	ReverseForEach(fn func(idx int64, e NodeElement[T]))
	// Front returns the first element of doubly linked list l or nil if the list is empty.
	Front() NodeElement[T]
	// Back returns the last element of doubly linked list l or nil if the list is empty.
	Back() NodeElement[T]
	// PushFront inserts a new element e with value v at the front of list l and returns e.
	PushFront(v T) NodeElement[T]
	// PushBack inserts a new element e with value v at the back of list l and returns e.
	PushBack(v T) NodeElement[T]
	// MoveToFront moves element e to the front of list l.
	MoveToFront(targetE NodeElement[T])
	// MoveToBack moves element e to the back of list l.
	MoveToBack(targetE NodeElement[T])
	// MoveBefore moves element srcE in front of element dstE.
	MoveBefore(srcE, dstE NodeElement[T])
	// MoveAfter moves element srcE next to element dstE.
	MoveAfter(srcE, dstE NodeElement[T])
	// PushFrontList inserts a copy of another linked list at the front of list l.
	PushFrontList(srcList LinkedList[T])
	// PushBackList inserts a copy of another linked list at the back of list l.
	PushBackList(srcList LinkedList[T])
}

LinkedList is the doubly linked list interface.

func NewLinkedList

func NewLinkedList[T comparable]() LinkedList[T]

type NodeElement

type NodeElement[T comparable] interface {
	HasNext() bool
	GetNext() NodeElement[T]
	HasPrev() bool
	GetPrev() NodeElement[T]
	GetValue() T
	SetValue(v T) // Concurrent data race error
}

NodeElement is the basic interface for node element. Alignment of interface is 8 bytes and size of interface is 16 bytes.

func NewConcurrentNodeElement

func NewConcurrentNodeElement[T comparable](v T) NodeElement[T]

func NewNodeElement

func NewNodeElement[T comparable](v T) NodeElement[T]

type SkipList

type SkipList[E comparable] interface {
	GetLevel() int
	Len() int64
	Insert(v E) SkipListNodeElement[E]
	Remove(v E) SkipListNodeElement[E]
	Find(v E) SkipListNodeElement[E]
	PopHead() E
	PopTail() E
	Free()
	ForEach(fn func(idx int64, v E))
}

func NewClassicSkipList

func NewClassicSkipList[E comparable](compareTo compareTo[E]) SkipList[E]

type SkipListLevel

type SkipListLevel[E comparable] interface {
	GetSpan() int64
	SetSpan(span int64)
	GetHorizontalForward() SkipListNodeElement[E]
	SetHorizontalForward(forward SkipListNodeElement[E])
}

type SkipListNodeElement

type SkipListNodeElement[E comparable] interface {
	GetObject() E
	GetVerticalBackward() SkipListNodeElement[E]
	SetVerticalBackward(backward SkipListNodeElement[E])
	GetLevels() []SkipListLevel[E]
	Free()
}