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[0]
        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[1]” (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[3]” of node “6” is pointing to “NIL”, and shouldn’t be redirected to node “25” because “node6._forward[3]” didn’t point to node “17”. The situation is the same for “forward[4]” 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.

Related Posts