An Introduction to the Linked List Data Structure in JavaScript

Everything about the linked list data structure in JavaScript.

Linked lists are probably the simplest and most common lists out there. It is so powerful that it can be used to implement other lists like queue, stack, associative arrays, etc. It allows for easy insertion and removal of items and it is for sure one of the data structures worth studying before diving into tree or graph data structures.

Video Version of This Article

This post is an improved and more detailed article version of the Linked List Data Structure Series on Youtube that you can check if you prefer videos.

Watch Videos

What is a Linked List?

A linked list is a linear data structure. It is a collection of elements whose order is not given by their physical placement in memory. Each element points to the other to indicate what element comes next and or before and together they form a sequence of data.

It can be used to implement other data structures which is something you can see by checking the Queue and Stack data structure article in this series. It can be super-efficient on insertion and removal of items since you don’t have to change the list to do so since all you got to do is change a few element pointers to remove or add a new element. We will see how later.

Some of its disadvantages are in the memory they use. All elements must also include the pointer information to indicate which element comes next or before along with the data. There is also no random access. That means if I want to read the 5th element you must start from the start — the head — and traverse to the 5th element to read it.

If it is a single-linked list, you can only traverse in one direction. By making it doubly you need more memory to store the back pointer and that gives you the ability to traverse in both directions which allows you to make even faster removal and insertion. There is also extra work to reverse or sort this list but it is a super fun process, ill dive, into later on.

When to use a Linked List?

Linked lists are excellent when there are not many reading operations, or the reading operation is normally of the whole list done by traversing rather than individual elements. An array is better for random access of items. This ability to quickly insert and remove items makes it excellent for real-time computing since insertion/removal is done constantly, which makes it more predictable.

Good applications that benefit a lot from this data structure can be your music player for example. Your image viewer or even the browser history navigation. These types of lists can keep a long list of items and do not require random access once you present all the items to the user. In general, as long as you don't require random access and are not constantly reading individual items, any application that uses a list can benefit from linked lists.

Linked List vs Array

Developers are more familiar with Arrays and it is probably a go-to list to use in applications but there are a lot of applications that are slow because of the wrong list usage. A linked list is better where Array is bad and Array is better when the linked list is bad. They make up for each other and it is good to know when to use which.

Array items are indexed and are store continuously in memory which means If I know where the list starts and the index, I can quickly grab the item in that position.

If I want to add or remove an item, I may have to shift a small or big part of the list. That’s why array access time is great but add and removal of items is slow.

In a linked list, items can be anywhere in memory and what connects them is their pointers to indicate which items come next and/or before.

To insert or remove an item, you simply have to update the pointer of the items before and after. If no item points to an item, it is not part of the sequence. This nature of the pointer makes insertion and removal quick since you don't have to update the position of the rest of the list. Imagine if the list had 1 million items.

It also makes it expensive to access an item directly. Finding an item in a linked list is the same as a treasure hunt. One clue leads to the next and in this case, an item can only tell you what’s next or before and you go from there. An array is faster in access.

So when to use which? If you are doing a lot of removing and adding items, go with and linked list. If you are doing a lot of reading and data accessing, go with an Array.

Single Linked List Implementation

A single linked list is one that all items that have a single pointer. Normally they all have the “next” pointer to indicate which item comes next. It is good when you know you only going to traverse in a single direction. A stack, for example, can be implemented with a single linked list.

Let's define a ‘LinkedList’ class with a property to track the size and store the head element, the first element. We need to keep the size private so it can only be updated internally and make it read-only.

class LinkedList {
#size = 0;
head = null;

get size() {
return this.#size;
}

createElement(value) {
return {value, next: null}
}
...

We also need to “createElement” method that takes the value of the item to add and includes a next pointer which we will update later.

The first method we need for this is the “push” method to add an item at the end of the list.

push(item) {
const element = this.createElement(item);
// handle the first item
if(this.head === null) {
this.head = element;
} else {
let current = this.head;
while (current.next !== null) {
current = current.next;
}
current.next = element;
}
this.#size += 1;
return this.size;

}

The push method is very simple. We first create our element with the item the “push” was called with. If the head is null it means that the list is getting its first item so this new element becomes the head element. If the list has items, we need to find the last element by looping starting from the head while the “next” pointer is not null.

The last element will have a null “next” since it won't have any element to point to. The push method will return the size once it is done.

We also need to be able to insert elements at a specific position and for that, we need the “insert” method. It will take an item to insert and the position to insert at.

insert(item, index = 0) {
// quit if index is out of bound
if (index < 0 || index > this.size) return;
const element = this.createElement(item); // if inserting at start replace head
if (index === 0) {
element.next = this.head;
this.head = element;

} else {
let previous = this.head;
for(let i = 0; i < index - 1; i++) {
previous = previous.next;
}
element.next = previous.next;
previous.next = element;

}
this.size += 1;
return this.size;

}

The insert method starts by quitting early in case the position is out of bounds. It is either below zero or higher than the next empty index. It is also zero-based just like an array to keep things simple.

If the new item is to go at the beginning we make the new element point at the head element — since it comes before — and then set the new element as the head element.

To set it anywhere in the middle of the list we need to iterate till the item before the position where we want to set it. That's why for loop till index minus one. We grab that item at that position as “previous” and make it point to our item and make our item point to the item “previous” was pointing to. Then we increment size and return it.

Now to remove an item from the list we will need to find it then unlink it by connecting its previous and next item. This process simply makes the before and after element of the one we are removing point to each other.

remove(index = 0) {
if (index < 0 || index > this.size) return null;
let removedElement = this.head; if (index === 0) {
this.head = this.head.next;
} else {
let previous = this.head;
for(let i = 0; i < index - 1; i++) {
previous = previous.next;
}
removedElement = previous.next;
previous.next = removedElement.next
;
}
this.#size -= 1;
return removedElement.value;
}

We need to track the item we are removing and start by being the head element. If the first element is to be removed that means the next element becomes the head otherwise, we do something similar to when we were inserting which is to find the element that comes before the one we want.

Once we find that element, we make it point to the element that the element we want to remove is pointing to. In the end, we decrement size and return the element value.

It will also be nice to be able to grab an item from the list which is an operation that is faster on Arrays but worth having in a linked list. It simply goes to the position we want and grabs the element. It returns null if the index is below zero(invalid index) or is equal or greater than the list size(out of reach).

get(index = -1) {
if (index < 0 || index >= this.size) return null;
let element = this.head; for(let i = 0; i < index; i++) {
element = element.next;
}
return element.value;
}

As with any list, it will be nice to be able to iterate it. We can add a method like “forEach” or make the entire LinkedList class iterable by introducing the concept of iterator which is a design pattern worth learning about. Let’s try both.

forEach(cb) {
let current = this.head;
let index = 0;
while(current) {
cb(current.value, index);
current = current.next;
index += 1;
}
}
// usage
list.forEach((v, i) => console.log('item', v, i))

The “forEach” gives us access to the items and their index through a callback but the iterator allows us to do much more, including being able to change a linked list into an array easily. To make the list iterable, we can add an iterator using the generator function in the constructor.

constructor() {
this[Symbol.iterator] = function* () {
let current = this.head;
while(current) {
yield current.value;
current = current.next;
}
};
}
// usage
const list = new LinkedList();
// use in for loops
for(const item of list) {
console.log(item)
}
// change it into an array
[...list]
Array.from(list)

Note: You can always loop the list by using the “head” node without special methods. These looping strategies are just nice to have and I prefer the shortcut.

We can also add more powerful methods to be able to find out if the item is on the list and what position an item is at. For that, we can add a “find” and an “indexOf” method to the list.

find(cb) {
let current = this.head;
let result = null;
while(current) {
const matched = cb(current.value);
if(matched) {
result = current;
break;
}
current = current.next;
}
return result?.value ?? null;
}
indexOf(item) {
let current = this.head;
if (current.value === item) return 0; for(let i = 0; i < this.size; i++) {
if (current.value === item) return i;
current = current.next;
}
return -1;
}

The find method will loop the list from the head and break out once the callback returns a “truthy” value then returns the value. The “indexOf” will also loop and return the index as soon as the item matches any element value in the list.

As you can see, working with linked list gives you extreme control over your list where you can introduce new methods as you wish to find a comfortable way to work with it. This is also a great way to learn how potential Array algorithms are implemented which is worth every line of code.

Source Code: Check this full code on Github

Next

Read the next part of this article where you will learn about how to create a double, and a sorted linked list.

YouTube Channel: Before Semicolon
Website: beforesemicolon.com

More content at plainenglish.io

beforesemicolon.com

Blog & YouTube Channel for Web, UI & Software Development - beforesemicolon.comyoutube.com/c/BeforeSemicolon

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store