Linked Lists

Linked list: nodes chained through next pointers. Prepend is O(1), while append and lookup require walking the chain.

A linked list is a chain of nodes. Each node holds a value and a reference, or pointer, to the next node. The list has no array index, so most operations work by walking from node to node.

A minimal singly linked list needs a Node class and a LinkedList class. prepend adds to the front in O(1). append walks to the last node and attaches there in O(n).

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
 
class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }
 
  prepend(value) {
    const node = new Node(value);
    node.next = this.head;
    this.head = node;
    this.size++;
  }
 
  append(value) {
    const node = new Node(value);
    if (!this.head) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next; // walk to the last node
      }
      current.next = node;
    }
    this.size++;
  }
 
}
 
const list = new LinkedList();
list.prepend("b");
list.prepend("a");
list.append("c");
console.log(list.size); // 3

In production

In JavaScript application code, arrays are usually the better default. Reach for a linked list only when constant-time insertion or removal is the real bottleneck and you already have a reference to the node.

Enjoyed this? Get more software craft delivered to your inbox.