2d:null 2e:["$","title",null,{"children":"Double Linked List | John C | Observable"}] 33:T10f0,# Double Linked List This is a js implementation for double link list. It provides apis in the python `llist.dllist` style ![img](https://socs.binus.ac.id/files/2017/03/rini-8-640x160.jpg) `DoubleLinkedListNode` Class for the node in the list.
`DoubleLinkedListNode.value` value in the node.
`DoubleLinkedListNode.prev` the previous node in the list, `null` if the node is the first.
`DoubleLinkedListNode.next` the next node in the list, `null` if the node is the last.
`DoubleLinkedListNode.owner` the onwer of this node.
`DoubleLinkedList` Class for the double linked list.
`new DoubleLinkedList(object1, object2, ...)` constructor, the parameter is the objects you need to put in the list.
`DoubleLinkedList.first` first object in the list.
`DoubleLinkedList.last` last object in the list.
`DoubleLinkedList.size` number of objects in the list.
`DoubleLinkedList.append(x)` add x to the right side of the list and return the inserted node, if x is a `DoubleLinkedListNode`, the value will be extract and added to the list.
`DoubleLinkedList.appendLeft(x)` add x to the left side of the list and return the inserted node, if x is a `DoubleLinkedListNode`, the value will be extract and added to the list.
`DoubleLinkedList.appendRight(x)` add x to the right side of the list and return the inserted node, if x is a `DoubleLinkedListNode`, the value will be extract and added to the list.
`DoubleLinkedList.appendNode(x)` add a DoubleLinkedListNode to the end of the list, it should not be in a list. Return the inserted node
`DoubleLinkedList.clear()` remove all nodes in the list, but the nodes will not be destroyed immediately.
`DoubleLinkedList.extend(iterable)` append elements from the `iterable` to the right side of the list, the `iterable` can be another DoubleLinkedList or an array, it will reject TypedArray instances.
`DoubleLinkedList.extendLeft(iterable)` append elements from the `iterable` to the left side of the list, the `iterable` can be another DoubleLinkedList or an array, it will reject TypedArray instances. The elements will be appended in reversed order. (i.e. {1,2,3} appends to {4,5,6} will result in {1,2,3,4,5,6})
`DoubleLinkedList.extendRight(iterable)` append elements from the `iterable` to the right side of the list, the `iterable` can be another DoubleLinkedList or an array, it will reject TypedArray instances.
`DoubleLinkedList.insert(x, (optional) before)` add x to the right side of the list if `before` is not specified, or insert x to the left of `before`. `before` should be a `DoubleLinkedListNode`, return the inserted node.
`DoubleLinkedList.insertAfter(x, ref)` insert x after `ref` and return the inserted node.
`DoubleLinkedList.insertBefore(x, ref)` insert x before `ref` and return the inserted node.
`DoubleLinkedList.insertNode(node, (optional) before)` Add node to the right side of the list if `before` is not specified, or insert node to the left side of `DoubleLinkedListNode before`. Return the inserted node.
`DoubleLinkedList.insertNodeAfter(node, ref)` insert node after `ref` and return the inserted node.
`DoubleLinkedList.insertNodeBefore(node, ref)` insert node before `ref` and return the inserted node.
`DoubleLinkedList.iterNodes()` return a generator over nodes in the list.
`DoubleLinkedList.iterValues()` return a generator over values in the list.
`DoubleLinkedList.iter()` return a generator over values in the list.
`DoubleLinkedList.nodeAt(index)` return the node at index, negative index will count node from the righ.t
`DoubleLinkedList.pop()` remove a node from the right side of the list and return the value of it.
`DoubleLinkedList.popLeft()` remove a node from the left side of the list and return the value of it.
`DoubleLinkedList.popRight()` remove a node from the right side of the list and return the value of it.
`DoubleLinkedList.remove(node)` remove the node from the list and return the value of it.
`DoubleLinkedList.rotate(n)` rotate this list n steps to the right, if n is negative, rotate to the left.
`DoubleLinkedList.toArray()` return an array of the values in the list.
To use, copy the below in your notebook: ```js import {DoubleLinkedList} from "@real-john-cheung/dllist" ```

34:T226f,class DoubleLinkedList{ constructor(){ this.size = 0; this.first = null; this.last = null; for (let i = 0 ; i < arguments.length; i++){ this.append(arguments[i]); } } append(x){ if (x instanceof DoubleLinkedListNode) x = x.value; let newNode = new DoubleLinkedListNode(x); newNode.owner = this; if (this.first === null) { this.first = newNode; this.last = this.first; } else { this.last.next = newNode; newNode.prev = this.last; this.last = newNode; } this.size ++; return newNode; } appendLeft(x){ if (x instanceof DoubleLinkedListNode) x = x.value; let newNode = new DoubleLinkedListNode(x); newNode.owner = this; if (this.first === null) { this.first = newNode; this.last = this.first; } else { newNode.next = this.first; this.first.prev = newNode; this.first = newNode; } this.size ++; return newNode; } appendRight(x){ return this.append(x); } appendNode(x){ if (!x instanceof DoubleLinkedListNode) throw new Error("Type mismatch: appendNode expected a DoubleLinkedListNode"); if (x.owner !== null) throw new Error("The node to add should not belong to a list"); x.owner = this; if (this.first === null) { this.first = x; this.last = this.first; } else { this.last.next = x; x.prev = this.last; this.last = x; } this.size++; return x; } appendNodeLeft(x){ if (!x instanceof DoubleLinkedListNode) throw new Error("Type mismatch: appendNode expected a DoubleLinkedListNode"); if (x.owner !== null) throw new Error("The node to add should not belong to a list"); x.owner = this; if (this.first == null){ this.first = x; this.last = this.first; x.prev = null; x.next = null; } else { x.next = this.first; this.first.prev = x; this.first = x; } this.size++; return x; } clear(){ this.size = 0; let n = this.first; while (n !== null) { n.owner = null; n = n.next; } this.first = null; this.last = null; } extend(itr){ if (itr instanceof DoubleLinkedList) { let n = itr.first; while (n !== null){ this.append(n); n = n.next; } } else if (Array.isArray(itr)) { itr.forEach(item => { this.append(item); }); } else { throw new Error("Type mismatch: extend expected a DoubleLinkedList or an array"); } } extendRight(itr){ this.extend(itr); } extendLeft(itr){ if (itr instanceof DoubleLinkedList) { let n = itr.last; while(n !== null) { this.appendLeft(n); n = n.prev; } } else if (Array.isArray(itr)){ for (let i = itr.length - 1; i > -1 ; i --){ let item = itr[i] this.appendLeft(item); } } else { throw new Error("Type mismatch: extendLeft expected a DoubleLinkedList or an array"); } } insert(x, before){ if (!before) { return this.append(x); } else { return this.insertBefore(x, before); } } insertAfter(x, ref){ if (x instanceof DoubleLinkedListNode) x = x.value; if (!ref instanceof DoubleLinkedListNode) throw new Error("Type mismatch: ref should be a DoubleLinkedListNode"); if (ref.owner !== this) throw new Error("ref should belong to the list"); if (ref === this.last) return this.append(x); let newNode = new DoubleLinkedListNode(x); newNode.owner = this; let na = ref.next; newNode.prev = ref; ref.next = newNode; newNode.next = na; na.prev = newNode; this.size ++; return newNode; } insertBefore(x, ref){ if (x instanceof DoubleLinkedListNode) x = x.value; if (!ref instanceof DoubleLinkedListNode) throw new Error("Type mismatch: ref should be a DoubleLinkedListNode"); if (ref.owner !== this) throw new Error("ref should belong to the list"); if (ref === this.first) return this.appendLeft(x); let newNode = new DoubleLinkedListNode(x); newNode.owner = this; let pb = ref.prev; pb.next = newNode; newNode.prev = pb; newNode.next = ref; ref.prev = newNode; this.size ++; return newNode; } insertNode(node, before){ if (!before) { return this.appendNode(node); } else { return this.insertNodeBefore(node, before); } } insertNodeAfter(node, ref){ if (!node instanceof DoubleLinkedListNode) throw new Error("Type mismatch: insertNode expected a DoubleLinkedListNode"); if (node.owner !== null) throw new Error("Node to insert should not belong to a list"); if (ref === this.last) return this.appendNode(node); node.owner = this; let na = ref.next; node.prev = ref; ref.next = node; node.next = na; na.prev = node; this.size ++; return node; } insertNodeBefore(node, ref){ if (!node instanceof DoubleLinkedListNode) throw new Error("Type mismatch: insertNode expected a DoubleLinkedListNode"); if (node.owner !== null) throw new Error("Node to insert should not belong to a list"); if (ref === this.first) return this.appendNodeLeft(node); node.owner = this; let pb = ref.prev; pb.next = node; node.prev = pb; node.next = ref; ref.prev = node; this.size ++; return node; } *iter(){ let n = this.first; let re; while (n !== null) { re = n; n = n.next; yield re.value; } } *iterNodes(){ let n = this.first; let re; while (n !== null) { re = n; n = n.next; yield re; } } *iterValues(){ let n = this.first; let re; while (n !== null) { re = n; n = n.next; yield re.value; } } nodeAt(index){ if (!Number.isInteger(index)) throw new Error("index should be an integer"); if (Math.abs(index) > this.size - 1) throw new Error("index out of range"); if (index === 0) return this.first; if (index === this.size - 1) return this.last; if (index < 0) index = this.size + index; let node, startPos,reverseDir; if (index < this.size / 2){ node = this.first; startPos = 0; reverseDir = 0; } else { node = this.last; startPos = this.size - 1; reverseDir = 1; } if (!reverseDir) { for(let i = startPos; i < index; ++i) { node = node.next; } } else { for(let i = startPos; i > index; --i) { node = node.prev; } } return node; } pop(){ return this.popRight(); } popLeft(){ if (this.size <1) throw new Error("list is empty"); let n = this.first; n.owner = null; let r = n.value; if (n.next !== null) n.next.prev = null; this.first = n.next; this.size --; n.next = null; n.prev = null; return r; } popRight(){ if (this.size <1) throw new Error("list is empty"); let n = this.last; n.owner = null; let r = n.value; if (n.prev !== null ) n.prev.next = null; this.last = n.prev; this.size --; n.next = null; n.prev = null; return r; } remove(node){ if (! node instanceof DoubleLinkedList) throw new Error("Type mismatch: node should be a DoubleLinkedListNode"); if (this.size < 1) throw new Error("the list is empty"); if (node.owner !== this) throw new Error("node should belong to the list"); node.owner = null; if (node === this.first) { return this.popLeft(); } if (node === this.last){ return this.pop(); } let r = node.value; let p = node.prev; let n = node.next; node.prev.next = n; node.next.prev = p; node.prev = null; node.next = null; this.size --; return r; } rotate(n){ if (!Number.isInteger(n)) throw new Error("n should be an integer"); if (n === 0) return; let nMod = Math.abs(n) % this.size; if (nMod === 0) return; let splitIndex; if (n > 0){ splitIndex = this.size - nMod; } else { splitIndex = nMod; } let nl = this.nodeAt(splitIndex - 1); if (nl !== null) { let nf = nl.next; this.first.prev = this.last; this.last.next = this.first; nf.prev = null; nl.next = null; this.first = nf; this.last = nl; } else throw new Error("invalid n"); } toArray(){ let res = []; let n = this.first; while(n !== null){ res.push(n.value); n = n.next; } return res; } _printList(){ let str = "Size:"; str += this.size; str += " {"; let n = this.first; while (n !== null){ str += ` ${n.value} <-->`; n = n.next; } if (this.size > 0) str = str.slice(0, str.length - 4); str += " } "; return str; } }35:T13bd,{ let h= html``; h.append(`let dllist = new DoubleLinkedList(1,2,3);`); let dllist = new DoubleLinkedList(1,2,3); h.append(`// dllist: ${dllist._printList()} \n`); let firstNode = dllist.first; h.append(`let firstNode = dllist.first; // {value: ${firstNode.value}, prev:${firstNode.prev}, next:${firstNode.next}, owner:${firstNode.owner}}\n`); let lastNode = dllist.last; h.append(`let lastNode = dllist.last; // {value: ${lastNode.value}, prev:${lastNode.prev}, next:${lastNode.next}, owner:${lastNode.owner}} \n`) dllist.append(4); h.append(`dllist.append(4); // dllist: ${dllist._printList()} \n`); lastNode = dllist.last; h.append(`lastNode = dllist.last; // {value: ${lastNode.value}, prev:${lastNode.prev}, next:${lastNode.next}, owner:${lastNode.owner}} \n`) dllist.appendLeft(0); h.append(`dllist.appendLeft(0); // dllist: ${dllist._printList()} \n`); firstNode = dllist.first; h.append(`firstNode = dllist.first; // {value: ${firstNode.value}, prev:${firstNode.prev}, next:${firstNode.next}, owner:${firstNode.owner}}\n`); dllist.clear(); h.append(`dllist.clear(); // dllist: ${dllist._printList()}\n`) dllist.extend([1,2,3]); h.append(`dllist.extend([1,2,3]); // dllist: ${dllist._printList()}\n`); let dllist2 = new DoubleLinkedList(); dllist2.extend(dllist); h.append(`let dllist2 = new DoubleLinkedList();\ndllist2.extend(dllist); // dllist2: ${dllist2._printList()}\n`); dllist.appendNode(lastNode); h.append(`dllist.appendNode(lastNode); // dllist: ${dllist._printList()}\n`); let error; try{ dllist2.appendNode(lastNode); } catch (e){ error = e.message; } h.append(`try{\n dllist2.appendNode(lastNode);\n} catch(e) // Error: ${error}\n`); dllist.extendLeft([-2, -1, 0]); h.append(`dllist.extendLeft([-2, -1, 0]); // dllist: ${dllist._printList()}\n`); dllist.insert(5); h.append(`dllist.insert(5);// dllist: ${dllist._printList()}\n`); let node = dllist2.nodeAt(1); h.append(`// dllist2: ${dllist2._printList()}\n`) h.append(`let node = dllist2.nodeAt(1); // {value: ${node.value}, prev:${node.prev}, next:${node.next}, owner:${node.owner}} \n`); dllist2.insert(1.5, node); h.append(`dllist2.insert(1.5, node); // dllist2: ${dllist2._printList()}\n`); dllist2.insertAfter(2.5,node); h.append(`dllist2.insertAfter(2.5,node); // dllist2: ${dllist2._printList()}\n`); node = dllist2.nodeAt(3); h.append(`node = dllist2.nodeAt(3); // {value: ${node.value}, prev:${node.prev}, next:${node.next}, owner:${node.owner}} \n`); dllist2.clear(); let node2 = dllist.nodeAt(4); h.append(`let node2 = dllist.nodeAt(4); // {value: ${node2.value}, prev:${node2.prev}, next:${node2.next}, owner:${node2.owner}} \n`); dllist.insertNodeAfter(node,node2); h.append(`dllist.insertNodeAfter(node,node2); // ${dllist._printList()}\n`); node = new DoubleLinkedListNode(1.5); h.append(`node = new DoubleLinkedListNode(1.5); // {value:${node.value}, prev:${node.prev}, next:${node.next}, owner:${node.owner}} \n`) dllist.insertNode(node,node2); h.append(`dllist.insertNode(node,node2); // ${dllist._printList()}\n`); let nodeArray = []; h.append(`let nodeArray = [];\n`); for(const n of dllist.iterNodes()){ nodeArray.push(n); } nodeArray; h.append(`for(const n of dllist.iterNodes()){ nodeArray.push(n); } nodeArray.map(n => n.value); // [${nodeArray.map(n => n.value).join(", ")}]\n`); let valueArray = Array.from(dllist.iter()); h.append(`let valueArray = Array.from(dllist.iter()); // [${valueArray.join(", ")}]\n`); dllist.pop(); h.append(`dllist.pop(); // ${dllist._printList()}\n`); dllist.popLeft(); h.append(`dllist.popLeft(); // ${dllist._printList()}\n`); node = dllist.nodeAt(3); h.append(`node = dllist.nodeAt(3); // {value:${node.value}, prev:${node.prev}, next:${node.next}, owner:${node.owner}}\n`); dllist.remove(node); h.append(`dllist.remove(node); // dllist: ${dllist._printList()}\n`); try { dllist2.remove(node); } catch(e){ error = e.message; } h.append(`try { dllist2.remove(node); } catch(e){ // ${error} } `); dllist2 = new DoubleLinkedList(0,1,2); try{ dllist2.remove(node); } catch(e){ error = e.message; } h.append(`dllist2 = new DoubleLinkedList(0,1,2); try{ dllist2.remove(node); } catch(e){ // ${error} } `); valueArray = dllist.toArray(); // h.append(`//${dllist._printList()}\n`) h.append(`valueArray = dllist.toArray(); // [${valueArray.join(", ")}]\n`); dllist.remove(dllist.first); h.append(`dllist.remove(dllist.first); // ${dllist._printList()}\n`); dllist.remove(dllist.last); h.append(`dllist.remove(dllist.last); // ${dllist._printList()}\n`); dllist.rotate(-2); h.append(`dllist.rotate(-2); // ${dllist._printList()}\n`); dllist.rotate(2); h.append(`dllist.rotate(2); // ${dllist._printList()}\n`); dllist.rotate(9); h.append(`dllist.rotate(9); // ${dllist._printList()}\n`); hljs.highlightBlock(h); return h; }36:[] 31:{"id":"fcff8dd4ace0326a","slug":"dllist","title":"Double Linked List","thumbnail":"b4564ce0cf1bcc77f66bacf3679cb30402ee14c4796d24e73b211943d9687399","access_level":"public","create_time":"$D2023-11-14T16:24:05.927Z","update_time":"$D2023-11-20T16:21:36.363Z","view_time":null,"first_public_time":"$D2023-11-14T16:24:05.927Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"b2e9840be7b1b607","login":"real-john-cheung","name":"John C","avatar_url":"https://avatars-next.observableusercontent.com/1d9ef6121a0bbd1a75fab479f9891fe1d78cc65f76c394585ae1a7dad0d3abf6","tier":"starter_2024"},"version":286,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"e8e99acdbe3aebfb","login":"real-john-cheung","name":"John C","avatar_url":"https://avatars-next.observableusercontent.com/1d9ef6121a0bbd1a75fab479f9891fe1d78cc65f76c394585ae1a7dad0d3abf6","tier":null}],"members":[{"type":"individual","id":"e8e99acdbe3aebfb","login":"real-john-cheung","name":"John C","avatar_url":"https://avatars-next.observableusercontent.com/1d9ef6121a0bbd1a75fab479f9891fe1d78cc65f76c394585ae1a7dad0d3abf6","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"aac27ce630a2ebd4","slug":"posts","title":"Posts","owner":{"id":"b2e9840be7b1b607","login":"real-john-cheung","name":"John C"}},"type":"notebook","body":{"title":"Double Linked List","cells":[{"id":0,"value":"$33","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":57,"value":"class DoubleLinkedListNode{\n constructor(v){\n this.value = v;\n this.next = null;\n this.prev = null;\n this.owner = null;\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":88,"value":"

\n\nTest & Example","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":91,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":238,"value":"

","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":139,"value":"hljs = window.hljs || (await require('@observablehq/highlight.js'))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W36","stdlib":"1","titling":"auto"}} 32:"$31:body"