Skip lists for probabilistic search in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a skip list?

A skip list is a data structure that allows fast search, insertion, and deletion operations by using multiple layers of linked lists. It uses randomization to decide how many layers each element appears in, making search faster on average.

beginner

How does a skip list improve search speed compared to a simple linked list?

A skip list adds multiple layers of 'express lanes' above the basic linked list. These layers let you skip over many elements at once, reducing the number of steps needed to find an item, similar to how an express train skips many stops.

intermediate

What role does probability play in skip lists?

Probability decides how many layers each element appears in. When inserting, a coin flip or random choice determines if the element is promoted to a higher level. This random layering keeps the structure balanced without complex reorganization.

intermediate

Explain the average time complexity of search in a skip list.

On average, searching in a skip list takes O(log n) time, where n is the number of elements. This is because the multiple layers let you jump ahead quickly, reducing the number of comparisons needed.

intermediate

What is one advantage of skip lists over balanced trees?

Skip lists are simpler to implement and maintain because they use randomization instead of strict balancing rules. This makes them easier to code and often faster in practice for some applications.

What determines the number of layers an element appears in a skip list?

A Random chance or probability

B The element's value

C The size of the list

D The time of insertion

Skip lists use randomization, like coin flips, to decide how many layers an element belongs to.

What is the average search time complexity in a skip list?

A O(n)

B O(log n)

C O(1)

D O(n log n)

Skip lists provide average O(log n) search time due to their layered structure.

Which data structure is most similar in purpose to a skip list?

A Balanced search tree

B Queue

C Stack

D Hash table

Skip lists and balanced trees both support fast search, insertion, and deletion.

Why are skip lists considered easier to implement than balanced trees?

A They do not support deletion

B They require less memory

C They use arrays instead of pointers

D They use randomization instead of strict balancing

Skip lists rely on random layering, avoiding complex balancing rules.

In a skip list, what does a higher level represent?

A More detailed data

B Fewer elements to skip

C Faster access by skipping more elements

D Slower access due to complexity

Higher levels let you skip more elements, speeding up search.

Describe how a skip list uses probability to maintain efficient search performance.

Think about how coin flips decide the layers for each element.

Compare skip lists and balanced trees in terms of implementation and performance.

Focus on how each keeps the data organized for fast search.