Skip to content

Implementation of a skiplist data structure that is thread-safe for searching and insertion.

Notifications You must be signed in to change notification settings

eval-exec/skiplist

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

3 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

skiplist

Skip lists were first described in 1989 by William Pugh.

It is a probabilistic data structure that allows O(log n) search complexity as well as O(log n) insertion complexity within an ordered sequence of n elements.

Skip lists are a probabilistic data structure that seem likely to supplant balanced trees as the implementation method of choice for many applications. Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.

— William Pugh, Concurrent Maintenance of Skip Lists (1989)

References

  • https://en.wikipedia.org/wiki/Skip_list
  • Papadakis, Thomas (1993). Skip Lists and Probabilistic Analysis of Algorithms. University of Waterloo.
  • William Pugh. "A skip list cookbook". 1990. Section 3.4 Linear List Operations .
  • Pugh, William (April 1989). Concurrent Maintenance of Skip Lists (PS, PDF) (Technical report). Dept. of Computer Science, U. Maryland. CS-TR-2222.

About

Implementation of a skiplist data structure that is thread-safe for searching and insertion.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages