Describe a skip list and how it relates to linked lists.

• A. A skip list uses multiple forward pointers at several levels to achieve probabilistic O(log n) search/insert/delete.
• B. A skip list is a dense binary tree structure.
• C. A skip list stores keys only as in a hash table.
• D. A skip list is a linked list with fixed single level pointers.

Answer: (A)

Skip lists extend a simple linked list by adding multiple forward pointers at several levels. Each element gets a random height, so some nodes participate in higher levels that skip over many elements. The bottom level is a regular ordered linked list containing all elements, while the higher levels provide shortcuts for faster traversal. To search, you start at the top level and move forward while the next value is still in range, dropping down a level when you can’t advance, and continue until you reach the bottom level. This approach yields expected O(log n) time for search, insert, and delete because you skip large portions of the list with the higher levels. The relationship to linked lists is direct: the bottom level behaves like a standard linked list, and the higher levels are additional forward pointers that enable skipping. It’s not a dense binary tree, not a hash table, and it doesn’t have a fixed single level of pointers.