Implementing a Linked List in JavaScript
An Introduction to Data Structures in JavaScript
Published on
Sep 30, 2019
Read time
8 min read
Introduction
What’s the best way to store data in a list? In computer science courses, linked lists are one of the first data structures learners encounter. They’re an abstract data type, in which each element points to the next one and — in theory — that brings certain advantages for performance.
There’s plenty of information about linked lists in lower-level languages like C and C++, where they’re more likely to be applied. But, in this article, I want to make this information more accessible to others — like self-taught developers or bootcampers — who are more comfortable working in higher-level, web development languages like JavaScript.
Will I Ever Need to Implement a Linked List in JavaScript?
This may seem like a strange answer for an article dedicated to the subject — but no, you probably won’t.
In theory, linked lists should be faster than arrays in certain situations, such as inserting new items. But, in practice, they’re not. That’s because arrays are highly optimised by JavaScript engines like Google’s V8, written in C++. Unless linked lists were introduced to the ECMAScript specification and given the same kind of optimisations, arrays (or Sets) remain the fastest choices.
So, Why Bother?
Well, as JavaScript becomes the language of choice for more and more programmers, it seems appropriate that important computer science topics should be explained in a language people are comfortable with.
Going through this process has helped deepen my knowledge of the kind of considerations and trade-offs that go into making a library, compiler or even an entire programming language. This knowledge can help us make better decisions in our production code, even if we’re not using linked lists.
Plus, this popular npm package has over 50,000 weekly downloads, so there’s clearly some demand!
What’s the Difference Between an Array and a Linked List?
Both an array and a linked list are ordered collections of data, but — at scale — one offers more efficient access to data and the other offers more efficient insertion. There may be other differences, depending on the implementation, but those are the most significant.
Array
Each item in an array has a number attached to it, called a numeric index, that allows you to access it. This makes accessing elements very efficient.
Say we had a list of four strings, "A"
, "B"
, "C"
and "D"
. If we were to structure this list as an array, it would look like this:
Value: | "A" | "B" | "C" | "D" |
Index: | 0 | 1 | 2 | 3 |
Linked List
Instead of using a numeric index, each element points to the next element. We don’t have to update the numeric index each time we insert or delete an element. In particular, inserting elements into linked lists is more efficient than inserting elements into arrays.
Here’s what our list would look like, structured as a linked list:
Value: | "A" | "B" | "C" | "D" |
Index: | "B" | "C" | "D" | null |
Implementing a Linked List in JavaScript
So, how do we go about implementing a linked list in JavaScript? Oleksii Trekhleb’s brilliant JavaScript Algorithms repository has a good implementation. In this article, we’ll be using Trekhleb’s implementation as the foundation of our own linked list, but we’ll be changing it in a few significant ways, by…
- adding an additional method (
includes
), - adding an additional property (
size
), and by - making some of Trekhleb’s existing methods (such as the
constructor
function) more versatile.
Before we get into the code, open up a new folder in your favourite IDE and create three new JavaScript files: index.js
, LinkedList.js
and LinkedListNode.js
. It’s good practice to keep our LinkedList
and the individual nodes as separate classes, so first we’ll build our node class, so we’ll start in LinkedListNode.js
.
Part 1: Class Constructors
LinkedListNode
Each node needs to hold its own value and the value of the next node in the list, so we can specify each as a property in our class constructor:
class LinkedListNode {
constructor(value, next) {
this.value = value;
this.next = next || null;
}
}
module.exports = LinkedListNode;
That’s all we need for our LinkedListNode
class! Back in index.js
, we can import our new class and try it out:
const LinkedListNode = require("./LinkedListNode");
console.log(new LinkedListNode(3));
console.log(new LinkedListNode(3, 10));
console.log(new LinkedListNode("string", true));
LinkedList Constructor
Now, let’s move into LinkedList.js
, which is going to be a much bigger class. We’ll begin working on the constructor. We want to hold the first entry (the head
) and the final entry (the tail
) in memory, which are null
by default.
For this implementation, I’d also like to keep the list’s size
in memory, so it’s easy to find out how many items are in the list at any one time:
const LinkedListNode = require("./LinkedListNode");
class LinkedList {
constructor() {
this.size = 0;
this.head = null;
this.tail = null;
}
}
module.exports = LinkedList;
Note that all the following code — unless otherwise specified — will be inside the LinkedList
class.
Part 2: Adding New Entries
prepend
Before we can test our new class, we’ll need a way to add new values. We’ll start with a prepend
method to add values to the front of the list, similar to Array.unshift
:
prepend(value) {
this.size += 1;
const newNode = new LinkedListNode(value, this.head);
this.head = newNode;
if (!this.tail) {
this.tail = newNode;
}
return this;
}
- First, we define a new node, based on the value provided and the current
head
node. - Then, we update the
head
to equal this new node. - Third, if no
tail
has been specified (because this is the first item in the list), then thehead
andtail
should be the same. - Finally, we use
this
to return the wholeLinkedList
.
append
We’ll also want a way to add elements to the end of the list, similar to Array.push
. There are a few more steps necessary to do this:
append(value) {
this.size += 1;
const newNode = new LinkedListNode(value);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
return this;
}
this.tail.next = newNode;
this.tail = newNode;
return this;
}
- We start by creating a
new LinkedListNode
as before, but this time we don’t need to specify a second argument (as there is no next value). - If this is the first element in the list, we’ll also want to update
this.head
and we can return the function early. - Finally, we need to change the
next
property of the current final node, before inserting ournewNode
at the end.
To see what’s going on, I recommend going back into index.js
to try adding values to our list.
Part 3: Converting To and From an Array
For convenience, it should be possible to provide an array in the constructor and get a LinkedList
of items in that order — similar to the Set
constructor.
fromArray
First, let’s create a fromArray
method, where we append
each item in the array:
fromArray(values) {
values.forEach(value => this.append(value));
return this;
}
constructor
Next, we can trigger our new method back in the constructor
:
constructor(value) {
this.size = 0;
this.head = null;
this.tail = null;
if (value) {
if (Array.isArray(value)) {
return this.fromArray(value);
}
return new TypeError(value + ' is not iterable');
};
return this;
}
If an array is passed, we run the fromArray
method. If a value other than an array is passed, we return a TypeError
. And if no value is provided, we set this.head
and this.tail
as null
, like before.
toArray
We’ll also want a way to turn our linked list back into an array.
toArray(useNodes = false) {
const nodes = [];
let currentNode = this.head;
while (currentNode) {
nodes.push(useNodes ? currentNode : currentNode.value);
currentNode = currentNode.next;
};
return nodes;
}
This method contains an argument named useNodes
, which — when true
— will fill the array with each LinkedListNode
object, rather than just the value, which could be helpful for debugging.
Back in index.js
, we can test the differences:
const LinkedList = require("./LinkedList");
let list = new LinkedList([1, 2, 3]);
console.log(list.toArray());
console.log(list.toArray(true));
Part 4: Deleting Entries
delete
The delete
operation is the most complex of any of our linked list methods, as it requires slightly different steps, depending on whether the head, tail or any other node needs to be deleted.
By default, our function will delete all nodes of a certain value. But we can pass true
as our second argument to just delete the first node we encounter with the given value.
delete(value, deleteOne = false) {
if (!this.head) {
return false;
}
let deletedNode = null;
// If the head needs to be deleted
while (this.head && this.head.value === value) {
this.size -= 1;
deletedNode = this.head;
this.head = this.head.next;
if (deleteOne) {
return true;
}
};
let currentNode = this.head;
// If any node except the head or tail needs to be deleted
if (currentNode !== null) {
while (currentNode.next) {
if (currentNode.next.value === value) {
this.size -= 1;
deletedNode = currentNode.next;
currentNode.next = currentNode.next.next;
if (deleteOne) return true;
} else {
currentNode = currentNode.next;
};
};
};
// If the tail needs to be deleted
if (this.tail.value === value) {
this.tail = currentNode;
};
if (deletedNode === null) {
return false;
} else {
return true;
};
}
For me, this code makes clear why deleting items can be a much more expensive operation than inserting them!
deleteHead
It would also be useful to delete items from the beginning or the end of our list. For the first item, this is straightforward:
deleteHead() {
if (!this.head) {
return false;
}
this.size -= 1;
const deletedHead = this.head;
if (this.head.next) {
this.head = this.head.next;
} else {
this.head = null;
this.tail = null;
}
return true;
}
deleteTail
Deleting the final item is a more expensive operation, since — when there is more than one item in our list — we need to iterate through the entire list to locate the penultimate item.
deleteTail() {
if (this.size === 0) {
return false;
}
if (this.size === 1) {
if (this.head === null) {
return false;
} else {
this.head = null;
this.tail = null;
this.size -= 1;
return true;
}
}
const deletedTail = this.tail;
let currentNode = this.head;
while (currentNode.next) {
if (!currentNode.next.next) {
this.size -= 1;
currentNode.next = null;
} else {
currentNode = currentNode.next;
}
}
this.tail = currentNode;
return deletedTail;
}
Part 5: Accessing Entries
In linked lists, accessing values has a linear time complexity because we must iterate through the entire list — always from the first entry to the last.
includes
In our implementation, we want our includes
method to accept either a value or an instance of the LinkedListNode
class. It should return true
if an element with the correct value exists in our list, and false
otherwise.
includes(value) {
if (!this.head) {
return false;
}
let isNode = value.constructor.name === 'LinkedListNode';
if (isNode) {
value = value.value;
}
let currentNode = this.head;
while (currentNode) {
if (value !== undefined && value === currentNode.value) {
return true;
};
currentNode = currentNode.next;
};
return false;
}
find
Our find
method should return the value of the first element in the linked list that satisfies a provided callback function. Otherwise, it should return undefined
. If the callback provided is not a function, we’ll throw a TypeError
:
find(callback) {
if (Object.prototype.toString.call(callback) !== '[object Function]') {
return new TypeError(callback + ' is not a function');
};
if (!this.head) {
return undefined;
}
let currentNode = this.head;
while (currentNode) {
if (callback && callback(currentNode.value)) {
return currentNode;
};
currentNode = currentNode.next;
};
return undefined;
}
Conclusion
And that’s a wrap!
To see the complete code of our implementation, check out this GitHub gist.
These methods should be sufficient to cover the core use cases of linked lists. Of course, there are lots of ways we could extend the functionality of our LinkedLists
. If you’re interested in building on what we’ve made so far, you could try adding a sort
, filter
, reverse
, forEach
, toString
or clear
method.
I hope you found this a useful introduction to one of computer science’s fundamental data types.
Further Reading
For alternative JavaScript implementations of a linked list, check out:
https://www.npmjs.com/package/linked-list
https://github.com/trekhleb/javascript-algorithms/blob/maste...
And if you’re keen to learn more about data structures and algorithms written in JavaScript, I strongly recommend you take a look at Oleksii Trekhleb’s full JavaScript Algorithms repository:
https://github.com/trekhleb/javascript-algorithms
Related articles
You might also enjoy...
How to Create a Super Minimal MDX Writing Experience
Learn to create a custom MDX experience so you can focus on writing without worrying about boilerplate or repetition
12 min read
I Fixed Error Handling in JavaScript
How to steal better strategies from Rust and Go—and enforce them with ESLint
14 min read
How to Easily Support ESM and CJS in Your TypeScript Library
A simple example that works for standalone npm libraries and monorepos
5 min read