Skip to content

Instantly share code, notes, and snippets.

@bdotsamir
Last active July 8, 2021 20:56
Show Gist options
  • Save bdotsamir/9b2c591732405887f58414a940449afa to your computer and use it in GitHub Desktop.
Save bdotsamir/9b2c591732405887f58414a940449afa to your computer and use it in GitHub Desktop.
probably not the best js implementation of a doubly linked list
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;
}
}
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; }
}
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()
@bdotsamir
Copy link
Author

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment