Deleting a node from a skip list

Question

I'm having some problems deleting a node from a skip list. I have the following structures:

struct Node
{
    int info;
    Node **link_;

    Node(int v, int levels)
    {
        info = v;
        link_ = new Node*[levels];

        for ( int i = 0; i < levels; ++i )
            link_[i] = NULL;
    }
};

struct List
{
    int H; // list height

    Node *Header;

    List()
    {
        Header = new Node(0, maxH);
        H = 1;
    }
};

The problem, I think, is in the function that searches for a node with a given value and then deletes it. The function is implemented like this:

void Remove(int v, List *L)
{
    Node *current = L->Header;

    for ( int i = L->H - 1; i >= 0; --i )
    {
        for ( ; current->link_[i] != NULL; current = current->link_[i] )
            if ( current->link_[i]->info > v )
                break;
            else if ( current->link_[i]->info == v )
            {
                // Node *del = current->link_[i];
                current->link_[i] = current->link_[i]->link_[i];

                // delete del;
                break;
            }
    }
}

The function works fine as it is, however the list seems to break if I uncomment the two commented lines. By break I mean that the following test code never finishes:

int main()
{
    srand((unsigned)time(0));

    List *SKL = new List();


    for ( int i = 0; i < 1000000; ++i )
        Insert(rand() * rand(), SKL);

    for ( int i = 0; i < 1000000; ++i )
        Search(rand() * rand(), SKL);

    for ( int i = 0; i < 1000000; ++i )
        Remove(rand() * rand(), SKL);

    for ( int i = 0; i < 1000000; ++i )
        Insert(rand() * rand(), SKL);


    return 0;
}

The problem lies in the last for loop that inserts more values in the list. If those two lines are commented out, the program finishes in about 10 seconds. If I uncomment them, it seems to enter an infinite loop as it doesn't even finish in minutes. I'm not sure if that's the right way of deleting a node from a skip list or not, so I'm posting my insertion function as well:

void Insert(int v, List *L)
{
    // this section just determines the levels the new node will be part of
    int newH = 0;

    int tmp;
    unsigned int rnd = rand() * rand(); 
    do
    {
        tmp = lookup[rnd & 255];
        rnd >>= 8;
        newH += tmp;
    } while ( tmp == 8 );

    if ( newH >= L->H )
        ++L->H;

    // this does the actual insertion
    Node *newNode = new Node(v, L->H);
    Node *current = L->Header;
    for ( int i = L->H - 1; i >= 0; --i )
    {
        for ( ; current->link_[i] != NULL; current = current->link_[i] )
            if ( current->link_[i]->info >= v )
                break;

        if ( i <= newH )
        {
            newNode->link_[i] = current->link_[i];
            current->link_[i] = newNode;
        }
    }
}

So, my questions are:

1. Why does the program break, and how can I make it work while actually deleting the nodes I want to delete from memory?
2. Is this a correct way of implementing skip lists, or am I using a wrong approach?

Answer 1

In your Remove function your outer loop iterates over the list for the count of the current number of entries. Then in the loop you remove one of those ntries but keep on iterating over the old count.

Answer 2

There is an issue with the Remove method, as you guessed:

void Remove(int v, List *L)
{
    Node *current = L->Header;

    for ( int i = L->H - 1; i >= 0; --i )
    {
        for ( ; current->link_[i] != NULL; current = current->link_[i] )
        {
            if ( current->link_[i]->info > v )
            {
                break;
            }
            else if ( current->link_[i]->info == v )
            {
                // Node *del = current->link_[i];
                current->link_[i] = current->link_[i]->link_[i];

                // if (0 == i) delete del;
                break;
            }
        }
    }
}

For the sake of example, let's assume that the node we wish to delete appears in 2 levels: 0 and 1.

The for loop on levels L->H to 2 does not do anything.

On level 1 it will find the node requested, and delete it.

On level 0, it will attempt to follow a pointer to the already deleted node, leading to undefined behavior.

Solution:

Only delete the node when at level 0. As long as your in a upper layer, the node is still referenced and you need to keep it alive.