skip list

From Wiktionary, the free dictionary
Jump to navigation Jump to search

English

[edit]
English Wikipedia has an article on:
Wikipedia

Noun

[edit]

skip list (plural skip lists)

  1. (computing theory) A probabilistic data structure that allows fast search within an ordered sequence of elements by maintaining a linked hierarchy of subsequences, with each successive subsequence skipping over fewer elements than the previous one.
    • 2021, Neeraj Kumar, Arzoo Miglani, Probabilistic Data Structures for Blockchain-Based Internet of Things Applications, CRC Press, →ISBN, page 187:
      Skip list follows a linked list alike structure. However, the worst case time complexity for a search operation in linked list in as the list is linearly traversed while searching whereas for a skip list it is .