Skip to content

Instantly share code, notes, and snippets.

@SHND
Last active December 27, 2020 01:44
Show Gist options
  • Save SHND/93d54c8d71817217b6a0c113f39dba23 to your computer and use it in GitHub Desktop.
Save SHND/93d54c8d71817217b6a0c113f39dba23 to your computer and use it in GitHub Desktop.
Simple double LinkedList JavaScript implementation
/**
* LinkedList Node Class
*/
function Node(tree, value, next = null, prev = null) {
this.tree = tree;
this.value = value;
this.next = next;
this.prev = prev;
}
Node.prototype.removeSelf = function() {
this.tree.removeNode(this);
}
Node.prototype.insertNext = function(node) {
this.tree.insertNext(this, node);
}
Node.prototype.insertPrev = function(node) {
this.tree.insertPrev(this, node);
}
/**
* LinkedList Class
*/
function LinkedList() {
this.head = null; // no next
this.tail = null; // no prev
}
LinkedList.prototype.createNode = function(value) {
return new Node(this, value);
}
LinkedList.prototype.addHead = function(node) {
if (!this.head) {
node.next = null;
node.prev = null;
this.head = this.tail = node;
return node;
}
node.next = null;
node.prev = this.head;
this.head.next = node;
this.head = node;
return node;
}
LinkedList.prototype.addTail = function(node) {
if (!this.head) {
this.next = null;
this.prev = null;
this.head = this.tail = node;
return node;
}
node.next = this.tail;
node.prev = null;
this.tail.prev = node;
this.tail = node;
return node;
}
LinkedList.prototype.insertNext = function(node, addingNode) {
addingNode.prev = node;
addingNode.next = node.next;
if (node === this.head) {
this.head = addingNode;
} else {
node.next.prev = addingNode;
}
node.next = addingNode;
}
LinkedList.prototype.insertPrev = function(node, addingNode) {
addingNode.next = node;
addingNode.prev = node.prev;
if (node === this.tail) {
this.tail = addingNode;
} else {
node.prev.next = addingNode;
}
node.prev = addingNode;
}
LinkedList.prototype.removeNode = function(node) {
if (!this.head) {
throw Error('Node not found to be removed');
}
const nextNode = node.next;
const prevNode = node.prev;
if (nextNode) {
nextNode.prev = prevNode;
} else {
this.head = prevNode;
}
if (prevNode) {
prevNode.next = nextNode;
} else {
this.tail = nextNode
}
}
LinkedList.prototype.toString = function() {
return [...this].map(node => node.value).join(' -> ')
}
LinkedList.prototype[Symbol.iterator] = function* () {
let current = this.tail;
while (current) {
yield current;
current = current.next;
}
}
const list = new LinkedList();
const node1 = list.createNode(1);
const node2 = list.createNode(2);
const node3 = list.createNode(3);
list.addHead(node1);
list.addHead(node2);
list.addHead(node3);
/*
tail head
1 -> 2 -> 3
prev-> node-> next
*/
@SHND
Copy link
Author

SHND commented Dec 27, 2020

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