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 {
#tail = null
append = (value) => {
const item = new Item(value)
this.#tail = item
return
}
this.#tail.next = item
this.#tail = item
}
size = () => {
let count = 1
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
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
if (!item) return null
while ((item = item.next)) {
if (item.value === value) {
return item
}
}
return null
}
}

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 previous

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

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.