Search code examples
data-structureslinked-listskip-lists

Skip List: Insertions

I'm trying to understand how a skip list works for insertion, but when I draw it out, it doesn't work out.

|-inf<---------------------------->+inf|0
|-inf<--------->4<---------------->+inf|1
|-inf<--------->4<--->9<--->11<--->+inf|2
|-inf<--->1<--->4<--->9<--->11<--->+inf|3

So I want to insert 5 on the above linked list.

Start on row 0: Start at -inf, compare 5 to +inf, move to next row.

Move to row 1:

Is 5 <= 4, no. Compare to what's on the right, +inf. Move down from the element 4 to row 2.

Move to row 2:

Now we're traversing between 4 and 9, so the comparison would be something like is 5 <= 4? No. Is 5 <= 9? Yes. Insert between 4 and 9.

But now 5 doesn't show up on row 3? What am I doing wrong?

Solution

  • When you see that 5 <= 9, you have to keep going down until you reach the bottom. There could be any number between 4 and 9 still in one of the lower levels. When you determine its location in the bottom row, you insert it there, and then start inserting it one row higher depending on the outcome of an RNG. The full sequence for your insertion is then something like:

    1. 5 > +inf? No: move down.
    2. 5 > 4? Yes: move to right.
    3. 5 > +inf? No: move down.
    4. 5 > 9? No: move down.
    5. 5 > 9? No: move down.
    6. Couldn't move down in previous step, so insert between 4 and 9 at bottom level.
    7. Probabilistically add 5 to higher rows.