5
\$\begingroup\$

Please review my skip list code that is implemented using a linked list. It supports the insertion and deletion of numeric values.

I'd like to know whether I implemented the skip list in its true sense or not.

Check it out on github also.

include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <ctime>
#include<windows.h>
using namespace std;
#define maxLevel 5;

struct node{
    double x;
    int key;
    node *next;
    node *up;
    node *bottom;
    node *prev;
};
bool flip()//for Randomly Generating LEVELS
{
    return rand()%2;

}
void add(node *pre, node *curr, double val)//Add NODE after the given node
{
    if (pre->x>val) {
            cout<<"pre\t"<<pre->x<<endl;

        cout<<"pre_after\t"<<pre->x<<endl;

    }


    curr->next=pre->next;
    curr->prev=pre;
    pre->next=curr;
        curr->x=val;
        curr->up=NULL;
        curr->bottom=NULL;

   }
void display(node *temp)//Display
{
    while (temp) {
        if (temp->prev) {
             cout<<temp->x<<"\t";
        }

        temp=temp->next;
    }
    cout<<endl;
   }
node *bottom(node *temp){
   return temp->bottom;
}
node *up(node *temp){
    return temp->up;
}
node *prev(node *temp){
    return temp->prev;
}
node *next(node *temp){
    return temp->next;
}
node *maxNode(node *temp){
    while (temp->up) {
        temp=temp->up;
    }
    return temp;
}
node *maxNode(node *temp, int level){
    for (int i=2; i<=level; i++) {
        temp=up(temp);
    }
    return temp;
}
node *position(node *temp, double val){
  // cout<<temp->x<<endl;
    int le=1;
        while (temp->bottom) {

            if (temp->next) {
                node *a=temp->next;

                while (temp->x<=val && temp->next && a->x<=val )
                {

                    a=a->next;

                    temp=temp->next;

                }
            }


                       temp=temp->bottom;
            ++le;
        }

    node *v=temp->next;
    while (temp->next && temp->x<=val && v->x<=val) {

        temp=temp->next;
        v=v->next;
    }

    return temp;
}
void insertAFterAbove(node *temp, node *curr){
    node *a=temp->next;
    curr->next=a;
    if (a) {
         a->prev=curr;
    }

    curr->prev=temp;
    temp->next=curr;

}
node* level(node *temp, int lev){
    node *curr=new node;
    temp->up=curr;
    curr->x=temp->x;
    curr->bottom=temp;
    curr->next=NULL;
    curr->prev=NULL;
    while (temp->prev && !temp->up) {
        temp=prev(temp);
    }
valid:
    int check=1;
    while (check!=lev && temp->up  ) {
        temp=up(temp);
        ++check;
    }
    if (check!=lev) {
        temp=prev(temp);
        while (temp->prev && !temp->up) {
            temp=prev(temp);
        }
        goto valid;
    }
    insertAFterAbove(temp, curr);
    return  curr;
    }
node* creaTenode(node *curr){
    node *temp=new node;
    temp->x=curr->x;
    temp->bottom=curr;
    temp->up=NULL;
    temp->next=NULL;
    temp->prev=NULL;
    curr->up=temp;
    return temp;

}
void deleteNode(node *temp){
    node *pre=temp->prev;

    pre->next=temp->next;
    temp=temp->next;
    if (temp) {
        temp->prev=pre;
    }

}
void menu(){
    cout<<"1 == > INSERT\n";
    cout<<"2 == > DELETE\n";
     cout<<"3 == > DISPLAY\n";
}
int main(int argc, const char * argv[])
{
   srand (time(NULL));
    node *start;
    start=new node;
    start->next=NULL;
    start->bottom=NULL;
    start->up=NULL;
    start->prev=NULL;
    start->x=-888888888888888;
    node *temp=start;
    int max=maxLevel;
    for (int i=2; i<=max; i++) {
            node *curr=new node;
            curr->next=NULL;
            curr->bottom=temp;
            curr->next=NULL;
            curr->prev=NULL;
            curr->up=NULL;
            curr->x=i*-888888888888888;
            temp->up=curr;
            temp=curr;
        }
           cout<<endl;
    while (1) {
              system("cls");
              system("color 4f");
        if (start->next) {

        }
        else {
            cout<<"LIST EMPTY!\n\n";
        }
        menu();
        int choice;
        cout<<"YOUR CHOICE :\t";
        cin>>choice;
          system("color 30");
        switch (choice) {
            case 1:
            {
                system("cls");

                //Initializing...............
                double num;
                temp=start;
                cout<<"ENTER THE NUMBER :\t";
                cin>>num;
                if(!start->next)
                {
                    temp=start;
                    node *curr=new node;
                    curr->prev=start;
                    start->next=curr;
                    curr->x=num;
                    curr->up=NULL;
                    curr->bottom=NULL;
                    curr->next=NULL;
                }
                else {
                    temp=position(maxNode(temp), num);
                    node *curr=new node;
                    add(temp, curr, num);
                    int check=1;
                    while (check!=max) {
                        int coin=flip();
                        if (!coin) {
                            break;
                        }

                        curr=creaTenode(curr);
                        while (!temp->up) {

                            temp=temp->prev;


                        }

                        temp=temp->up;

                        insertAFterAbove(temp, curr);
                        ++check;

                    }

                }
                system("pause");
                break;

            }
            case 2:{
                  system("cls");
                if (start->next) {
                        cout<<"\n==================\n";
            display(start);
            cout<<"\n==================\n";
                    cout<<"ENTER THE VALUE TO DELETE :\t";
                    double del;
                    cin>>del;
                    temp=start;
                    temp=position(temp, del);
                    if (temp->x==del) {
                        while (temp) {
                            deleteNode(temp);
                            temp=temp->up;
                        }
                        cout<<"\n------->DELETED!\n";
                    }
                    else {
                            system("color 4f");
                        cout<<"Incorrect Number entered!\n";
                    }

                }
                else {
                        system("color 4f");
                    cout<<"\n==================\n";
                     cerr<<"OOOOOOOPS! LIST IS EMPTY__!\n";
                    cout<<"\n==================\n";
                }
                  system("pause");
                break;

            }//case-----2----ends
            case 3:{
                  system("cls");
                if (start->next) {
                    cout<<"\n==================\n";

                    temp=start;

                        display(temp);

                    cout<<"\n==================\n";
                }
                else {
                        system("color 4f");
                    cout<<"\n==================\n";
                    cerr<<"OOOOOOOPS! LIST IS EMPTY__!\n";
                    cout<<"\n==================\n";
                }
                  system("pause");
                break;
            }//case 3 ___ENDs;;;;;;
            default:{

               system("color 4f");
                cerr<<"INCORRRECT CHOICE\n";
                system("pause");
                break;
            }
        }
    }

    return 0;
}
\$\endgroup\$
0

2 Answers 2

5
\$\begingroup\$

I main issue with this code is that it is not C++ (it's more C like).

But you asked for a C++ review.
So here it is.

==========

Overall Design:

You don't encapsulate you list.

  • So there is no distinguishing what is part of your public and private interface (that's just going to blow up)
  • The user is responsible for resource management (bad design).
  • You are using pointers rather than local variables (bad design)

Yo be honest there is so much manipulation of the object outside the context of the functions its hard to see if your invariants are maintained. So the code is really hard to read and even harder to verify if it is correct.

SkipList Design

I find it hard to follow your code so I can't really tell if you implemented a skip list.

BUT this is not the structure I would expect from a skip list.

struct node{
    double x;
    int key;
    node *next;
    node *up;
    node *bottom;
    node *prev;
};

To me this should look more like:

struct node{
    double x;                   // the value

    std::vector<node*> next;    // invariant next.size() == prev.size()
    std::vector<node*> prev;

    // next[0]  is the next value in the chain.
    // next[1]  skips some elements
    // next[2]  skips even more elements.
    // etc.
    // The size of this depends on the total length of the list.
    // and is an implementation details. I have seen implementation
    // That use powers of 2 or 10 or some custom value for each level.
};

Here is a picture of a skip list that uses powers of 2 for each level.

SkipList

Issues:

You have a goto!

valid:
    // STUFF 
    if (check!=lev) {
        // STUFF
        goto valid;
    }

Technically still legal. But in my 40 years I have only needed to use goto twice and one of those times there was a better way. The goto makes your code less readable (many papers on the subject) and it has been shown that it can nearly always be replaced by higher level constructs.

So unless you can prove that the goto makes the code more readable than the alternative I think you will have a big issue. So you need a big comment around the goto explaining why this is the better solution.

Not Creating Objects in valid state

Your code just uses new to allocate an object.

start=new node;         // user allocates a node
start->next=NULL;       // then has to initialize it.
start->bottom=NULL;     // You should have a function that creates
start->up=NULL;         // and initializes all these members
start->prev=NULL;
start->x=-888888888888888;

The user of your code should never be manipulating any of the internal members of your node structure. They should only do that threw the access functions you provide (to make sure the internal structure stays consistent.

PS. You can set everything to NULL by zero initializing your object on construction.

start = new node();   // forces zero-init
//
start = new node{};   // Same thing but a more modern style C++14

Naming conventions

One of the most important things in C++ is Types. So we like to distinguish Types (a compile time concept) from objects (a run-time concept). So in C++ it is generally accepted (not universal) that (user defined) type names have a leading uppercase letter while objects have a leading lower case letter.

While we are on conventions. Putting the * to indicate pointer next to the member name is a C convention. In C++ it is more traditional to put the * next to the type. This is because it is part of the type information of the member. The type of the member is Node*.

struct Node        // Make this uppercase so we can see it is a type.
{
    double x;
    int    key;
    Node*  next;
    Node*  up;
    Node*  bottom;
    Node*  prev;
};

Inconsistent Indentation

curr->next=pre->next;
curr->prev=pre;
pre->next=curr;
    curr->x=val;
    curr->up=NULL;
    curr->bottom=NULL;

Please you are supposed to be making this easy to read for humans. Please be consistent with your indentation.

Output

void display(node *temp)//Display

The standard out (std::cout) is not the only stream you way mant to serialize to. So you should pass a stream to this function (it can default to std::cout).

void display(node *temp, std::ostream& stream = std::cout)//Display

Also in C++ the default way to print something is via the operator<< so you should also define one of those:

std::ostream& operator<<(std::ostream& str, node* node) {
    display(node, str);
    return str;
}

Stop Using NULL

The problem with NULL is that it is a type of integer and thus can change its type very easily. For this reason we don't use it in C++ (its a C construct).

C++ has nullptr. This is a literal that represents the null pointer. It has a type of std::nullptr_t and can convert to any other pointer type. BUT it will not convert to something that is not a pointer.

Prefer "\n" over `std::endl

The difference between the two is that std::endl flushes the stream. The stream will already flush itself when required. So you forcing a flush will only make the output operations less efficient.

Bug 1

Lets start with the comment on this line.
That is absolutely not helpful in any way. Which node am I adding (there are two of them). And the name of the function is add and takes two nodes so I can guess this functions add's a node. **DO NOT* add useless comments.

Now lets look at the names of the parameters: pre and curr. to me this looks like these are both already members of the list and you are adding val in some way. You need to come up with much better names.

But after reading the code that's not what's happening. You are adding the node curr to the list and putting val into curr. WHY are val and curr two different parameters!!!!

void add(node *pre, node *curr, double val)//Add NODE after the given node
{

    // OK so you are adding `curr` to the doubly linked chain.
    // These two look good.
    curr->next=pre->next;
    curr->prev=pre;

    // Yes so that looks good.
    pre->next=curr;

    // Seems like you forgot a value.
    // If the old value of `pre->next` pointed at a member in the chain
    // then it still points back at `pre` So if you link backwards along
    // the chain the you will skip over `curr`

    // Sure but should these not have already been initialized!!!
    // Why waste time setting them twice.
        curr->x=val;
        curr->up=NULL;
        curr->bottom=NULL;

Bug 2

Are you sure when printing the list you don't want to display the first value?

void display(node *temp)//Display
{
    while (temp) {
        // This prints all but the first value.
        if (temp->prev) {
             cout<<temp->x<<"\t";
        }

        temp=temp->next;
    }
    cout<<endl;
   }

I think you may have wanted:

void display(node *temp)//Display
{
    while (temp) {
        if (temp->prev) {
             // Don't print a tab before the first value.
             cout << "\t";
        }
        cout << temp->x
        temp=temp->next;
    }
    cout << "\n";
}

Also this could have been written much nicer with a for loop:

void display(node *temp)//Display
{
    for(;temp;temp = temp->next) {
        if (temp->prev) {
             // Don't print a tab before the first value.
             cout << "\t";
        }
        // Add some spaces around your << operator.
        // It makes it nicer to read for us humans.
        cout << temp->x
    }
    cout << "\n";
}

I think that is more than enough on a first review:

Overall I doubt that works (I found one bug in the first function). I checked your github account and there were no unit tests. TDD is a good technique. Set up your github account to build on Travis_CI and add some unit tests.

Overall I think you need to rewrite this from scratch using correct C++ techniques. Encapsulate your skip list in a class. The class contains its own Node class internally that is never exposed externally.

First build a doubly linked list get that reviewed here then once you have that correct upgrade it to a skip list.

\$\endgroup\$
2
\$\begingroup\$

I'm only going to review the very obvious points of your code without going deeper into its functionality.

Fix your formatting to be consistent

Stuff like

void add(node *pre, node *curr, double val)//Add NODE after the given node
{
    if (pre->x>val) {
            cout<<"pre\t"<<pre->x<<endl;

        cout<<"pre_after\t"<<pre->x<<endl;

    }


    curr->next=pre->next;
    curr->prev=pre;
    pre->next=curr;
        curr->x=val;
        curr->up=NULL;
        curr->bottom=NULL;

   }

is hard to read. It should be formatted consistently like this

void add(node *pre, node *curr, double val)//Add NODE after the given node
{
    if (pre->x>val) {
        cout<<"pre\t"<<pre->x<<endl;
        cout<<"pre_after\t"<<pre->x<<endl;
    }
    curr->next=pre->next;
    curr->prev=pre;
    pre->next=curr;
    curr->x=val;
    curr->up=NULL;
    curr->bottom=NULL;
}

Write portable code whenever possible

Don't include any non portable headers when these aren't necessary to compile your code.

#include<windows.h>

should be omitted.

Don't use using namespace std;

For various reasons you should not do that. Rather use specific using statements like

using std::cout;

for the stuff you really need, or prefix the std:: namespace scope explicitly.

Don't declare functions unnecessarily

A function like

bool flip()//for Randomly Generating LEVELS
{
    return rand()%2;

}

isn't really useful. It's usage should be just replaced with the body (and may be a comment along).

Don't use srand(), rand() with modern c++

Use a better random number generator than

srand(time(0));

// ...

rand();

There are various random generators available with the current standard in the numerics library.

Don't use macros

#define maxLevel 5;

should be

const int maxLevel = 5;

or

constexpr int maxLevel = 5;

for sake of type safety and clarity.

Don't use system() calls

For the same reasons of portability I mentioned earlier, don't use stuff like

system("pause");
system("cls");
system("color 4f");

Don't use magic numbers

Code like

start->x=-888888888888888; 

is semantically unclear. Better define a named const variable that makes it clear what the purpose of the value -888888888888888 is in your context.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.