Skip to content

Instantly share code, notes, and snippets.

@alpox
Last active June 12, 2022 11:44
Show Gist options
  • Save alpox/ae8e702f727b796a385557dc32f93e82 to your computer and use it in GitHub Desktop.
Save alpox/ae8e702f727b796a385557dc32f93e82 to your computer and use it in GitHub Desktop.
Immutable Linked List with Pipelining
function forEachInList(list, fn) {
if (!list) return null;
let current = list;
let i = 0;
while(true) {
fn(current.data, i, current, list);
if (!current.next) break;
current = current.next;
i++;
}
}
function reduceList(list, fn, init) {
let current = init;
forEachInList(list, (data, i, node) => {
current = fn(current, data, node, i, list);
})
return current;
}
function mapList(list, fn) {
const head = {
data: fn(list.data, 0, list, list),
next: null
};
reduceList(list.next, (buildNode, data, node, i, list) => {
buildNode.next = {
data: fn(data, i + 1, node, list),
next: null,
}
return buildNode.next;
},
head);
return head;
}
function appendToList(list, data) {
const head = mapList(list, (d) => d);
let current = head;
while(current.next && (current = current.next));
current.next = {
data,
next: null,
}
return head;
}
function prependToList(list, data) {
const head = mapList(list, (d) => d);
return {
data,
next: head
};
}
function findInList(list, data) {
let current = list;
while(current.next) {
if (current.data === data) return current;
current = current.next;
}
return null;
}
function insertAfterInList(list, targetData, data) {
const head = mapList(list, (d) => d);
const node = findInList(head, targetData);
const newNode = { data, next: node.next };
node.next = newNode;
return head;
}
function createLinkedList(...data) {
const [butLast, last] = [data.slice(0, -1), data.at(-1)];
const tail = {
data: last,
next: null,
};
return butLast.reverse().reduce(prependToList, tail);
}
const list = createLinkedList(1, 2, 3)
|> appendToList(%, 1)
|> mapList(%, data => data + 2)
|> reduceList(%, (a, b) => a + b, 0);
console.log(list);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment