2b:null 2c:["$","title",null,{"children":"SkipList | Pedro Maciel Xavier | Observable"}] 31: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. `32: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 } };33:[{"id":"3ad09c579d8fe31c055a04d6236a54aac101f6d5bdabcedb27e41062b74ddc2dde0375972ba241742b3d89c7b1e86eb5a284d716a2aeb40c1857986e55530ee5","href":"https://static.observableusercontent.com/files/3ad09c579d8fe31c055a04d6236a54aac101f6d5bdabcedb27e41062b74ddc2dde0375972ba241742b3d89c7b1e86eb5a284d716a2aeb40c1857986e55530ee5","name":"image.png","type":"image/png","lastModified":1599448310998.44,"size":14891}] 2f:{"id":"4599b13972dd2e2a","slug":"skiplist","title":"SkipList","thumbnail":"ca592a9a5b56d042be951adb47bac238019caf7dba798f2e543fb9be67c4dc53","access_level":"public","create_time":"$D2020-04-03T02:31:30.468Z","update_time":"$D2020-09-08T04:47:13.599Z","view_time":null,"first_public_time":"$D2020-04-03T02:32:05.865Z","fork":false,"stars":3,"starred":false,"owner":{"type":"team","id":"b0809a55bfcdd12f","login":"pedromxavier","name":"Pedro Maciel Xavier","avatar_url":"https://avatars-next.observableusercontent.com/50648ee559603e01ca45dc9167ada9140b1bc8ddee5d1469243ac98ca00d916a","tier":"starter_2024"},"version":440,"publish_version":440,"role":null,"authored":false,"authors":[{"type":"individual","id":"e343985e3b3b129c","login":"pedromxavier","name":"Pedro Maciel Xavier","avatar_url":"https://avatars-next.observableusercontent.com/50648ee559603e01ca45dc9167ada9140b1bc8ddee5d1469243ac98ca00d916a","tier":null}],"members":[{"type":"individual","id":"e343985e3b3b129c","login":"pedromxavier","name":"Pedro Maciel Xavier","avatar_url":"https://avatars-next.observableusercontent.com/50648ee559603e01ca45dc9167ada9140b1bc8ddee5d1469243ac98ca00d916a","tier":null,"role":"editor"}],"comments":[{"id":"a81157614d7bef97","reply_to_id":null,"content":"... or equal _to_ key is found","create_time":"$D2020-08-31T20:02:00.568Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null}},{"id":"59d1cfdabeebc500","reply_to_id":"a81157614d7bef97","content":"What does Search return?\nAlso, ordinarily I think methods should start with lowercase letters rather than uppercase, which should be reserved for classes... But it's just a style preference.","create_time":"$D2020-08-31T20:05:51.075Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null}},{"id":"f4e4c19592d53611","reply_to_id":null,"content":"What is a skip list? I think you should give a very short description about what it is and what are the advantages with regard to, say, red-black trees or other deterministic data structures...","create_time":"$D2020-08-31T20:07:39.268Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null}},{"id":"7e8a3523a8314c5a","reply_to_id":null,"content":"This looks weird, since Search seemingly does not return anything...","create_time":"$D2020-08-31T20:10:35.741Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null}},{"id":"08da9ddd0b92e56c","reply_to_id":"7e8a3523a8314c5a","content":"It was a problem with the lazy (topological) order of execution in this environment. The search was executed before the insertions.\n\nI've included the same line in the previous cell for a working example.","create_time":"$D2020-09-07T02:05:02.110Z","update_time":"$D2020-09-07T02:06:47.581Z","resolved":true,"user":{"type":"individual","id":"e343985e3b3b129c","login":"pedromxavier","name":"Pedro Maciel Xavier","avatar_url":"https://avatars-next.observableusercontent.com/50648ee559603e01ca45dc9167ada9140b1bc8ddee5d1469243ac98ca00d916a","tier":null}},{"id":"20c8b286470d347e","reply_to_id":"a81157614d7bef97","content":"I've written in lowercase before but there was a conflict with the js keyword `delete`. Switching to uppercase sounded the nearest workaround to me.","create_time":"$D2020-09-07T02:09:34.210Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"e343985e3b3b129c","login":"pedromxavier","name":"Pedro Maciel Xavier","avatar_url":"https://avatars-next.observableusercontent.com/50648ee559603e01ca45dc9167ada9140b1bc8ddee5d1469243ac98ca00d916a","tier":null}},{"id":"57fe59001f71e5e8","reply_to_id":"7e8a3523a8314c5a","content":"Good! Now you can remove this cell.","create_time":"$D2020-09-08T02:46:42.134Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null}},{"id":"7f584a9a027cf3d1","reply_to_id":null,"content":"I would start with an empty list defined in the block itself. Like so (see below).","create_time":"$D2020-09-08T02:49:57.540Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null}}],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"title":"SkipList","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"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","author":"$undefined","summary":"$undefined"},{"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","author":"$undefined","summary":"$undefined"},{"id":161,"value":"function newArray(size, value=null) {\n return new Array(size).fill(value)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"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","author":"$undefined","summary":"$undefined"},{"id":251,"value":"NIL = ({\n 'key' : Infinity,\n 'val' : null,\n 'forward' : null,\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"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","author":"$undefined","summary":"$undefined"},{"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","author":"$undefined","summary":"$undefined"},{"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","author":"$undefined","summary":"$undefined"},{"id":141,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":436,"value":"md`## An Example`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":263,"value":"{\n let L = new SkipList();\n L.Insert(0, 'zero');\n L.Insert(1, 'one');\n L.Insert(10, 'ten');\n L.Insert(11, 'eleven');\n L.Insert(13, 'thirteen'); // Try commenting this line!\n L.Delete(13);\n return [\n L.Search(0),\n L.Search(1),\n L.Search(2),\n L.Search(10),\n L.Search(11),\n L.Search(12),\n L.Search(13),\n L.toString()\n ];\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":148,"value":"md`Bibliography\n1. William Pugh, _A Skip List Cookbook_, University of Maryland, 1990.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W33","stdlib":"1","titling":"auto"}} 30:"$2f:body"