Implement new Data Structure: SkipList

[willow-iam]

https://en.wikipedia.org/wiki/Skip_list

I learned about this data structure in my distributed systems class. Could we add it to the project?

[zelf0]

Sure, I'm gonna take a crack at this!

[AshifReja]

I want to take this i can fix

[zelf0]

i still want to do this eventually but I haven't had time yet, so i guess you can go for it

[Skilly55]

class Node {
constructor(value, level) {
this.value = value;
this.next = new Array(level + 1);
this.prev = new Array(level + 1);
}
}

class SkipList {
constructor() {
this.head = new Node(-Infinity, 16);
this.level = 0;
}

randomLevel() {
let level = 0;
while (Math.random() < 0.5 && level < 16) {
level++;
}
return level;
}

insert(value) {
let update = new Array(this.head.next.length);
let node = this.head;

for (let i = this.level; i >= 0; i--) {
  while (node.next[i] && node.next[i].value < value) {
    node = node.next[i];
  }
  update[i] = node;
}

let newLevel = this.randomLevel();
if (newLevel > this.level) {
  for (let i = this.level + 1; i <= newLevel; i++) {
    update[i] = this.head;
  }
  this.level = newLevel;
}

let newNode = new Node(value, newLevel);
for (let i = 0; i <= newLevel; i++) {
  newNode.next[i] = update[i].next[i];
  newNode.prev[i] = update[i];
  update[i].next[i] = newNode;
}

}

delete(value) {
let update = new Array(this.head.next.length);
let node = this.head;

for (let i = this.level; i >= 0; i--) {
  while (node.next[i] && node.next[i].value < value) {
    node = node.next[i];
  }
  update[i] = node;
}

node = node.next[0];
if (node.value === value) {
  for (let i = 0; i <= this.level; i++) {
    if (update[i].next[i] !== node) {
      break;
    }
    update[i].next[i] = node.next[i];
  }
  while (this.level > 0 && this.head.next[this.level] === null) {
    this.level--;
  }
}

}

find(value) {
let node = this.head;

for (let i = this.level; i >= 0; i--) {
  while (node.next[i] && node.next[i].value < value) {
    node = node.next[i];
  }
}

node = node.next[0];
return node && node.value === value ? node.value : null;

}
}

This code provides the basic functionality for a skip list data structure, including the ability to insert, delete, and find values within the list.