Computer science in JavaScript: Linked list

  1. What is a linked list?
  2. Why use a linked list?
  3. The design of a linked list
  4. The LinkedList class
    1. Adding new data to the list
  5. Retrieving data from the list
  6. Removing data from a linked list
  7. Making the list iterable
  8. Using the class

What is a linked list?

A linked list is a data structure that stores multiple values in a linear fashion. Each value in a linked list is contained in its own node, an object that contains the data along with a link to the next node in the list. The link is a pointer to another node object or null if there is no next node. If each node has just one pointer to another node (most frequently called next) then the list is considered a singly linked list (or just linked list) whereas if each node has two links (usually previous and next) then it is considered a doubly linked list. In this post, I am focusing on singly linked lists.

Why use a linked list?

The primary benefit of linked lists is that they can contain an arbitrary number of values while using only the amount of memory necessary for those values.

Though originally intended for better memory management, linked lists also became popular when developers didn’t know how many items an array would ultimately contain. It was much easier to use a linked list and add values as necessary than it was to accurately guess the maximum number of values an array might contain. As such, linked lists are often used as the foundation for built-in data structures in various programming languages.

The built-in JavaScript Array type is not implemented as a linked list, though its size is dynamic and is always the best option to start with. You might go your entire career without needing to use a linked list in JavaScript but linked lists are still a good way to learn about creating your own data structures.

The design of a linked list

The most important part of a linked list is its node structure. Each node must contain some data and a pointer to the next node in the list. Here is a simple representation in JavaScript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class LinkedListNode {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

const node12 = new LinkedListNode(12);
const node99 = new LinkedListNode(99);
const node37 = new LinkedListNode(37);

node12.next = node99;
node12.next.next = node37;

console.assert(node12.data === 12, 'node12 has the value of 12');
console.assert(node99.data === 99, 'node99 has the value of 99');
console.assert(node37.data === 37, 'node37 has the value of 37');

console.assert(node12.next.data === 99, 'The next node of node12 has the value of 99');
console.assert(node99.next.data === 37, 'The next node of node99 has the value of 37');

The following image shows the resulting data structure.

The structure of a linked list allows you to traverse all of the data by following the next pointer on each node. Here is a simple example of how to traverse a linked list and print each value out to the console:

1
2
3
4
5
6
let current = node12;

while (current) {
  console.log('current:', current.data);
  current = current.next;
}

The LinkedList class

It’s more customary to create a class to encapsulate this functionality.

1
2
3
4
5
6
7
const head = Symbol("head");

class LinkedList {
  constructor() {
    this[head] = null;
  }
}

Adding new data to the list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const head = Symbol('head');

class LinkedList {
  constructor() {
    // A symbol makes it clear that this property is not intended
    // to be modified outside the class
    this[head] = null;
  }
  add(data) {
    const newNode = new LinkedListNode(data);
    if (this[head]) {
      // Find the property node to set its next property to.
      let current = this[head];
      while (current.next !== null) {
        current = current.next;
      }
      // assign the node into the `next` pointer
      current.next = newNode;
    } else {
      // no items in the list yet
      // just set the head to the new node
      this[head] = newNode;
    }
  }
}

const list1 = new LinkedList();
console.assert(list1[head] === null, 'The head node is empty for an empty list');
list1.add(5);
console.assert(list1[head].data === 5, 'The head node has the value of 5');
list1.add(6);
console.assert(list1[head].next.data === 6, 'The next node has the value of 6');

Retrieving data from the list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class LinkedList {

  // other methods hidden for clarity

  get(index) {
    // Returns undefind if `index` is a negative value
    if (index < 0) return undefined;
    let i = 0;
    let current = this[head];
    // traverse the list until reach either the end or the index
    while (current !== null && i < index) {
      i++;
      current = current.next;
    }
    return current !== null ? current.data : undefined;
  }
}

Removing data from a linked list

Removing data from a linked list is a little bit tricky because you need to ensure that all next pointers remain valid after a node is removed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class LinkedList {
  // other methods hidden for clarity
  remove(index) {
    // special cases: empty list or invalid `index`
    if ((this[head] === null) || (index < 0)) {
      throw new RangeError(`Index ${index} does not exist in the list.`);
    }

    // special case: removing the first node
    if (index === 0) {
      // temporary store the data from the node
      const data = this[head].data;

      // just replace the head with the next node in the list
      this[head] = this[head].next;

      // return the data at the previous head of the list
      return data;
    }

    // pointer use to traverse the list
    let current = this[head];

    // keeps track of the node before current in the loop
    let previous = null;

    // used to track how deep into the list you are
    let i = 0;

    // same loops as in `get()`
    while ((current !== null) && (i < index)) {
      // save the value of current
      previous = current;
      // traverse to the next node
      current = current.next;
      // increment the count
      i++;
    }

    // if node was found, remove it
    if (current !== null) {
      // skip over the node to remove
      previous.next = current.next;
      // return the value that was just removed from the list
      return current.data;
    }

    // if node wasn't found, throw an error
    throw new RangeError(`Index ${index} does not exist in the list.`);
  }
}

Making the list iterable

In order to be used with the JavaScript for-of loop and array destructuring, collections of data must be iterables. The built-in JavaScript collections such as Array and Set are iterable by default, and you can make your own classes iterable by specifying a Symbol.iterator generator method on the class. I prefer to first implement a values() generator method (to match the method found on built-in collection classes) and then have Symbol.iterator call values() directly.

The values() method need only do a basic traversal of the list and yield the data that each node contains:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class LinkedList {

    // other methods hidden for clarity

    *values(){

        let current = this[head];

        while (current !== null) {
            yield current.data;
            current = current.next;
        }
    }

    [Symbol.iterator]() {
        return this.values();
    }

}

The values() method is marked with an asterisk (*) to indicate that it’s a generator method. The method traverses the list, using yield to return each piece of data it encounters. (Note that the Symbol.iterator method isn’t marked as a generator because it is returning an iterator from the values() generator method.)

Using the class

Once complete, you can use the linked list implementation like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const list = new LinkedList();
list.add("red");
list.add("orange");
list.add("yellow");

// get the second item in the list
console.log(list.get(1));       // "orange"

// print out all items
for (const color of list) {
    console.log(color);
}

// remove the second item in the list
console.log(list.remove(1));    // "orange"

// get the new first item in the list
console.log(list.get(1));       // "yellow"

// convert to an array
const array1 = [...list.values()];
const array2 = [...list];

This basic implementation of a linked list can be rounded out with a size property to count the number of nodes in the list, and other familiar methods such as indexOf(). The full source code is available on GitHub at my Computer Science in JavaScript project.

Source:

https://humanwhocodes.com/blog/2019/01/computer-science-in-javascript-linked-list/