Skip to content

Instantly share code, notes, and snippets.

@indifferentghost
Created June 1, 2020 21:52
Show Gist options
  • Save indifferentghost/084d46c718ed0e5fccca28ead741a7e5 to your computer and use it in GitHub Desktop.
Save indifferentghost/084d46c718ed0e5fccca28ead741a7e5 to your computer and use it in GitHub Desktop.
A pretty awkward linked list
const Node = (function () {
const _value = new WeakMap();
function _Node(value) {
_value.set(this, value);
this.next = null;
this.prev = null;
}
_Node.prototype.getValue = function getValue() {
return _value.get(this);
};
return _Node;
})();
const LinkedList = (function () {
const _constructor = new WeakMap();
function _LinkedList() {
_constructor.set(this, {
head: null,
tail: null,
});
}
function _loop(callback) {
(function recursive(currentNode) {
if (currentNode === null) return;
callback(currentNode);
recursive(currentNode.next);
})(_constructor.get(this).head);
}
function _loopRev(callback) {
(function recursive(currentNode) {
if (currentNode === null) return;
callback(currentNode);
recursive(currentNode.prev);
})(_constructor.get(this).tail);
}
function push(...nodes) {
for (let node of nodes) {
const constructor = _constructor.get(this);
if (!constructor.head) {
_constructor.set(this, { ...constructor, head: node, tail: node });
continue;
}
constructor.tail.next = node;
node.prev = constructor.tail;
_constructor.set(this, { ...constructor, tail: node });
}
}
function splice(startNode, count, ...nodes) {
let currentNode = startNode;
let prevNode = startNode.prev;
for (let i = 0; i < count && currentNode !== null; i++) {
let temp = currentNode.next;
this.remove(currentNode);
currentNode = temp;
}
if (nodes.length) {
currentNode = prevNode;
for (const node of nodes) {
const temp = currentNode.next;
currentNode.next = node;
node.prev = currentNode;
node.next = temp;
temp.prev = node;
currentNode = node;
}
}
}
function find(value) {
return (function recursive(currentNode) {
if (currentNode === null) return false;
if (currentNode.getValue() === value) return currentNode;
return recursive(currentNode.next);
})(_constructor.get(this).head);
}
function remove(node) {
const constructor = _constructor.get(this);
if (node === constructor.tail) {
node.prev.next = null;
_constructor.set(this, { ...constructor, tail: node.prev });
} else if (node === constructor.head) {
node.next.prev = null;
_constructor.set(this, { ...constructor, head: node.next });
} else {
node.prev.next = node.next;
node.next.prev = node.prev;
}
}
function filter(value) {
this._loop((node) => {
if (node.getValue() === value) {
this.remove(node);
}
});
}
function print() {
let str = "";
this._loopRev((node) => {
str += `{${node.getValue()}}`;
if (node.prev !== null) {
str += " - ";
}
});
console.log(str.trim());
}
_LinkedList.prototype = {
push,
find,
filter,
print,
splice,
remove,
_loop,
_loopRev,
};
return _LinkedList;
})();
const a = new Node("a");
const b = new Node("b");
const c = new Node("c");
const d = new Node("d");
const c2 = new Node("c");
const ll = new LinkedList();
ll.push(a, b, c, d, c2);
ll.print();
console.log(ll.find("b") == b);
ll.filter("c");
ll.print();
ll.push(c, c2);
ll.print();
ll.splice(b, 2, d, b);
ll.print();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment