skiplist

README

skipList

平均时间复杂度为O(log n).

数据结构

跳表由多层链表组成，每一层都是一个有序链表。底层链表包含所有元素，而上层链表是下层链表的抽样，通常每隔一定数量的元素抽样一个元素到上一层。最顶层的链表可能只有几个元素。

乜咯节点步进保存值，还保存多个纸箱不同层次下一个节点的处在多少层上。每个链表的末尾指向nil。

在最稀疏的层次进行搜索，直至需要查找的元素在该层两个相邻的元素中间。这时，算法将跳转到下一个层次，重复刚才的搜索，直到找到需要查找的元素为止。

查找操作

查找一个元素的步骤如下：

1. 从顶层链表的第一个节点开始。
2. 在当前层向右移动，直到找到一个节点，其值大于或等于要查找的值。
3. 如果找到值相等的节点，则查找成功；否则，向下一层移动，重复步骤 2。
4. 如果到达最底层仍未找到，则查找失败。

Documentation

Index

• type Skiplist
  • func (s *Skiplist) Get(key int) (int, bool)

Types

type Skiplist

type Skiplist struct {
	// contains filtered or unexported fields
}

func (*Skiplist) Get

func (s *Skiplist) Get(key int) (int, bool)