JS Data Structures: Linked List
Learn what a Linked List is and how to write one in Javascript
Data structures are a vital part of computer science. They are important for understanding fundamentals and often come up in interviews. Let’s see how to make a singly linked list in Javascript. We’ll be using ES6 syntax throughout.
What is a Linked List?
Singly Linked List with a Head
I advise reading this on a desktop or in landscape mode on a mobile device, as the text diagrams, which are critical to the article, can get distorted if lines are wrapped.
A linked list is an ordered, linear structure, similar to an array. Instead of items being placed at indices, however, they are connected through a chain of references, with each item containing a reference to the next item. There are benefits to using a linked list over an array, and benefits for using an array over a linked list. The two differ in the amount of memory they use and the speed of various tasks related to accessing, adding, and removing data.
For this article, we’re speaking only of a singly linked list with a head. The beginning of the chain is called the head and the end of the chain is symbolized with ∅.
Array: 0: 12 1: 99 2: 37Linked List: head → 12 → 99 → 37 → ∅
This is referred to as singly-linked because each item has only a one-way link to its next item. Each link in the chain is called a node. Each node is just a plain old Javascript object. The linked list depicted above in Javascript looks like this.
const list = {
head: {
value: 12
next: {
value: 99
next: {
value: 37
next: null
}
}
}
};A linked list, as you can see, is nothing more than objects nested deeply inside of each other. The next property of each node object in the list is a reference to the next node object. To see why this is, or if you need a refresher on references in Javascript, check out this article.
The head is a reference to the first node in the chain. In other words, the head property on the outermost object of the linked list points to first item in the list. Each item in the list is accessed through the next property of the item before it.
How would we access 37 in the array we depicted above? Because an array has everything ordered and accessible by index, it’s easy.
arr[2]; // -> 37A linked list has items accessible only through the parent object, i.e. the previous item. To access the same item 37 in the linked list above, the code would look like this.
list.head.next.next.value; // -> 37With this line of code, we see this structure begin to resemble a linked chain. In addition, we see that the only way to get to a value in the list is to start at the beginning, the head, and traverse our way down until we get to what we’re looking for.
Let’s create this data structure.
Writing a Singly Linked List with a Head
Let’s write a class.
class LinkedList {
constructor(value) {
this.head = {
value,
next: null
}; this.length = 1;
}
}console.log(new LinkedList('Hello!'));
// -> { head: { value: 'Hello!', next: null } }
All we get back from the class at this point is an object with a head property containing another object. This is a linked list with a single node.
head → 'Hello!' → ∅Not very exciting. Let’s allow a user to add items to the head with a method.
Add To Head
class LinkedList {
constructor(value) {
this.head = null;
this.length = 0;
this.addToHead(value);
}
addToHead(value) {
const newNode = { value }; // 1
newNode.next = this.head; // 2
this.head = newNode; // 3
this.length++;
return this;
}
}const list = new LinkedList('first')
.addToHead('second')
.addToHead('third');
Note that returning this allows us to chain addToHead calls. Our list looks like this.
head → 'third' → 'second' → 'first' → ∅Let’s walk through what happened. Our method creates a new node, an object with a value property. It sets the next property of that node to the current head. It then makes the head point to this newly created node. In visual form, corresponding with the numbered comments in our method:
head → ∅1. const newNode = { value }; 'first'head → ∅2. newNode.next = this.head; 'first'
↓
head → ∅3. this.head = newNode; 'first'
↑ ↓
head ∅head → 'first' → ∅
The last two are identical, but drawn differently. Let’s go through one more.
head → 'first' → ∅
1. const newNode = { value }; 'second'head → first → ∅2. newNode.next = this.head; 'second'
↓
head → 'first' → ∅3. this.head = newNode; 'second'
↑ ↓
head 'first' → ∅head → 'second' → 'first' → ∅
Adding 'third' does the same thing and we end up with our final chain. The final object looks like this.
{
length: 3,
head: {
value: 'third',
next: {
value: 'second',
next: {
value: 'first',
next: null
}
}
}
}Let’s examine the time complexity of addToHead. The method adds an item to the beginning of our data structure. It creates an object with value and next properties and reassigns the head reference. This is O(1), a constant-time operation. In comparison, adding an item to the beginning of an array with array.unshift is a linear O(n) operation because every subsequent item in the array has to be shifted over to the next index. Therefore, this operation is much faster in a linked list than in an array. Let’s look at code that adds to the beginning of an array.
const arr = [1, 2, 3];
arr.unshift(4); // -> arr: [4, 1, 2, 3]Here’s a diagram of what’s happening.
4 [1, 2, 3]
4 [1, 2, 3, ]
⤻4 [1, 2, , 3]
⤻4 [1, , 2, 3]
⤻4 [ , 1, 2, 3]
⤻
[4, 1, 2, 3]
Remove From Head
We also need a method to allow removal from the head. Let’s add this method to the class.
removeFromHead() {
if (this.length === 0) {
return undefined;
}
const value = this.head.value;
this.head = this.head.next;
this.length--;
return value;
}Here’s what’s happening when we call list.removeFromHead().
head
↓
'third' → 'second' → 'first' → ∅
head
↓
'third' ⥇ 'second' → 'first' → ∅ head
↓
'second' → 'first' → ∅head → 'second' → 'first' → ∅
In the code, notice that we don’t need to explicitly delete the first node. By setting the head equal to the next node, we lose all references to the first node and it gets garbage collected.
This is again O(1), as we’re performing a fixed number of operations every time we add to the head. The equivalent array method, array.shift, is O(n). If we delete the first item of an array, every subsequent item has to be moved down one index.
Find Item
What if a user wants to locate an item? Let’s write a method.
find(val) {
let thisNode = this.head;
while(thisNode) {
if(thisNode.value === val) {
return thisNode;
}
thisNode = thisNode.next;
}
return thisNode;
}Here’s what we’re doing when we call list.find('first'). Starting from our list with 3 items:
head → 'third' → 'second' → 'first' → ∅ thisNode
↓
head → 'third' → 'second' → 'first' -> ∅ thisNode
↓
head → 'third' → 'second' → 'first' → ∅ thisNode
↓
head → 'third' → 'second' → 'first' -> ∅
With the while loop, we’re moving along the list until we either find our item or get to the end. Once we find our item, we return the reference to the node. If the item’s not found the function returns undefined.
Finding an item is a linear-time operation in both linked lists and arrays.
Remove Anywhere
Let’s allow a user to remove an item from anywhere in the list. This is the most complex function we’ll write. We’ll write a function that takes in a value and traverses the list until it finds that value. Once found, it’ll remove it from the list.
remove(val) {
if(this.length === 0) {
return undefined;
}
if (this.head.value === val) {
this.removeFromHead();
return this;
}
let previousNode = this.head;
let thisNode = previousNode.next;
while(thisNode) {
if(thisNode.value === val) {
break;
}
previousNode = thisNode;
thisNode = thisNode.next;
}
if (thisNode === null) {
return undefined;
}
previousNode.next = thisNode.next;
this.length--;
return this;
}Again, returning this allows us to chain function calls if desired.
If we’re trying to remove from a list of length 0, we return undefined. If the item we’re trying to remove is the head, delegate to removeFromHead. If neither of those, create a reference to head and a reference to the item after head. Go through the list until the item is found, updating both references. If the end of the list is reached, the item’s not present and we return undefined.
If the item is found, set the next value of the previous node equal to the next value of the item. Once the function returns, there are no references left to the item’s node and it is able to be garbage collected. These last steps are depicted here when running list.remove('first').
pN === previousNode and tN === thisNode.
head → 'third' → 'second' → 'first' → ∅ pN tN
↓ ↓
head → 'third' → 'second' → 'first' → ∅ pN tN
↓ ↓
head → 'third' → 'second' → 'first' → ∅ tN
↓
pN 'first'
↓ ↓
head → 'third' → 'second' → ∅head → 'third' → 'second' → ∅
This is a linear operation in both linked lists and arrays.
The Full Class
class LinkedList {
constructor(value) {
this.head = null;
this.length = 0;
this.addToHead(value);
}
addToHead(value) {
const newNode = { value };
newNode.next = this.head;
this.head = newNode;
this.length++;
return this;
}
removeFromHead() {
if (this.length === 0) {
return undefined;
}
const value = this.head.value;
this.head = this.head.next;
this.length--;
return value;
}
find(val) {
let thisNode = this.head;
while(thisNode) {
if(thisNode.value === val) {
return thisNode;
}
thisNode = thisNode.next;
}
return thisNode;
}
remove(val) {
if(this.length === 0) {
return undefined;
}
if (this.head.value === val) {
return this.removeFromHead();
}
let previousNode = this.head;
let thisNode = previousNode.next;
while(thisNode) {
if(thisNode.value === val) {
break;
}
previousNode = thisNode;
thisNode = thisNode.next;
}
if (thisNode === null) {
return undefined;
}
previousNode.next = thisNode.next;
this.length--;
return this;
}
}Let’s enhance it a little. We’ll allow users to invoke the class with multiple values and add multiple values to the head at once. The constructor and addToHead methods change and we add a new method.
constructor(...values) {
this.head = null;
this.length = 0;
this.addToHead(...values);
}_addSingleItemToHead(value) {
const newNode = { value };
newNode.next = this.head;
this.head = newNode;
this.length++;
}addToHead(...values) {
values.forEach(value => this._addSingleItemToHead(value));
return this;
}
More Complex Implementations
Tail Pointer
Many linked list implementations will have a tail pointer as well as a head pointer. With the tail pointer, it becomes possible to write new methods including addToTail and removeFromTail. It’s possible to write those already, but they’ll be more difficult to write and more inefficient without the tail pointer.
head tail
↓ ↓
12 → 99 → 37 → ∅const list = {
head: → { value: 12, next: ⤵ }
{ value: 99, next: ⤵ }
tail: → { value: 37, next: ∅ }
};
Doubly Linked List
A doubly-linked list is the same as a singly-linked list, except that every node has both a next pointer pointing forwards and a pre (previous) pointer pointing backwards. This takes more memory to maintain and the logic of the methods becomes a little more difficult to reason about. It allows some speed optimizations. It would look like this.
head
↓
∅ ← 12 ⇄ 99 ⇄ 37 → ∅const list = {
head: → { value: 12, pre: ∅, next: ⤵ }
{ value: 99, pre: ⤴, next: ⤵ }
{ value: 37, pre: ⤴, next: ∅ }
};
Circular Linked List
A circular linked list has no null value at the end. The next value of the last item is set equal to the head.
head
↓
12 ← 37
↘ ↑
99const list = {
head: → { value: 12, next: ⤵ }
{ value: 99, next: ⤵ }
{ value: 37, next: list.head }
};
Circular, Doubly-Linked List with Head and Tail Pointers
Of course, you can have it all.
head tail
↓ ↓
12 ⇄ 37
↘↖ ↗↙
99
const list = {
head: → { value: 12, pre: list.tail, next: ⤵ }
{ value: 99, pre: ⤴, next: ⤵ }
tail: → { value: 37, pre: ⤴, next: list.head }
};
Other Methods
There are other methods sometimes implemented in linked lists that we won’t work with, but here are a few.
getFromIndex(index)— pass in a number and get the value of the item at that index in the list. We’d need to traverse the list, going down until we get to the index we want.addAtIndex(index, val)— pass in an index and add a new node at that location
addToTail(value)removeFromTail()
Time Complexity
Here’s a table of time complexity, compared to arrays.
Linked List ArrayInsert at O(1) O(n)
beginningRemove from O(1) O(n)
beginningInsert O(1), O(n) * O(1)
at endRemove O(1), O(n) O(1)
from endInsert O(1), O(n) * O(n)
in middle Remove from O(n), O(n) O(n)
middleFind / Get O(n) O(1)
item at indexWasted O(n) 0
Space
- Insert and removal at end is O(1) with a tail pointer or stored reference to the last node. O(n) if the node needs to be accessed by traversing down the list.
- Insertion in middle is O(1) if we already have a reference to that node stored. If we need to traverse to the location first, O(n)
We’d use a linked list over an array when we need faster insertion and deletion, but we can tolerate slow item retrieval and we’re o.k. with extra space taken up. If we’re space-limited or access speed is important, we’d use an array.
Phew. That’s it.
If this article was helpful, please hit the heart on the left and feel free to check out some of my other recent work.
My Work
Online Courses
I’ve created an online course on educative.io covering intermediate JavaScript topics such as scope, closures, OOP, this, new, apply/call/bind, asynchronous code, array and object manipulation, and ES2015+.
I’ve created another course to help people ace a JavaScript interview.
