Last active
July 8, 2021 20:56
-
-
Save bdotsamir/9b2c591732405887f58414a940449afa to your computer and use it in GitHub Desktop.
probably not the best js implementation of a doubly linked list
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const DLLNode = require("./DLLNode"); | |
module.exports = class DLinkedList { | |
constructor(nodes) { | |
if(!Array.isArray(nodes)) throw new TypeError(`Expected type Array<DLLNode>, got ${typeof nodes} instead`); | |
this.head = null; | |
this.tail = null; | |
this.list = []; | |
for(let i = 0; i < nodes.length; i++) { | |
if(!(nodes[i] instanceof DLLNode)) throw new TypeError(`Expected type DLLNode at nodes[${i}], got ${typeof nodes[i]} instead`); | |
if(i === 0) { // first node | |
nodes[i].setChild(nodes[i + 1]); | |
this.head = nodes[i]; | |
this.list.push(nodes[i]); | |
continue; // break out of this loop and go to the next since this is all we can do | |
} | |
if(i === nodes.length - 1) { // last node | |
nodes[i].setParent(nodes[i - 1]); | |
this.tail = nodes[i]; | |
this.list.push(nodes[i]); | |
continue; // break out of this loop and go to the next since this is all we can do | |
} | |
nodes[i].setChild(nodes[i + 1]); | |
nodes[i].setParent(nodes[i - 1]); | |
this.list.push(nodes[i]); | |
} | |
} | |
getHead() { return this.head; } | |
getTail() { return this.tail; } | |
getList() { return this.list; } | |
push(newNode) { | |
if(!(newNode instanceof DLLNode)) throw new TypeError(`Expected type DLLNode, got ${typeof newNode} instead`); | |
this.getTail().setChild(newNode); | |
newNode.setParent(this.getTail()); | |
this.tail = newNode; | |
return newNode; | |
} | |
unshift(newNode) { | |
if(!(newNode instanceof DLLNode)) throw new TypeError(`Expected type DLLNode, got ${typeof newNode} instead`); | |
this.getHead().setParent(newNode); | |
newNode.setChild(this.getHead()); | |
this.head = newNode; | |
return newNode; | |
} | |
insert(index, newNode) { | |
if(!(newNode instanceof DLLNode)) throw new TypeError(`Expected type DLLNode, got ${typeof newNode} instead`); | |
if(typeof index !== 'number') throw new TypeError(`Expected type number, got ${typeof index} instead`); | |
if(index === 0) return this.unshift(newNode); | |
if(index === this.getList().length - 1) return this.push(newNode); | |
const parentNode = this.getList()[index - 1]; | |
const childNode = this.getList()[index + 1]; | |
parentNode.setChild(newNode); | |
childNode.setParent(newNode); | |
newNode.setParent(parentNode); | |
newNode.setChild(childNode); | |
return newNode; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
module.exports = class DLLNode { | |
constructor(data) { | |
this.data = data ?? null; | |
this.parent = null; | |
this.child = null; | |
} | |
store(newData) { | |
this.data = newData; | |
return newData; | |
} | |
getData() { return this.data; } | |
setChild(newChild) { | |
if(!(newChild instanceof DLLNode)) throw new TypeError(`Expected type DLLNode, got ${typeof newChild} instead`); | |
this.child = newChild; | |
return newChild; | |
} | |
setParent(newParent) { | |
if(!(newParent instanceof DLLNode)) throw new Error(`Expected type DLLNode, got ${typeof newParent} instead`); | |
this.parent = newParent; | |
return newParent; | |
} | |
getChild() { return this.child; } | |
getParent() { return this.parent; } | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const DLinkedList = require('./DLinkedList'); | |
const DLLNode = require('./DLLNode'); | |
const node1 = new DLLNode('01'); | |
const node2 = new DLLNode('02'); | |
const node3 = new DLLNode('03'); | |
const node4 = new DLLNode('04'); | |
const list = new DLinkedList([node1, node2, node3, node4]); | |
console.log('node1 data', node1.getData()); | |
console.log('node2 data', node2.getData()); | |
console.log('node3 data', node3.getData()); | |
console.log('node4 data', node4.getData()); | |
console.log('list list', list.getList()); | |
console.log(' '); | |
console.log('list head', list.getHead()); | |
console.log('list tail', list.getTail()); | |
console.log(' '); | |
console.log('list head + 1', list.getHead().getChild()); | |
console.log('list head + 2', list.getHead().getChild().getChild()); | |
console.log('list head + 2 - 1', list.getHead().getChild().getChild().getParent()); | |
// untested: DLinkedList#push(), DLinkedList#unshift(), DLinkedList#insert() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
For a more practical example (and maybe a better implementation?) check out a project I'm working on that I used code from here for: https://gitlab.com/akii0008/sobi