Skip lists

Question 1

Describe skip lists.

Answer 1

Skip lists have some variable MAX_LEVELS. We create a dummy node with this many levels.

For each element we insert, we select a random height between [1,MAX_LEVELS], and connect all the adjacent pointers on the same levels to it.

Question 2

How do search a skip tree?

Answer 2

Start at the dummy node’s highest level. Look at the size of the element pointed to.

• If lower, continue to that node and look at its highest level, then repeat this step.
• If it’s higher, stay at the current node, go down one level and repeat the this step.

At some point, you’ll either:

• reach the lowest level and it’s NULL (Eg. this is the highest element)
• find the element’s position.
• Find the position where the element would go, but realize the element is not there.

Question 3

Describe deletion from a skip list.

Answer 3

1) Find the element.
2) Connect pointers to it to whatever it’s pointing to at that level.
3) Delete the element object.

Question 4

Describe inserting an element into a skip list.

Answer 4

1) Search for where the element would go.
2) Connect the parent elements to it.
3) Connect it to its children elements.