JavaScript Data Structures: Linked lists

Linked lists are one of the most important data structures you can learn.

In a linked list, each item contains a reference to the item that follows it.

We can start from the beginning of the list, the head, and iterate through all the items of the list, until we reach the end (the tail).

Compared to an array, items do not sit next to each other in the actual memory (in low-level programming languages) or don’t have an index we can use to randomly access an item of the array.

We can’t reference an item in the middle of the list, without starting from the beginning, as we don’t know how to reference it.

JavaScript does not have an implementation of linked lists, so we will create one now.

First we create the Item class that will be the contained for each item in the list:

class Item {
  next = null
  value = null
  constructor(value) {
    this.value = value
  }
}

We have a pointer to the next item in the list, and the value.

Then we defined a LinkedList class that will host 2 private values: head and tail.

We define an append() method to add an item to the list. If it’s the first item we add, the item is both the head and the tail of the list. Otherwise, we create the item and we assign it to the next property of the tail item:

class LinkedList {
  #head = null
  #tail = null
  append = (value) => {
    const item = new Item(value)
    if (!this.#head) {
      this.#head = item
      this.#tail = item
      return
    }
    this.#tail.next = item
    this.#tail = item
  }
  size = () => {
    let count = 1
    let item = this.#head
    if (!item) return 0
    while ((item = item.next)) {
      count++
    }
    return count
  }
}

This is how we can use it:

const list = new LinkedList()
list.append(1)
list.append(2)
list.append(3)

We can add a size() method to return the size of the list:

class LinkedList {
  //...
  size = () => {
    let count = 1
    let item = this.#head
    if (!item) return 0
    while ((item = item.next)) {
      count++
    }
    return count
  }
}

const list = new LinkedList()
list.size() //0
list.append(1)
list.size() //1
list.append(2)
list.append(3)
list.size() //3

How can we find an item in the list, by value? Let’s implement a method to do so:

class LinkedList {
  //...
  find = (value) => {
    let count = 1
    let item = this.#head
    if (!item) return null
    while ((item = item.next)) {
      if (item.value === value) {
        return item
      }
    }
    return null
  }
}

const list = new LinkedList()
list.append(1)
list.append(2)
list.append(3)
const item = list.find(2) //item.value === 2

What if we want to insert an item to the linked list? We already have append() to insert the item at the end of the list. Let’s implement a way to insert the item at a specific position:

class LinkedList {
  //...
  insert = (index, value) => {
    //check for out-of-bounds values
    if (index < 0 || index > this.size()) return

    const node = new Item(value)
    let current = this.#head
    let previous

    if (index === 0) {
      //first position
      node.next = current
      this.#head = node
    } else {
      let i = 0
      while (i++ < index) {
        previous = current
        current = current.next
      }
      node.next = current
      previous.next = node
    }
  }
}

const list = new LinkedList()
list.append(1)
list.append(2)
list.append(3)
list.insert(2, 'a')
list.size() //4

Another type of linked list is the double linked list, where each item contains a link to the previous element, too.