Data structures are the building blocks of the code we write every day. Whether you’ve written them yourself or not, you’re using them in one way or another: arrays, hash tables, trees, and more.
There aren’t that many resources for learning data structures using JavaScript, though. Most books and CS curriculums will use C, or Java, or Python. And that’s great if you already know those languages, but not if you don’t.
Data structures are hard enough to learn on their own. No need to complicate things by learning a new language at the same time.
In this article I’ll cover the first of the common data structures: Linked Lists.
I’m choosing to start with linked lists instead of something like graphs or trees because most of the other common data structures are based on the idea of interlinked nodes, and linked lists are the simplest way to learn that concept.
Normal Language Ahead
I got my Bachelors and Masters in Computer Science. I took at least 4 courses directly related to data structures and algorithms (one of them about computational geometry! which was very cool). Despite all that I’ve never been one for “formal definitions” and lots of math.
So, fair warning: If you want precise definitions and mathematical proofs, this is not the article for you :) I’m going to try to avoid that stuff as hard as I can, and write for maximum understanding, instead.
Prerequisites
This post uses ES6 JavaScript classes, while loops, and a tiny bit of recursion. If you know basic JavaScript you should be set. The most important thing is to understand how references work in JavaScript, and I’ve linked my post on that. (it’s got visuals and animations too!)
Why Learn Data Structures at All?
On the surface, data structures – especially the “core” ones like linked lists – seem kind of irrelevant to us as JS developers.
We have variable-length arrays built into JavaScript, so we don’t usually need linked lists at all. Arrays can also be used as stacks and queues, using the built-in push, pop, and shift methods.
We have objects that fill the role of hashes (aka hash tables or maps) and let us store values by key, and look up those values quickly. (we also have Map!)
And when was the last time you needed a binary tree? Sure, the DOM is a tree, but you don’t usually need to worry about that – you’ve got document.querySelector for finding things.
And so, the most common answer to “why learn data structures” is “to pass interviews”. Gotta grind that LeetCode.
Honestly, having a good grasp of the basic data structures will help a lot when it comes to solving algorithm problems and killing it at coding interviews. But I like to think of them another way:
Data structures are your palette, as a programmer. The algorithms – or more generally, the code you write – that’s the painting.
Having a wide variety of colors in your palette will expand the range of pictures you can paint.
Having a good set of data structures in your mind will expand the number of problems you can solve quickly (because you know them intimately) and efficiently (because you’ll know of faster ways than “nested for loops”).
If all you have is blue and white, it’s hard (but not impossible) to paint a forest scene.
If all you have is arrays and nested loops, it’s hard (but not impossible) to write fast code.
And all this data structures and algorithms stuff is, in day-to-day code, mostly about avoiding nested loops.
Data Structures and Algorithms?
Data structures are usually learned alongside algorithms, sometimes simultaneously. I think there’s a “correct” order to learn these, though: data structures first, then algorithms.
Knowing the common data structures will make it easier to solve problems (especially the LeetCode variety) because often the “trick” to making something fast is to use a data structure other than a plain old array.
It’s hard to learn data structures without touching on some algorithms, because there are operations to perform: adding items to a linked list, traversing that linked list, popping something off a queue.
Operating on data structures kinda has to involve algorithms, at least if you define an algorithm as “a set of rules that precisely defines a sequence of operations” (which is how Wikipedia defines it).
So I can’t say “don’t touch a single algorithm until you learn data structures”, but it’s a good idea to learn some data structures before you get to tackling a lot of problems in earnest.
Linked Lists in JavaScript
First off, what exactly is a “linked list”?
A linked list is a way to represent… well, a list of items. The values can be anything, but let’s say we’re storing the numbers of a PIN as the user enters it. If the user enters 4321, a linked list holding those numbers would look like this:
Each item in the list is a node, and a node contains two things: the value itself, and a reference to the next node in the list.
Why would you do this instead of use an array? Well that’s a good question. It depends on what kind of array you’ve got.
In JavaScript, we have variable-length arrays: we can push items on, and the array will grow to accomodate them. They’re great. (and in fact, they use linked lists under the hood, sometimes! This article by Ryan Peden is a great rundown of how JS arrays are implemented)
In lower-level languages, like C, arrays have a fixed length. An array is literally a chunk of bytes reserved in memory, and they’re contiguous, and you’ve gotta decide up front how long it will be.
Once a fixed-length array is full, if you want to add another item you have to first create a new larger array, then copy over all the items, and then, finally, insert the new one. You can imagine this would be a pain, and potentially very slow, if you’re overflowing the array often. (in practice, there are strategies to make this less frequent)
This is where linked lists become useful: you can always easily add one more item – no resizing needed! Just tack it on the end, very quickly.
All that said, there aren’t a lot of compelling reasons to use a linked list over an array in JavaScript, because our arrays are powerful on their own. Like I mentioned earlier, though, linked lists are a building block for the more complex data structures. Understanding linked lists will make understanding the others easier.
Let’s look at how they work.
A Linked List With One Value
A linked list cannot merely spring into existence as simply as creating an array like [4, 3, 2, 1]. There is no language syntax for this. We need to build it up, one item at a time.
We’ll start with an “empty list”, which we’ll represent as null.
let list = null;We can represent each node as an object with two properties: one for the value, and one to reference the next node in the list.
let node = {
value: 4,
next: null
}This node is actually a list with a length of 1 – it’s a single value that doesn’t have any values after it. Since we’ll need to create nodes pretty often, let’s write a function for that:
function makeNode(value) {
return {
value: value,
next: null
}
}That function is all we need to let us create a linked list from scratch. Here we’ll create one to hold our “4321” PIN:
// create the nodes
let four = makeNode(4);
let three = makeNode(3);
let two = makeNode(2);
let one = makeNode(1);
// link them together
four.next = three;
three.next = two;
two.next = one;First we create 4 nodes, each holding a number of the 4-digit PIN. Each of those nodes is isolated, though. Initially, they don’t point next to anything.
Then, we link them up by assigning each node’s next pointer to the following node. Here’s what we’re doing, visually:
This is the simplest possible list. We can’t even really do anything with it yet, other than marvel at its connectedness.
Let’s write a function to print out the nodes. We’ll call it printList and it will take a list.
function printList(list) {
// print each node somehow
}Now here’s a funny thing: I’ve called the argument list, but I could’ve called it node. Think about that for a second: every node in our list is actually its own list.
Starting from four? Then we’d expected to see 4, 3, 2, 1.
Starting from two? Well, the next node from two is one, so we’d print 2, 1.
Let’s fill out the function now. We need to start by printing the current node, and then advance to the next one, print it, advance to the next one, and so on.
function printList(list) {
// Start with the first node
let current = list;
// As long as `current` isn't null, print out the value
while(current) {
console.log(current.value);
// Advance to the next node in the list by replacing
// current with whatever `next` points to
current = current.next;
}
}Here’s what this is doing:
And we can try it out on our list, starting at various places:
printList(four)
// 4
// 3
// 2
// 1
printList(two)
// 2
// 1
printList(null)
// (doesn't print anything!)Looks like it works! (always check the edge cases too, like empty lists ;)
We talked about this idea that each node in the list is itself a standalone list. This is a special property that not every data structure has (arrays aren’t like this, for instance – not every array element is itself an array).
This property where each node in the data structure is itself a self-contained version of that data structure makes this a recursive data structure, and it means that we can write our printList function as a recursive one:
function printListRecursive(list) {
// If this node exists, print it out
if(list) {
console.log(list.value)
} else {
// Hit the end? Stop here.
return;
}
// Do it again for the next one
// (eventually, list.next will be null)
printListRecursive(list.next);
}If you’re not used to recursion, it can be a bit brain-bending at first. It still hurts my brain sometimes. Recursion gets easier with practice, though, and the iterative verison of printList works fine too.
Let’s look at other operations we can perform on the list.
Practicality First: Head and Tail
For most things we’ll want to do, we need access to the first or last element of the list. These are called the head and tail.
Want to print everything out? Start at the head, and walk down the list.
Want to add something to the end? Start at the tail, and assign tail.next to point at the new item.
There’s 2 ways we can write this now: either as a class in the object-oriented style, or as individual functions that each take a list and do something with it.
I’m going to focus on a class-based approach here.
Create a JavaScript Linked List Class
Ok! Let’s make a class to contain the list. We’ll start off simple, with a constructor that will set up the head and tail – both null to start, since the list will start off empty.
class List {
constructor() {
this.head = null;
this.tail = null;
}
}Add a Node to the List
Remember earlier how we linked up the list manually? Yeah. That was a pain. Let’s not do that anymore.
We’re going to write an append function to add a new item to the end. It’s going to have to be a bit more complicated because we have a head and a tail to keep track of, and we’ll have to handle the case when the list is empty. We can reuse our makeNode function, though!
There are two cases to handle, here: initially, the list is empty, so we need to assign head and tail to this new node. After that, we only need to tack this node on the end by updating the tail.
class List {
constructor() {
this.head = null;
this.tail = null;
}
append(value) {
let node = makeNode(value);
// Is it currently empty?
if(!this.tail) {
// Head and tail are one and the same
this.head = this.tail = node;
return node;
}
// If it's not empty, tack this on the end,
// and update `tail` to point at this new node
this.tail.next = node;
this.tail = node;
// Return the node we added
return node;
}
}Here’s what that looks like when the list is empty, with null for a head and tail:
Then, for the second node (and every node after that), the process is the same: point the existing tail’s next at this new node, then update tail to be the new end-of-the-list node.
Print the List
Let’s write a print function so we have some way of debugging this thing. It’ll work the same as the iterative printList we wrote earlier.
class List {
// ...
print() {
let current = this.head;
while(current) {
console.log(current.value);
current = current.next;
}
}
}Now we can make a list, add a few items, and print it out:
let test = new List();
console.log('first, as an empty list:')
test.print();
console.log('then, with contents')
test.append('t');
test.append('e');
test.append('s');
test.append('t');
test.print();
// class List test:
// first, as an empty list:
// then, with contents
// t
// e
// s
// tLooks like it works! How about adding items to the beginning?
Prepending Items Onto the List
The “empty list” case is pretty much identical. We’re inspecting head here because it felt more congruent with prepending, but in reality it doesn’t matter whether we look at head or tail to check for emptyness – they’ll both be null.
The main difference between prepending and appending is that we need to work with the head instead of the tail.
We’re tacking this new node on the front by replacing the old head, making sure to point the new node’s next at the old head before reassigning the head.
class List {
// ...
prepend(value) {
let node = makeNode(value);
// Is it currently empty?
if(!this.head) {
// gee this looks familiar
this.head = this.tail = node;
return node;
}
// If it's not empty, this new value
// will become the `head`, and it will
// need to point at the old head
node.next = this.head;
this.head = node;
// Return the node we added
return node;
}
}Order of Operations Matters!
With the add/remove/insert operations, the order of the assignments matters. We need to do them in the right order, or we’ll break the list.
In this prepend function, for example: when we go to link up the new node, head is still pointing at the existing first item, and the new node is dangling in space, disconnected from everything.
It’s important to notice here that head is our only way to access the rest of the list! It points at the first node, the first node points to the next, and so on… but head is the only thing that points to that first node.
So if we were to point head at the new node as Step 1, then how would we access the list anymore?
// wrong order. don't do this!
this.head = node;
node.next = this.head;Doing that would cut off access completely, and in this case, it’ll create an infinite loop if we were to print out the list!
So, make sure to do the assignments in the right order. Think it through for every operation. Each one has its own “right order” – notice how append and prepend differ by more than just variable names.
I like to draw out boxes and lines on paper when I’m not sure.
If the next and head and tail pointers seem confusing, it might help to read this post about how references a.k.a. pointers work in JavaScript.
Remove the First Node From the List
Let’s look at how to remove the first or last item in the list.
These are like the shift and pop functions on JavaScript arrays, but I can never keep those names straight so I’m gonna call them removeFirst and removeLast :)
The goal here is to reassign head to point at the second node in the list (or null if the list only has one item). Again, the order of assignments matters. When we remove the first node, we’ll also blank out its next pointer so that it won’t continue to refer to the rest of the list.
class List() {
// ...
removeFirst() {
// Is the list empty? Give up here.
if(!this.head) {
return null;
}
// Save a reference to the head,
// then detach it by pointing `head`
// at the second node.
let nodeToRemove = this.head;
this.head = nodeToRemove.next;
// Truly detach this node by removing
// its link to the rest of the list
nodeToRemove.next = null;
// If we're removing the last node,
// then we need to update `tail` too!
if(nodeToRemove === this.tail) {
this.tail = null;
}
// Maybe the user wants to do something
// with it. Return the node we removed.
return nodeToRemove;
}
}Notice in every one of these changes we need to take special care to think about what should happen to head and tail. In this case, if we’re removing the one-and-only list node, we need to explicitly set tail to null.
Remove the Last Item From the List
Removing the first node was easy. Take it out, reassign head, all done.
Removing the last one is a bit more involved.
Our linked list is singly-linked, which means the links only go in one direction: beginning to end. That means we can easily walk forwards through the list (you’ve seen that when we printed it out), but it’s much harder to walk backwards. The nodes don’t have a reference to the previous one, only the next.
One way to make this easier is to convert our implementation into a doubly-linked list, where each node has both a next and a previous pointer. Having both pointers makes every other operation more complex, though, and it takes a little more memory. It’s a tradeoff. We’ll stick with a singly-linked list for this article.
So are we stuck?
Well, think about it for a second: we need to find the node before the last one.
Said another way, we need to find the node that has node.next === tail. To do that, we can start at the front and walk the list until we find it.
Quick Diversion: findNodeBefore
Let’s write a function for that. We’ll call it findNodeBefore and it will take a node, and find the one before it in the list.
class List {
// ...
findNodeBefore(node) {
// Exit early if node is null
if(!node) {
return null;
}
// There's nothing before the head!
//
// (technically we don't need this check here,
// can you figure out why?)
if(node === this.head) {
return null;
}
// Start at the head
let current = this.head;
// Walk the list until `current.next`
// points at `node`, or until we're out of
// nodes.
while(current) {
// Break out when we find the node
if(current.next === node) {
break;
}
// If this wasn't it, then advance
// to the next one
current = current.next;
}
// Breaking out of the loop above left `current`
// at the node before the `node` we're looking for,
// so we're done.
return current;
}
}Removing the Last, at Last
Now we can finally remove the last node. We’ll use the findNodeBefore function we just wrote.
class List {
// ...
removeLast() {
// Is the list empty? Give up here.
if(!this.tail) {
return null;
}
// Save a reference to the tail,
// then detach it by pointing `tail`
// at the previous node
let nodeToRemove = this.tail;
this.tail = this.findNodeBefore(this.tail);
// If this was the last node in the list, then
// update `head`
if(nodeToRemove === this.head) {
this.head = null;
}
return nodeToRemove;
}
}Get the Length of the List
It’d be nice if we could figure out how long the list is.
There are two ways to do this: the manual way, where we walk the list and count up the elements… and the better way, where we keep a length variable and update it every time we add or remove an item.
The only downside to the length variable is it’s an extra thing to keep track of, but it only requires incrementing and decrementing a number. Let’s look at both ways.
First, we’ll implement length as a function that walks the list and counts up the nodes. This is gonna look a lot like the print function, because it’s essentially the same process, except that the operation will be to “add 1” instead of “console.log”.
class List {
// ...
getLength() {
let current = this.head;
let count = 0;
while(current) {
count++;
current = current.next;
}
return count;
}
}The main downside with this method is speed: it has to traverse the entire list. That’ll get slow if you do it a lot, or if the list is very long.
The alternative is to keep track of the length as it changes, by incrementing and decrementing a number whenever we add or remove a node. For that, we need to initialize the length to 0 in the constructor, and we have to add a bit to every function that modifies the list.
class List {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
append(value) {
let node = makeNode(value);
// Is it currently empty?
if(!this.tail) {
// Head and tail are one and the same
this.head = this.tail = node;
// gotta increment length before we return!
this.length++;
return;
}
// If it's not empty, tack this on the end,
// and update `tail` to point at this new node
this.tail.next = node;
this.tail = node;
// Return the node we added (and increment length)
this.length++;
return node;
}
prepend(value) {
let node = makeNode(value);
// Is it currently empty?
if(!this.head) {
// gee this looks familiar
this.head = this.tail = node;
// gotta increment length before we return!
this.length++;
return node;
}
// If it's not empty, this new value
// will become the `head`, and it will
// need to point at the old head
node.next = this.head;
this.head = node;
// Return the node we added (and increment length)
this.length++;
return node;
}
removeFirst() {
// ... do the removal ...
this.length--;
return nodeToRemove;
}
removeLast() {
// ... do the removal ...
this.length--;
return nodeToRemove;
}
}There we go. All updated. And since we “spread the work out” by keeping the length correct at all times, it’s very fast to read the length property.
Insert a Node in the Middle
We’ve seen how to add an item at the beginning or end of the list… but what about adding one in the middle?
To do it, we need two things: the value to add, and where to insert it. We’ll call that the index. It’ll be zero-based, and if we say to insert the value Wednesday at index 2 in a list like this one, here’s what will happen:
We also have to decide what should happen if we try to insert something at an index that doesn’t exist.
For instance, if we call list.insert('Wednesday', -5), what should happen?
Or what if the list is empty, and we call list.insert('Wednesday', 25)? Should it make a best effort, and insert the item as far back as it can (as the first item, in this case)? Should it throw an exception? Should it fail silently?
These are all the pesky choices that you, dear library designer, get to decide upon. Just make sure you document them somewhere ;)
For our implementation here, let’s decide that if the index is at or before the beginning of the list, we’ll insert the node at the beginning. And if it’s past the end, we’ll insert the node at the end. This is the same behavior we get from Array.splice.
class List {
// ...
insert(value, asIndex) {
let previous = null;
let current = this.head;
let currentIndex = 0;
// If the index is 0, negative, or falsy
// we'll insert the node at the front
if(asIndex <= 0 || !asIndex) {
// oh hey, we have a function for this!
return this.prepend(value);
}
// If the index is at or past the end, insert this
// new node at the end
if(asIndex >= this.length) {
return this.append(value);
}
// create a new node to insert
let node = makeNode(value);
// Walk through the list, looking for a place to put it.
// Keep track of the `previous` node; we'll need it soon.
while(current && currentIndex !== asIndex) {
previous = current;
current = current.next;
currentIndex++;
}
// When we're done, `current` points at the
// node that currently holds the `currentIndex` place,
// and `previous` is the node before it. We need both,
// so that we can insert ours in the middle.
previous.next = node;
node.next = current;
// We added a node! Keep the length up to date.
this.length++;
return node;
}
}Read through the comments to understand how it works, and watch the animation a few times.
For these operations (and most data structures stuff) I like to have a pen and paper handy to draw it out.
Remove a Node From the Middle
Now that we know how to insert a node in the middle, removing one should be… pretty similar. We need to find the node before the one we want to remove, and point its next at the node after the one we want to remove. That will unlink our node from the chain, and we’re good to go. Let’s see how it works.
class List {
// ...
remove(index) {
// If the index is out of range, just return null
if(index < 0 || index >= this.length) {
return null;
}
// Use our existing function if this is
// the first node, rather than handling the
// special case of previous===null below
if(index === 0) {
return this.removeFirst();
}
// Start at the beginning
let current = this.head;
let previous = null;
let currentIndex = 0;
// Walk along the list, keeping track of the `previous`
// We'll need it to re-link everything
while(current && currentIndex !== index) {
previous = current;
current = current.next;
currentIndex++;
}
// Link up the before & after nodes
previous.next = current.next;
// Unlink this node by wiping out its `next`
current.next = null;
this.length--;
return current;
}
}Linked Lists! Yay!
I really couldn’t think of a better headline there, I’m sorry.
But we’re done! If you read all the way down here, congrats! This was a long one. Phew.
We covered the basics of singly-linked lists: inserting, removing, searching, traversing. As with most things, the rabbit hole goes deeper: you can learn about sorting, doubly-linked and circular linked lists. You can learn more about Big O notation, and lots else. There’s a whole wide world of data structures out there and this is just the tip of the iceberg.
Hopefully you understand linked lists a bit better than you did before!
This post is part of a series on data structures and algorithms in JavaScript, and if you want me to let you know when the next one is out, drop your email in the box. You’ll also hear about other posts I write, like stuff on React, CSS, and front end development in general.