Created
June 1, 2020 21:52
-
-
Save indifferentghost/084d46c718ed0e5fccca28ead741a7e5 to your computer and use it in GitHub Desktop.
A pretty awkward 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 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