Building the Skip List: Node, Insert & the Coin Flip

Time to turn the diagram from the last lesson into real C++. A skip list node is a value plus an array of forward pointers, one per level that node was promoted to.

struct SkipNode {
    int horseId;
    float key;                          // the value the list is sorted by
    std::vector<SkipNode*> forward;      // forward[i] = next node at level i

    SkipNode(int id, float k, int level) : horseId(id), key(k), forward(level, nullptr) {}
};

A node promoted to level 3 has forward.size() == 3, three separate "next" pointers, one per lane it participates in. A node that only exists at level 0 (the common case) has just one.

The skip list itself

const int MAX_LEVEL = 16;

class SkipList {
public:
    SkipList() : head(new SkipNode(-1, 0.f, MAX_LEVEL)), currentLevel(1) {}

    int randomLevel() {
        int level = 1;
        while (((float) rand() / RAND_MAX) < 0.5f && level < MAX_LEVEL) {
            level++;
        }
        return level;
    }

private:
    SkipNode* head;      // sentinel: never holds real data, only points into the list
    int currentLevel;    // how many levels are actually in use right now
};

head is a sentinel node, allocated once at MAX_LEVEL so it always has enough forward pointers, but its own horseId/key are never read, it exists purely as a fixed starting point every search and insert begins from. currentLevel tracks how many levels are actually in use, there's no reason to search levels 5 through 16 if nothing has ever been promoted that high yet.

Insert: find the spot at every level, then splice in

void insert(int horseId, float key) {
    std::vector<SkipNode*> update(MAX_LEVEL, head); // update[i] = the node to splice after, at level i
    SkipNode* current = head;

    for (int level = currentLevel - 1; level >= 0; level--) {
        while (current->forward[level] != nullptr && current->forward[level]->key > key) {
            current = current->forward[level];
        }
        update[level] = current; // the last node before key at this level
    }

    int newLevel = randomLevel();
    if (newLevel > currentLevel) {
        for (int level = currentLevel; level < newLevel; level++) {
            update[level] = head; // new top levels start empty, so head is the predecessor
        }
        currentLevel = newLevel;
    }

    SkipNode* newNode = new SkipNode(horseId, key, newLevel);
    for (int level = 0; level < newLevel; level++) {
        newNode->forward[level] = update[level]->forward[level];
        update[level]->forward[level] = newNode;
    }
}

Note the comparison: this list is sorted descending by key, the horse in the lead (highest distance) belongs at the front. current->forward[level]->key > key keeps moving forward while the next node is still ahead of the value being inserted.

The update array is the key idea: while walking down from the top level to find the insertion point, record the last node visited at every level, that's exactly the set of nodes whose forward pointers need to change once the new node exists. Once newLevel is decided, splicing in is just: for each level from 0 up to newLevel, point the new node at whatever update[level] used to point to, then point update[level] at the new node, the standard "insert into a linked list" pattern, just repeated once per level.