Skip List — Probabilistic Alternative to Balanced BSTs

int randomLevel() {
  int lvl = 0;
  while (Math.random() < 0.5 && lvl < MAX_LEVEL) lvl++;
  return lvl;
}
void insert(int val) {
  int lvl = randomLevel();
  Node newNode = new Node(val, lvl + 1);
  Node cur = head;
  for (int i = lvl; i >= 0; i--) {
    while (cur.next[i] != null && cur.next[i].val < val) cur = cur.next[i];
    newNode.next[i] = cur.next[i];
    cur.next[i] = newNode;
  }
}