JavaScript linked lists and iterators
A linked list stores each value in a node that points to the next one. Adding at the front is O(1) and needs no shifting, but finding the n-th item means following n links. JavaScript arrays are usually faster in practice, but understanding lists helps with queues, undo chains, and many interview problems.
JavaScript
class Node {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
this.length = 0;
}
addFirst(value) {
this.head = new Node(value, this.head);
this.length++;
}
addLast(value) {
const node = new Node(value);
if (this.head === null) {
this.head = node;
} else {
let current = this.head;
while (current.next !== null) {
current = current.next;
}
current.next = node;
}
this.length++;
}
reverse() {
let previous = null;
let current = this.head;
while (current !== null) {
const next = current.next;
current.next = previous;
previous = current;
current = next;
}
this.head = previous;
}
*[Symbol.iterator]() {
for (let node = this.head; node !== null; node = node.next) {
yield node.value;
}
}
}
const list = new LinkedList();
list.addFirst(2);
list.addFirst(1);
list.addLast(3);
list.addLast(4);
console.log([...list].join(" -> "), "(" + list.length + " nodes)");
list.reverse();
console.log([...list].join(" -> "));
let sum = 0;
for (const value of list) {
sum += value;
}
console.log("sum " + sum);