JavaScript linked lists and iterators

Before you start

JavaScript classes and generators.

Build a singly linked list class that can be looped over with for...of.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

A class can make itself iterable by defining a generator method named [Symbol.iterator]. A generator function, written with an asterisk, produces values one at a time with yield. Then for...of, the spread operator, and Array.from all work on the list. The reverse method relinks the nodes in a single pass.

Code example

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);

Output

1 -> 2 -> 3 -> 4 (4 nodes)
4 -> 3 -> 2 -> 1
sum 10

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1class Node {

2 constructor(value, next = null) {

3 this.value = value;

4 this.next = next;

5 }

6}

8class LinkedList {

9 constructor() {

10 this.head = null;

11 this.length = 0;

12 }

14 addFirst(value) {

15 this.head = new Node(value, this.head);

16 this.length++;

17 }

19 addLast(value) {

20 const node = new Node(value);

21 if (this.head === null) {

22 this.head = node;

23 } else {

24 let current = this.head;

25 while (current.next !== null) {

26 current = current.next;

27 }

28 current.next = node;

29 }

30 this.length++;

31 }

33 reverse() {

34 let previous = null;

35 let current = this.head;

36 while (current !== null) {

37 const next = current.next;

38 current.next = previous;

39 previous = current;

40 current = next;

41 }

42 this.head = previous;

43 }

45 *[Symbol.iterator]() {

46 for (let node = this.head; node !== null; node = node.next) {

47 yield node.value;

48 }

49 }

50}

52const list = new LinkedList();

53list.addFirst(2);

54list.addFirst(1);

55list.addLast(3);

56list.addLast(4);

57console.log([...list].join(" -> "), "(" + list.length + " nodes)");

58list.reverse();

59console.log([...list].join(" -> "));

60let sum = 0;

61for (const value of list) {

62 sum += value;

63}

64console.log("sum " + sum);

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
The new node points to the old head and becomes the head: O(1).	`—`	—
addLast walks to the end: O(n).	`—`	—
A generator method that makes the list iterable.	`—`	—
Spread uses the iterator to turn the list into an array.	`—`	1 -> 2 -> 3 -> 4 (4 nodes)
Reversal points each node backwards.	`—`	1 -> 2 -> 3 -> 4 (4 nodes)
The same values in the opposite order.	`—`	1 -> 2 -> 3 -> 4 (4 nodes) 4 -> 3 -> 2 -> 1
for...of also works with the iterator.	`—`	1 -> 2 -> 3 -> 4 (4 nodes) 4 -> 3 -> 2 -> 1 sum 10

Behind the scenes

How JavaScript processes this code

A JavaScript engine parses and runs the source. A function body runs when the function is called. console.log writes to the console.

Cost and common mistakes

addFirst O(1), addLast O(n), reverse O(n), iteration O(n).

Save current.next before changing it in reverse, or the rest of the list is lost.
Keeping a tail reference makes addLast O(1) but requires care when the list becomes empty.
Arrays have better cache behaviour and are the default choice. Use a list when you need O(1) insertion in the middle given a node.

Try it yourself

How would you find the middle node in one pass?

Reveal answer and reasoning

Walk with two pointers: a slow one moving one node at a time and a fast one moving two. When the fast one reaches the end, the slow one is at the middle.