Algorithm: Insertion in skip list

Question

How does the algorithm for insertion in skip list look like?

Normally something like this would pop up when searching on google, but oddly enough I can't seem to find anything helpful in my book or on the internet.

The only thing I can find are explanations of how skip lists work.

Answer 1

Firstly, we need to find a position for the new element (I'll call it a key).

We do it this way:

1. Let's start from the highest level and see where the link leads us. If it leads to the end of the list or to the number that is greater than the key, we need to go one level down. Otherwise, we follow this link and repeat the procedure for the node this link leads us to.

2. The level is decreased every time we cannot make a jump and the position in the list increases every time we can, so after a finite number of steps we will reach the level zero and a link that leads from a number that is less than a key to the number that is greater than the key. It's exactly where the key should be inserted.

Now its time to insert it.

1. Let's randomly generate the "height" of the new node.

2. When we traverse the list during the search, we can keep an array that stores the rightmost link for every given height.

3. For each level from 0 to "height", we create a link from this node to the node which the rightmost link points to and redirect the rightmost link to a newly created node.

I did not mention what to do with equal elements. We can either insert the key anyway (if we want to store duplicates), or just ignore it.

Here is a pseudocode of the insert function:

class Node {
    // an array of links for levels from 0 to the height of this node
    Node[] next; 
    int key; 

    Node(int height, int key) {
        key = key;
        next = new Node[height + 1];
    }
}

// I assume that the list always has two nodes: head and tail, which do not
// hold any values

void insert(int newKey) {
    // The rightmost node for each level such that the node itself has a key 
    // less than newKey but the node which the link points to has a larger key. 
    rightMostForLevel = new Node[maxLevel + 1]
    fill(leftMostForLevel, head)
    curLevel = maxLevel
    curNode = head
    // We need to find a node with the largest key such that its key is less
    // than or equal to the newKey, but the next node in the list is either 
    // equal to the tail or a has a greater key. 
    // We are done when the level is equal to zero and the next node has 
    // a key greater than newKey.
    while (curLevel != 0 
            or (curNode.next[curLevel] != tail and curNode.next[curLevel] <= key)) {
        if (curNode.next[curLevel] == tail or curNode.next[curLevel].key > key) {
            // We cannot make the jump (its too "long")
            // So we go one level lower
            curLevel--
        } else {
            // Otherwise, we make the jump
            curNode = curNode.next[curLevel]
            // And update the rightmost node for the current level
            rightMostForLevel[curLevel] = curNode
        }
    }  
    // Now we know where the new node should be inserted 
    newHeight = random height
    newNode = new Node(newHeight, newKey)
    // All we need to do is to update the links
    for (level = 0; level <= newHeight; level++) {
        // We "cut" the links that go through the new node
        newNode.next[level] = rightMostForLevel[level].next[level] 
        rightMostForLevel[level].next[level] = newNode  
    }
}