# JavaScript Data Structures: Linked lists

> Learn how to implement a linked list in JavaScript from scratch, building Item and LinkedList classes with append, size, find and insert methods.

Author: [Flavio Copes](https://flaviocopes.com/about/) | Published: 2020-11-09 | Topics: [JavaScript](https://flaviocopes.com/tags/js/) | Canonical: https://flaviocopes.com/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](https://flaviocopes.com/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:

```js
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:

```js
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:

```js
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:

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

```js
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:

```js
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:

```js
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.