javascript-algorithms

javascript-algorithms copied to clipboard

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?

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

I want to take this i can fix

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

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.