Singly Linked List Template
Linked lists rarely beat arrays in production JavaScript, but they are the single most-asked interview data structure and the conceptual foundation for skip lists, LRU caches, and queue implementations. This snippet covers the Node + List skeleton with O(1) prepend, an O(n) traversal helper, and the in-place reverse that shows up in nearly every interview round.
1,134 views
16
class ListNode {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
class LinkedList {
constructor() { this.head = null; this.size = 0; }
prepend(value) {
this.head = new ListNode(value, this.head);
this.size++;
return this;
}
toArray() {
const out = [];
for (let n = this.head; n !== null; n = n.next) out.push(n.value);
return out;
}
}
const list = new LinkedList();
list.prepend(3).prepend(2).prepend(1);
console.log(list.toArray()); // [1, 2, 3]
console.log(list.size); // 3A singly linked list is a chain of Node { value, next } cells where the list itself stores only a head pointer. Prepending in O(1) is the linked list's headline win over arrays: build a new node whose next points at the current head, then reseat head. The toArray helper makes the list inspectable in tests and the chained prepend mirrors immutable list APIs from functional languages. Storing size is optional but pays for itself the first time a caller asks for length.
class LinkedList2 {
constructor() { this.head = null; this.tail = null; this.size = 0; }
append(value) {
const node = new ListNode(value);
if (this.tail === null) { this.head = node; this.tail = node; }
else { this.tail.next = node; this.tail = node; }
this.size++;
return this;
}
remove(value) {
let prev = null;
for (let n = this.head; n !== null; n = n.next) {
if (n.value === value) {
if (prev) prev.next = n.next; else this.head = n.next;
if (n === this.tail) this.tail = prev;
this.size--;
return true;
}
prev = n;
}
return false;
}
toArray() { const out = []; for (let n = this.head; n !== null; n = n.next) out.push(n.value); return out; }
}
const l2 = new LinkedList2();
l2.append(1).append(2).append(3);
console.log(l2.toArray()); // [1, 2, 3]
l2.remove(2);
console.log(l2.toArray()); // [1, 3]Adding a tail pointer keeps append O(1) without sacrificing the O(1) prepend. The remove(value) walk is the place most interview candidates trip: deleting the head requires reseating this.head, deleting the tail requires reseating this.tail, and deleting an interior node requires the predecessor's next to skip the doomed cell. Tracking prev as we walk makes all three cases explicit. Returning a boolean lets the caller distinguish 'removed' from 'not found' without throwing.
function reverseList(head) {
let prev = null;
let curr = head;
while (curr !== null) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
const head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
const reversed = reverseList(head);
const out = [];
for (let n = reversed; n !== null; n = n.next) out.push(n.value);
console.log(out); // [4, 3, 2, 1]Reversing a linked list in place is the canonical pointer-juggling exercise. The pattern keeps three pointers: prev (the new head being built), curr (the node being moved), and next (saved before we overwrite curr.next). Each iteration flips one link without losing track of the rest of the list. The runtime is O(n) and the extra space is O(1), strictly better than building a reversed copy. Memorise this exact body; it shows up in 'reverse linked list', 'reverse in groups of K', and the second half of palindrome-list.