Editing Skip list (section)

{{Short description|Probabilistic data structure}}
{{Infobox data structure
| name = Skip list
| type = List
| invented_by = [[William Pugh (computer scientist)|W. Pugh]]
| invented_year = 1989
| space_avg = <math>\theta(n)</math>
| space_worst = <math>O(n\log n)</math><ref name="cs.uwaterloo">{{cite thesis |title=Skip Lists and Probabilistic Analysis of Algorithms |first=Thomas |last=Papadakis |type=Ph.D. |year=1993 |publisher=University of Waterloo |url=http://www.cs.uwaterloo.ca/research/tr/1993/28/root2side.pdf}}</ref>
| search_avg = <math>\theta(\log n)</math>
| search_worst = <math>O(n)</math><ref name="cs.uwaterloo" />
| insert_avg = <math>\theta(\log n)</math>
| insert_worst = <math>O(n)</math>
| delete_avg = <math>\theta(\log n)</math>
| delete_worst = <math>O(n)</math>
}}
{{Probabilistic}}
In [[computer science]], a '''skip list''' (or '''skiplist''') is a [[Randomized algorithm|probabilistic]] [[data structure]] that allows <math>O(\log n)</math> [[Average-case complexity|average complexity]] for search as well as <math>O(\log n)</math> average complexity for insertion within an [[ordered sequence]] of <math>n</math> elements. Thus it can get the best features of a sorted [[Array data structure|array]] (for searching) while maintaining a [[linked list]]-like structure that allows insertion, which is not possible with a static array. Fast search is made possible by maintaining a linked hierarchy of subsequences, with each successive subsequence skipping over fewer elements than the previous one (see the picture below on the right). Searching starts in the sparsest subsequence until two consecutive elements have been found, one smaller and one larger than or equal to the element searched for. Via the linked hierarchy, these two elements link to elements of the next sparsest subsequence, where searching is continued until finally searching in the full sequence. The elements that are skipped over may be chosen probabilistically<ref name="pugh">{{Cite journal | doi = 10.1145/78973.78977| title = Skip lists: A probabilistic alternative to balanced trees| journal = [[Communications of the ACM]]| volume = 33| issue = 6| pages = 668–676| year = 1990| last1 = Pugh | first1 = W. | s2cid = 207691558| author-link1 = William Pugh (computer scientist) | url = https://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf}}</ref> or deterministically,<ref>{{cite conference |url=https://www.ic.unicamp.br/~celio/peer2peer/skip-net-graph/deterministic-skip-lists-munro.pdf |title=Deterministic skip lists |last1=Munro |first1=J. Ian |author-link1=Ian Munro (computer scientist) |last2=Papadakis |first2=Thomas |last3=Sedgewick |first3=Robert |author-link3=Robert Sedgewick (computer scientist) |date=1992 |publisher=Society for Industrial and Applied Mathematics, Philadelphia, PA, USA |book-title=Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms (SODA '92) |pages=367–375 |location=Orlando, Florida, USA |s2cid=7477119}}</ref> with the former being more common.