Question

What is indexed skip list?

(a) it stores width of link in place of element

(b) it stores index values

(c) array based linked list

(d) indexed tree

I want to ask this question from Skip List topic in chapter Types of Lists of Data Structures & Algorithms I

The question was asked during an online interview.

Answer 1

Correct answer is (a) it stores width of link in place of element

The best explanation: The width is defined as number of bottom layer links that are being traversed by each of higher layer elements. e.g: for a level-2 skip lists, all level-1 nodes have 1 as width, for level-2 width will be 2.