2e:null 2f:["$","title",null,{"children":"Reversing Linked Lists | Mike Bostock | Observable"}] 34:T521,LinkedList = { class LinkedList { static of(...nodes) { const list = new LinkedList; for (const node of nodes) list.insert(node); return list; } constructor() { this.head = null; } *[Symbol.iterator]() { let node = this.head; while (node) { yield node; node = node.next; } } insert(node, where = null) { node.next = where; let prev = null, next = this.head; while (next !== where) prev = next, next = next.next; if (prev) prev.next = node; else this.head = node; return this; } remove(node) { let prev = null, next = this.head; while (next !== node) prev = next, next = next.next; if (prev) prev.next = node.next; else this.head = node.next; node.next = null; return this; } reverse() { let node = this.head; if (!node) return this; let prev = null; let next = node.next; while (next) { node.next = prev; prev = node; node = next; next = next.next; } node.next = prev; this.head = node; return this; } } LinkedList.Node = class Node { constructor(value) { this.value = value; this.next = null; } }; return LinkedList; }35:[] 32:{"id":"c3ccf9823b74364f","slug":"reversing-linked-lists","title":"Reversing Linked Lists","thumbnail":"cc0724e7abbdd8be5971ba1cff53d6b6c6ad33f3f1d7e3cbeacf29f470ebb874","access_level":"public","create_time":"$D2018-10-01T22:44:51.181Z","update_time":"$D2018-10-01T23:22:26.922Z","view_time":null,"first_public_time":"$D2018-10-01T23:22:59.637Z","has_unpublished_edits":null,"fork":false,"stars":9,"starred":false,"owner":{"type":"team","id":"8c2e47252fd4995c","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":"pro_2026"},"version":168,"publish_version":168,"role":null,"authored":false,"authors":[{"type":"individual","id":"074c414ad1d825f5","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":null}],"members":[{"type":"individual","id":"074c414ad1d825f5","login":"mbostock","name":"Mike Bostock","avatar_url":"https://avatars-next.observableusercontent.com/7dbba99ced40bd5ab8013c99b1a11da61231bce321ba1148a9d16ad0f121550a","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"d9361552bd1f55f4","slug":"data-structures","title":"Data Structures","owner":{"id":"8c2e47252fd4995c","login":"mbostock","name":"Mike Bostock"}},"type":"notebook","body":{"title":"Reversing Linked Lists","cells":[{"id":0,"value":"md`# Reversing Linked Lists\n\nIn these diagrams,\n
the previous node is magenta.\n
the current node is orange.\n
the next node is cyan.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":90,"value":"md`Since we start with the head of the list, the previous node is null. The current node is the head of the list, *A*, and *A*’s next node is *B*.\n\n${dot`digraph {\n rankdir = LR;\n A [color=orange]\n B [color=cyan]\n C\n D\n A -> B -> C -> D\n}`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"md`At each step, we set the current node’s next edge to be the previous node. So to start, that means *A*’s next node is now null.\n\n${dot`digraph {\n rankdir = LR;\n A [color=orange]\n B [color=cyan]\n C\n D\n B -> C -> D\n}`}\n\nThen we advance the previous node to the current node, the current node to the next node, and the next node to the next node’s next node.\n\n${dot`digraph {\n rankdir = LR;\n A [color=magenta]\n B [color=orange]\n C [color=cyan]\n D\n B -> C -> D\n}`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"md`Repeating the process, we set *B*’s next node to *A*:\n\n${dot`digraph {\n rankdir = LR;\n A [color=magenta]\n B [color=orange]\n C [color=cyan]\n D\n B -> A\n C -> D\n}`}\n\nAdvancing:\n\n${dot`digraph {\n rankdir = LR;\n A\n B [color=magenta]\n C [color=orange]\n D [color=cyan]\n B -> A\n C -> D\n}`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"md`Repeating the process, we set *C*’s next node to *B*:\n\n${dot`digraph {\n rankdir = LR;\n A\n B [color=magenta]\n C [color=orange]\n D [color=cyan]\n C -> B -> A\n}`}\n\nAdvancing:\n\n${dot`digraph {\n rankdir = LR;\n A\n B\n C [color=magenta]\n D [color=orange]\n C -> B -> A\n}`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":25,"value":"md`Repeating the process, we set *D*’s next node to *C*:\n\n${dot`digraph {\n rankdir = LR;\n A\n B\n C [color=magenta]\n D [color=orange]\n D -> C -> B -> A\n}`}\n\nSince the next node (cyan) is null, *D* is the new head, and we’re done!`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"{\n const a = new LinkedList.Node(\"A\");\n const b = new LinkedList.Node(\"B\");\n const c = new LinkedList.Node(\"C\");\n const d = new LinkedList.Node(\"D\");\n return LinkedList.of(a, b, c, d).reverse();\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":148,"value":"md`An animated version:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":136,"value":"viewof play = html`