30:T484,md`# SkipList Skip lists are a probabilistic data structure designed to support the basic operations of _searching_, _insertion_ and _deletion_ with asymptotic time complexity of a general balanced tree implementation, while being more efficient in terms of memory [1]. Other miscellaneous operations (such as _merging_) happen asymptotically faster in skip lists than in its tree counterparts. For a brief insight in the internal structure of this object, this list is built in many levels, as depicted below.

When searching for a list node to interact with, it's not necessary to walk through each item. Instead, the algorithm walks in leaps. This is done by setting random heights for each node in such a way that is less likely that the nodes get very tall (the procedure is shown in the code). Then, we begin at the topmost level, going ahead until a node whose key is greater than ours is found. At this moment, either we found the desired node or we must continue our raid in the level below. Once we've reached the lowest level without any success, the search fails. `31:T9d5,class SkipList { constructor (max_level=10, p=0.5) { this.level = 1; this.maxLevel = max_level; this.p = p; // Growth probability this.header = new Node(-Infinity, null, this.maxLevel); // Node(key, val, level) } Insert (key, val) { /* Insertion */ let update = newArray(this.maxLevel, NIL); let x = this.header; // Search for (let i = this.level - 1; i >= 0; i--) { while (x.forward[i].key < key) { x = x.forward[i]; } update[i] = x; } x = x.forward[0] if (x.key == key) { x.val = val; } else { let new_level = this.randomLevel(); if (new_level > this.level) { for (let i = this.level; i < new_level; i++) { update[i] = this.header; } this.level = new_level; } // Create node to insert x = new Node(key, val, new_level); for (let i=0; i= 0; i--) { while (x.forward[i].key < key) { x = x.forward[i]; } } x = x.forward[0]; if (x.key == key) { return x.val; } else { return undefined; } } Delete (key) { /* Deletion */ let update = newArray(this.maxLevel, NIL); let x = this.header; // Search for (let i=this.level - 1; i >= 0; i--) { while (x.forward[i].key < key) { x = x.forward[i]; } update[i] = x; } x = x.forward[0]; if (x.key === key) { for (let i = 0; i < this.level; i++) { if (update[i].forward[i] != x) { break; } else { update[i].forward[i] = x.forward[i]; } } while (this.level > 0 && this.header.forward[this.level] === NIL) { this.level--; } } else { throw `Key Error: key '${key}' not found.`; } } toString() { let s = "header"; let x = this.header; while (x.forward[0] != NIL) { x = x.forward[0] s = s + ` -> [${x.key}|${x.val}]`; } return s + " -> NIL"; } randomLevel () { let level = 1; while (Math.random() < this.p) { // biased coin toss level++; } return level } };32:T5cd,graphViz = function(sl) { let header = {key:'H', forward:[...sl.header.forward]} let top = header.forward.length; while (header.forward[top-1] == NIL && top > 1) top--; let keys = []; for (let i = 0; i < top; i++) keys[i] = header.key; header.forward.length = top; let node; let next = function () { node = header.forward[0]; header.key = node.key; if (!node.forward) return; for (let i = 0; i < node.forward.length; i++) { header.forward[i] = node.forward[i]; keys[i] = node.key } } let result = ""; let emitNode = function(node) { let box = [node.key == 'H' ? '-∞' : (node.key==Infinity ? '∞' : node.key)]; let n = top; if (node.forward) n = node.forward.length; for (let i = 0; i < n; i++) box.push(`<${i}>`); result+= `struct${node.key}[ label = "${box.join("|")}" ];\n` } let emitLinks = function (node) { let n = top; if (node.forward) n = node.forward.length; for (let i = 0; i < n; i++) { result += `struct${keys[i]}:<${i}>->struct${node.key}:<${i}>;\n` } } node = header; for(;;) { emitNode(node); if (!node.forward) break next() } header = {key:'H', forward:[...sl.header.forward]}; for (let i = 0; i < top; i++) keys[i] = header.key; for(;;) { emitLinks(header.forward[0]); next() if (!node.forward) break } return `digraph{ rankdir=LR; node [ shape=record margin=0 width=0.3 fontsize=12 ]; ${result}}`; }33:[{"id":"3ad09c579d8fe31c055a04d6236a54aac101f6d5bdabcedb27e41062b74ddc2dde0375972ba241742b3d89c7b1e86eb5a284d716a2aeb40c1857986e55530ee5","href":"https://static.observableusercontent.com/files/3ad09c579d8fe31c055a04d6236a54aac101f6d5bdabcedb27e41062b74ddc2dde0375972ba241742b3d89c7b1e86eb5a284d716a2aeb40c1857986e55530ee5","name":"image.png","type":"image/png","lastModified":1601738697332.67,"size":14891}] 2e:{"title":"SkipList","cells":[{"id":0,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":398,"value":"md`### Details\nBefore diving into the code, let's see an overview on some of the elements that appear below.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":303,"value":"md`The function \\`newArray(size, value=null)\\` initializes an Array filled with \\`size\\` copies of \\`value\\`. Equivalent to the Python statement
\\`>>> L = [value] * size\\`.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":161,"value":"function newArray(size, value=null) {\n return new Array(size).fill(value)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":319,"value":"md`The \\`NIL\\` object is present at the end of each level in the SkipList. Its \\`key\\`, represented here by \\`Infinity\\`, is higher than any other found in the list. Its \\`val\\` and \\`forward\\` attributes aren't necessary, but intend to resemble \\`Node\\` behaviour.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":251,"value":"NIL = ({\n 'key' : Infinity,\n 'val' : null,\n 'forward' : null,\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":335,"value":"md`Each \\`Node\\` contains a \\`key\\`, a \\`val\\` and also a \\`forward\\` attribute. The \\`key\\` is what indexes each \\`Node\\` and is exactly what the \\`Insert\\`, \\`Search\\` and \\`Delete\\` operations will run against. \\`val\\` contains the value store in each \\`Node\\` and may be any kind of object.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":5,"value":"class Node {\n constructor (key, val, level) {\n this.key = key\n this.val = val\n this.forward = newArray(level, NIL); // null array\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":346,"value":"md`\nFinally, the \\`SkipList\\` itself.\n\n- \\`Search(key)\\`
\n Searching starts at the topmost level in the list. At every step, a pointer goes forward until a node with key greater than or equal to \\`key\\` is found. It returns the \\`value\\` stored in the target node. If the \\`key\\` is absent, returns \\`undefined\\`, as expected for JS objects.\n\n- \\`Insert(key, value)\\`
\n Insertion is preceded by searching for the appropriate place to insert a new node. If the \\`key\\` is already there, we simply exchange the \\`value\\` attribute of that node. If we've got a fresh \\`key\\` to insert, we create a new node and relink the previous and next nodes to fit the new one. Keeping track of these links is done with the aid of the \\`update\\` vector.\n\n- \\`Delete(key)\\`
\n Deletion follows pretty much like insertion does. When the key is found, relinking is carried between the node's neighbours. If the search fails, an error is thrown.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":141,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":436,"value":"md`## An Example`","pinned":false,"hidden":false,"mode":"ojs"},{"id":522,"value":"viewof refresh = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":452,"value":"sl = {\n refresh;\n let L = new SkipList();\n for (let [key, value] of [\n [2, \"two\"],\n [4, \"four\"],\n [10, \"ten\"],\n [7, \"seven\"],\n [3, \"three\"],\n [1, \"one\"],\n [9, \"nine\"],\n [5, \"five\"],\n [6, \"six\"],\n [8, \"eight\"]\n ]) {\n L.Insert(key, value);\n }\n return L;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":467,"value":"dot`${graphViz(sl)}`","pinned":true,"hidden":false,"mode":"ojs"},{"id":148,"value":"md`## Bibliography\n1. William Pugh, _A Skip List Cookbook_, University of Maryland, 1990.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":514,"value":"md`## Drawing code`","pinned":false,"hidden":false,"mode":"ojs"},{"id":454,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":443,"value":"dot = require(\"@observablehq/graphviz\")","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}