14 SKIP LISTS Flashcards
What is a skip list?
A sorted linked list with multiple pointers that allow jumping forward to elements further ahead during operations like search, insertion, or deletion.
Who proposed the concept of skip lists?
William Pugh
What is the main advantage of using skip lists over traditional linked lists?
They mitigate the need to scan through all elements, allowing for more efficient search, insertion, and deletion.
How do skip lists improve search efficiency?
By creating multiple layers of linked lists, allowing searches to start at higher levels with fewer nodes and take larger steps.
What is the structure of a skip list node?
Each node has a key, value, height, and an array of pointers to SkipListNodes.
Define the terms ‘top_level’ and ‘max_level’ in a skip list.
‘top_level’ represents the highest level currently in use; ‘max_level’ represents the highest allowable level.
What role does randomness play in skip lists?
Randomness is used to assign heights to nodes, which helps balance performance in average cases.
True or False: Skip lists are deterministic data structures.
False
What happens if all nodes in a skip list are at the same level?
The skip list devolves into a sorted linked list with additional memory overhead.
How is the height of a new node determined in a skip list?
By flipping a weighted coin and checking against a constant probability p until a number greater than p is obtained or the maximum height is reached.
What does the search process in a skip list involve?
Starting at the top-most level and iterating through nodes, dropping down levels as necessary until the target is found or the end is reached.
Fill in the blank: Skip lists allow for _______ steps across the list to skip unnecessary nodes.
large
What is a key disadvantage of deterministic data structures when faced with worst-case data?
They can become inefficient, such as a binary search tree becoming a sorted linked list if data is inserted in sorted order.
Describe the relationship between node height and the number of nodes at that level in a skip list.
Nodes of level L + 1 are less numerous than nodes at level L, promoting a good average case performance.
What metaphor is used to describe the process of searching in a skip list?
Passing messages between buildings by signaling with flashlights.
What is the termination condition for the search in a skip list?
The search terminates when trying to drop below the bottom level.
What happens during the search if the target key is not found?
The search returns null.
Fill in the blank: Skip lists are _______ data structures.
randomized
What is the expected outcome when using a good randomization strategy in skip lists?
It will often produce a reasonable structure and provide good average case performance.
How do skip lists prevent consistently suboptimal choices?
By introducing randomness into the structural choices of the data.
What analogy is used to describe the traversal in a skip list?
A squirrel navigating along a row of trees.
What is the main purpose of using a probability p in skip lists?
To balance search efficiency with memory usage.
How does William Pugh’s approach determine the height of a node in a skip list?
By flipping a weighted coin until a number greater than p is obtained or the maximum height is reached.
What is the expected number of nodes at level L when using p = 0.5?
Approximately half the nodes at level L are expected to be promoted to level L + 1.
