First inserted value always pushed to rear of sorted skip list c++

Question

#include <iostream>
#include <string>
#include <ctime>
#include <cstdlib>

using namespace std; // TESTING ONLY

class SkipList
{
private:
    struct Node
    {
        Node(int value, int level)
        {
            this->value = value;
            next = new Node*[level];
        }

        Node **next;
        int value;
    };

    Node *head = new Node(0, maxLevel);
    int maxLevel;

    public:

    SkipList()
    {
        maxLevel = 10;
        srand((int)time(nullptr));

        head->next = new Node*[maxLevel];
        for (int i = 0; i < maxLevel; i++)
        {
            head->next[i] = nullptr;
        }
    }

    int promotion()
    {
        int level = 0;
        int _rand = rand() % 2;
        while (_rand)
        {
            level++;
            _rand = rand() % 2;
        }
        return level;
    }

    void Insert(int value)
    {
        int level = promotion();
        Node *newNode = new Node(value, level);

        Node *curr = head;
        for (int i = 9; i >= 0; i--)
        {
            if (curr->next[i] != nullptr)
            {
                while (value > curr->next[i]->value && curr->next[i]->next[i] != nullptr)
                {
                    curr = curr->next[i];
                }
            }
        }

        for (int i = 0; i <= level; i++)
        {
            newNode->next[i] = curr->next[i];
            curr->next[i] = newNode;
        }
    }

    void print() const
    {
        Node *cur = head->next[0];
        cout << "List: NULL --> ";
        while (cur != nullptr)
        {
            cout << cur->value << " --> ";
            cur = cur->next[0];
        }
        cout << "NULL";
        cout << endl;
    }
};


int main()
{
    SkipList skip;

    skip.Insert(3);
    skip.Insert(2);
    skip.Insert(50);
    skip.Insert(39);
    skip.Insert(2000);
    skip.Insert(500);
    skip.print();

    cout << endl << endl;
    system("pause"); // TESTING
    return 0;
}

When I run the above code the first element inserted (in this example 3) is always the last element in the list. Every other elements inserts in the correct order. The above program displays 2-39-50-500-2000-3. I could insert a further 100 values and they would all slot into the correct positions except that first element inserted will always be last, no matter if I place a larger value.

I cannot quite put my finger on it but obviously it's ignoring the last element of the list when placing the insert. Appreciate if someone could shed some light on this. Thanks!

Answer 1

        if (curr->next[i] != nullptr)
        {
            while (value > curr->next[i]->value && curr->next[i]->next[i] != nullptr)
            {
                curr = curr->next[i];
            }
        }

I think there is much more wrong. But the specific bug you asked about is obvious in the above while. It always stops before the last item. I think you should drop the if and change the while to:

        while (curr->next[i] != nullptr && value > curr->next[i]->value )
        {
            curr = curr->next[i];
        }

Notice that in your original code, both the if and the curr->next[i]->next[i] test are defending against curr->next[i]->value seg faulting. You need to stop the curr->next[i]->value test before the last item is reached. But you don't want to stop the curr = curr->next[i]; before the last item could be reached. To do that, I reversed the two sides of your && so I could safely remove one level of indirection from one of them. I hope that explanation was clear enough.