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.
→ I wrote 17 books to help you become a better developer, download them all at $0 cost by joining my newsletter
→ JOIN MY CODING BOOTCAMP, an amazing cohort course that will be a huge step up in your coding career - covering React, Next.js - next edition February 2025