skip list

英語（米国） (en-US) 英語（イギリス） (en-GB)

名詞

(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.

このボタンはなに？

When optimizing the database index, she implemented a skip list to speed up range queries.

詳細

意味（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.

Skip list follows a linked list alike structure. However, the worst case time complexity for a search operation in linked list in O(n) as the list is linearly traversed while searching whereas for a skip list it is O( log n).

詳細

skip lists （ plural ）