README
¶
Skip List
Description
This package implements a skip list, a probabilistic data structure often used as an alternative to balanced trees, like AVL or red-black. Skip lists have an average-case time complexity of O(log N) and worst-case of O(N) for searching for, inserting, and deleting elements, where N is the number of elements in the list.
Documentation
¶
Index ¶
- Constants
- type Iterator
- type Pair
- type SkipList
- func (sl *SkipList[K, V]) Clear()
- func (sl *SkipList[K, V]) Delete(key K) (V, bool)
- func (sl *SkipList[K, V]) DeleteAll(keys ...K)
- func (sl *SkipList[K, V]) First() *Pair[K, V]
- func (sl *SkipList[K, V]) Get(key K) (V, bool)
- func (sl *SkipList[K, V]) IsEmpty() bool
- func (sl *SkipList[K, V]) Iterator() Iterator[K, V]
- func (sl *SkipList[K, V]) IteratorFrom(start K) Iterator[K, V]
- func (sl *SkipList[K, V]) IteratorFromEnd() Iterator[K, V]
- func (sl *SkipList[K, V]) Last() *Pair[K, V]
- func (sl *SkipList[K, V]) Len() int
- func (sl *SkipList[K, V]) MaxLevel() int
- func (sl *SkipList[K, V]) Range(start, end K) Iterator[K, V]
- func (sl *SkipList[K, V]) Set(key K, val V) (bool, V)
- func (sl *SkipList[K, V]) SetAll(items []Pair[K, V])
- func (sl *SkipList[K, V]) SetMaxLevel(newMaxLevel int)
- func (sl *SkipList[K, V]) String() string
Constants ¶
const AbsoluteMaxLevel = 64
const DefaultMaxLevel = 32
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Iterator ¶
type Iterator[K, V any] interface { // Next returns true if there are further nodes over which to iterate and // advances the iterator if there are Next() bool // Prev returns true if there are previous elements over which to iterate // and rewinds to the previous node if possible Prev() bool // Key returns the current key Key() K // Value returns the current value Value() V }
Iterator is a bidirectional iterator over the skip list.
type Pair ¶ added in v0.1.4
type Pair[K, V any] struct { // contains filtered or unexported fields }
Pair is a key-value pair, or element, in the skip list.
func (Pair[K, V]) Key ¶ added in v0.1.4
func (p Pair[K, V]) Key() K
Key returns the key of this key-value pair.
type SkipList ¶
type SkipList[K, V any] struct { // contains filtered or unexported fields }
func Merge ¶
Merge returns a new skip list with the elements from both lists. For any keys that are in both of the lists, the result will use the value from the second list. The maxLevel of the result will be the greater maxLevel of the inputs.
func NewCustomSkipList ¶
NewCustomSkipList initializes a skip list using a custom key type, which means there must be a function that defines a linear ordering of keys, i.e. for two keys X & Y the function must define how X is less than Y. Optionally include items with which to initialize the list. Uses default max level of 32.
func NewSkipList ¶
NewSkipList initializes a skip list using a cmp.Ordered key type and with a default max level of 32. Optionally include items with which to initialize the list.
func (*SkipList[K, V]) Clear ¶
func (sl *SkipList[K, V]) Clear()
Clear resets the state of the skip list, removing all elements from the skip list.
func (*SkipList[K, V]) Delete ¶
Delete removes the element with given key from the skip list. Returns the deleted value if it existed and a bool indicating if it did. Time complexity: O(logN), where N is the number of elements in the skip list.
func (*SkipList[K, V]) DeleteAll ¶
func (sl *SkipList[K, V]) DeleteAll(keys ...K)
DeleteAll elements with the given keys. Time complexity: O(MlogN), where M is the number of keys, and N is the number of elements of the skip list.
func (*SkipList[K, V]) First ¶ added in v0.1.3
First returns the first element, or the element with the minimum key, of the skip list, or nil if the list is empty. Time complexity: O(1).
func (*SkipList[K, V]) Get ¶
Get returns the value associated with the key if the key exists and a bool indicating if it does. Time complexity: O(logN), where N is the number of elements in the skip list.
func (*SkipList[K, V]) Iterator ¶
Iterator returns a bidirectional iterator starting from the first node of the skip list, or nil if the list is empty.
func (*SkipList[K, V]) IteratorFrom ¶
IteratorFrom returns a bidirectional iterator starting from the first node with key equal to or greater than start, or nil if the list is empty.
func (*SkipList[K, V]) IteratorFromEnd ¶
IteratorFromEnd returns a bidirectional iterator starting from the last node of the skip list, or nil if the list is empty.
func (*SkipList[K, V]) Last ¶ added in v0.1.3
Last returns the last element, or the element with the maximum key, of the skip list, or nil if the list is empty. Time complexity: O(1).
func (*SkipList[K, V]) MaxLevel ¶
MaxLevel returns the maximum number of levels any node in the skip list can be on.
func (*SkipList[K, V]) Range ¶
Range returns a bidirectional iterator beginning at the first node with key greater than or equal to start (inclusive) to the node with key end (exclusive), or nil if the list is empty.
func (*SkipList[K, V]) Set ¶
Set sets a key to a value in the skip list. Returns true if this is pair was newly inserted. If this updated an existing key, returns the old value and false. Time complexity: O(logN), where N is the number of elements in the skip list.
func (*SkipList[K, V]) SetAll ¶
SetAll inserts each key-value pair in an array of pairs into the skip list.
func (*SkipList[K, V]) SetMaxLevel ¶
SetMaxLevel sets the max level of the skip list, up to 64. Inputs greater than 64 are clamped to 64. If the new max level is less than the level of the highest node in the list, the new max level will instead be that node's level.
Source Files