After reading the classic paper about Skip-list, I tried to implement it by myself. But then I found a line of pseudo-code in the “Delete” function that I couldn’t understand:
Seems all the elements in “update” will point to “x”, so why do we need to check here? Maybe I can ignore this checking. Now here comes a part of my code:
def erase(self, num: int) -> bool: update = Node(-1) curr = self._head for level in range(MAX_LEVEL-1, -1, -1): while curr._forward[level] and curr._forward[level]._key < num: curr = curr._forward[level] update._forward[level] = curr curr = curr._forward if curr == None or curr._key != num: return False curr._count -= 1 if curr._count > 0: return True for level in range(MAX_LEVEL): update._forward[level]._forward[level] = curr._forward[level] del curr return True
But unfortunately, it failed for the test case. In the debugging process, I realized that not all elements in “update” will point to “x”. Le’ts just take the figure-1 from the paper as my example:
As above, imaging we are deleting node “17”. The “forward” (index start from 0, this is the difference of my code with the paper) of node “9” is pointing to node “17” so it should be redirect to node “25”. But the “forward” of node “6” is pointing to “NIL”, and shouldn’t be redirected to node “25” because “node6._forward” didn’t point to node “17”. The situation is the same for “forward” and beyond, of node “6”.
This is why the last few lines of my code should be:
...... for level in range(MAX_LEVEL): if update._forward[level]._forward[level] != curr: break update._forward[level]._forward[level] = curr._forward[level] del curr return True
Just like the pseudo-code in the paper!
I am really respect to these academic guys — everytime I thought they were wrong is actually I missed something.