CPP skiplist for numeric values

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
#include
#include
#include
#include
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) {
coutxxnext=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) {
coutxnext;
}
coutbottom;
}
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; ixbottom) {

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

while (temp->xnext && a->xnext;

temp=temp->next;

}
}

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

node *v=temp->next;
while (temp->next && temp->xxnext;
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

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 next;    // invariant next.size() == prev.size()
    std::vector 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.

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` flus

StackExchange Code Review Q#159256, answer score: 5