Documentation ¶
Overview ¶
Skip List implement in Go.
A Skip List is a data structure that allows fast search within an ordered sequence of elements. Fast search is made possible by maintaining a linked hierarchy of subsequences, each skipping over fewer elements.
Example (ManuplateSkiplist) ¶
//New a skiplist sl := NewSkipList(utils.IntComparator) //Insert search key 50, value "5", value could be anything. sl.Insert(50, "5") sl.Insert(40, "4") sl.Insert(70, "7") sl.Insert(100, "10") //Search key, which time complexity O(log n) ret, err := sl.Search(50) if err == nil { fmt.Println("key 50: val->", ret) } else { fmt.Println("Not found, ", err) } //Delete by search key err = sl.Delete(70) if err != nil { fmt.Println("Delete not found") } //Display all skip list content. sl.DisplayAll()
Output:
Index ¶
- Constants
- type Skiplist
- func (b *Skiplist) Delete(searchKey interface{}) error
- func (b *Skiplist) DisplayAll()
- func (b *Skiplist) Insert(searchKey interface{}, value interface{})
- func (b *Skiplist) RandomLevel() int
- func (b *Skiplist) Search(searchKey interface{}) (interface{}, error)
- func (b *Skiplist) SetMaxLevel(maxLevel int)
- type Skipnode
Examples ¶
Constants ¶
View Source
const ( DefaultMaxLevel int = 15 //Maximal level allow to create in this skip list DefaultPropobility float32 = 0.25 //Default propobility )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Skiplist ¶
type Skiplist struct { Header *Skipnode // List configuration MaxLevel int Propobility float32 // List Comparison Comparator utils.Comparator // List status Level int //current level of whole skiplist Random *rand.Rand }
func NewSkipList ¶
func NewSkipList(comparator utils.Comparator) *Skiplist
NewSkipList : Init structure for Skit List.
Example ¶
//New a skiplist sl := NewSkipList(utils.IntComparator) sl.DisplayAll()
Output:
func (*Skiplist) Delete ¶
Delete: Delete element by search key
Example ¶
//New a skiplist sl := NewSkipList(utils.IntComparator) //Insert search key 50, value "5", value could be anything. sl.Insert(70, "7") //Delete by search key err := sl.Delete(70) if err != nil { fmt.Println("Delete not found") }
Output:
func (*Skiplist) DisplayAll ¶
func (b *Skiplist) DisplayAll()
DisplayAll: Display current SkipList content in console, will also print out the linked pointer.
func (*Skiplist) Insert ¶
func (b *Skiplist) Insert(searchKey interface{}, value interface{})
Insert: Insert a search key and its value which could be interface.
Example ¶
//New a skiplist sl := NewSkipList(utils.IntComparator) //Insert search key 50, value "5", value could be anything. sl.Insert(50, "5")
Output:
func (*Skiplist) RandomLevel ¶
func (*Skiplist) Search ¶
Search: Search a element by search key and return the interface{}
Example ¶
//New a skiplist sl := NewSkipList(utils.IntComparator) //Insert search key 50, value "5", value could be anything. sl.Insert(50, "5") sl.Insert(40, "4") sl.Insert(70, "7") sl.Insert(100, "10") //Search key, which time complexity O(log n) ret, err := sl.Search(50) if err == nil { fmt.Println("key 50: val->", ret) } else { fmt.Println("Not found, ", err) }
Output:
func (*Skiplist) SetMaxLevel ¶
Change SkipList default maxlevel is 4.
Click to show internal directories.
Click to hide internal directories.