阅读中文版本

Skip List CLI

A Node CLI that implements a skip list with probabilistic levels, accepting insert and search commands from stdin and printing search results.

node --version

printf "insert 5\ninsert 1\ninsert 3\nsearch 3\nsearch 2" | node skiplist.mjs

node --test skiplist.test.mjs

Prints "found" or "not found" for each search command, using a skip list with O(log n) expected insert and search.

What it does

Implements a skip list with a maximum of 16 levels and a 0.5 promotion probability. Insert assigns a random level and links the node at each level; search walks the top levels down, skipping ahead at each level. Both operations are O(log n) in expectation.

const MAX = 16, P = 0.5;
const head = { val: -Infinity, next: new Array(MAX).fill(null) };
const randLevel = () => { let l = 1; while (l < MAX && Math.random() < P) l++; return l; };
const insert = v => {
  const lvl = randLevel(), update = new Array(MAX).fill(head);
  let cur = head;
  for (let i = MAX - 1; i >= 0; i--) { while (cur.next[i] && cur.next[i].val < v) cur = cur.next[i]; update[i] = cur; }
  const node = { val: v, next: new Array(lvl).fill(null) };
  for (let i = 0; i < lvl; i++) { node.next[i] = update[i].next[i]; update[i].next[i] = node; }
};
const search = v => {
  let cur = head;
  for (let i = MAX - 1; i >= 0; i--) while (cur.next[i] && cur.next[i].val < v) cur = cur.next[i];
  return cur.next[0] && cur.next[0].val === v;
};
const rl = require('readline').createInterface({ input: process.stdin });
rl.on('line', cmd => {
  const [op, val] = cmd.split(' ');
  if (op === 'insert') insert(+val); else if (op === 'search') console.log(search(+val) ? 'found' : 'not found');
});

Run and verify

printf "insert 5\ninsert 1\ninsert 3\nsearch 3\nsearch 2" | node skiplist.mjs

Run the test command to check the implementation: node --test skiplist.test.mjs.

Expected Output

After inserting 5, 1, 3, searching for 3 finds it and searching for 2 does not:

found
not found

Limitations

The skip list is in-memory and not persisted. The level distribution is probabilistic, so the worst case is O(n) though the expected case is O(log n). No deletion is implemented.