Insert skip list

[midnight stump]

Hi, I'm trying to get my skip list working but ive looked over my code and can't find the problem. Randomlevel just produces a number thats at least 1 and at most the MaxLevel+1. Maxlevel is stored in the skiplist. MaxLevel gets updated in the insert function which you can see. My skip list only inserts numbers that is smaller than the first element. My node only contains the key value and the dynamic array of node pointers. Any ideas as to where the problem could be would be very helpful. I don't have an infinity node, im using nullpointers instead. If youd like to see the node or any other part of the class let me know.

[steady flame]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

@midnight stump

Screenshots!

Your message appears to contain screenshots but no code. Please send code and error messages in text instead of screenshots if applicable!

[unkempt jacinth]

!f

[steady flame]

void Insert(int x) {
  Node* current = first;

  int lvl = randomLevel();
  if (lvl > MaxLvl) {
    Node** newnodes = new Node*[lvl];
    for (int k = 0; k < MaxLvl; k++) {
      newnodes[k] = first->nodes[k];
    }
    for (int k = MaxLvl; k < lvl; k++) {
      newnodes[k] = nullptr;
    }
    MaxLvl = lvl;
    current->nodes = newnodes;
  }

  Node** update = new Node*[lvl];
  cout << "\nLvl: " << lvl << "For " << x << endl;
  for (int i = lvl - 1; i >= 0; i--) {
    while (current->nodes[i] != nullptr && current->nodes[i]->key < x) {
      current = current->nodes[i];
    }

    update[i] = current;
    cout << update[i]->key;
  }
  if (current->nodes[0] == nullptr || current->nodes[0]->key != x) {
    for (int i = 0; i < lvl; i++) {
      Node* insertnode = new Node(x, lvl);
      insertnode->nodes[i] = update[i]->nodes[i];
      update[i]->nodes[i] = insertnode;
      // cout << update[i]->key;
    }
  }
}

Monke

Formatted by Elias Schablowski

[unkempt jacinth]

It seems like an issue with using arrays as your levels, rather than linked lists, which might be overriding your existing nodes, though you should probably step through your code with gdb (either locally or online at https://www.onlinegdb.com)

!wiki gdb

[steady flame]

Debugging with GDB

Compile your program with -g flag and run your program using gdb: gdb yourprogname. From there, you can debug using GDB commands. Use help to list commands and their options.

Break

Set a breakpoint to pause execution at a certain line or a function:

• break main
• b 42

Run

Run your program inside gdb after setting breakpoints:

• run
• r

Print

Print value of expression:

• print my_var
• p (char) ch

Walk & Step

Execute next line of code, where next stays in the function and step enters functions:

• n
• s

Continue

Continue execution until (Nth) next breakpoint

• continue
• c 3

Backtrace

Print backtrace of all or N stack frames:

• backtrace -full
• bt 3

Learn More:

• TCCPPCon#1: Debugging with GDB
• How to Debug Using GDB
• GDB Step By Step Instruction
• GDB Cheatsheet

[midnight stump]

Is there a reason you suspect the arrays being the problem? I don't understand why it would be a problem compared to using a vector or list instead

[midnight stump]

DAMNIT

[midnight stump]

my problem ended up being that i Initialized my insertnode inside my for loop

if (current->nodes[0] == nullptr || current->nodes[0]->key != x) {
for (int i = 0; i < lvl; i++) {
Node insertnode = new Node(x, lvl);*
insertnode->nodes[i] = update[i]->nodes[i];
update[i]->nodes[i] = insertnode;
// cout << update[i]->key;
}
}

once I moved it outside it works perfectly

i hate my life