Data Structures in JavaScript (Part 1: Linked Lists)
Programming in JavaScript, I had never run into a linked list in the wild since it isn’t a native data structure in JavaScript, unlike in C++ and Java. This is until I started studying up on data structures and algorithms as these are crucial for not only the interview process, but in order to be a good engineer. The goal of this series is to go through the basic data structures, how to implement them in JavaScript, and the pros and cons of each.
What is it?
As mentioned above, a linked list is a type of data structure that is native to languages such as C++ and Java. It’s a way of storing data and you can think of it as the snake in the game Snake from the early mobile gaming days (think Nokia 3310). In the game, you start off with a short snake and as you eat the dots, the snake grows longer by a unit. You can think of the snake as the linked list, which is made up of these units, or ‘nodes’. Each node can store a value, and a pointer to the next node. You would start at the head of the snake, or the ‘head node’, and as you add more values to you linked list, it would create a node for the new value and add it to the end of the list.
There are 3 main types of linked lists: a singly linked list, a doubly linked list and a circular linked list. In this post, I’ll only be looking at singly linked lists as this is meant to be an introduction, but below is a visualization of the 3 different types, so you can get an idea of what the differences are.
What’s so great about them?
If you’re reading this looking to learn about linked lists, you may be wondering ‘I can just use an array to store data, right?’, and you can, but there are several key differences between an array and a linked list. Two main difference are how they use memory and the time complexity of certain methods.
Arrays take up a block of memory big enough to hold the array. If you add more and more data to the array that it grows larger than the initial block that the program had allocated, JavaScript will (under the hood) double the size of that block to accommodate the additional values. This happens because JavaScript is a dynamic language and makes it easier for the programmer instead of having to declare a set size for the array upon initialization. You can see where this could be wasteful when an array is just slightly over the initial size and it has to take up double the memory just to fit in those additional values. This is where it differs from linked lists because in linked lists, each node takes up enough memory for itself, so even if you keep adding values to it, the new value will be stored in its own node, and the previous node would know where to find it.
The other main difference is the time complexity of certain methods. Take a look at the table below, it should give you a good idea of the differences between array and linked lists. You’ll notice the main differences come from the lookup and prepend methods. The lookup method is O(n) for the linked list, because as stated earlier, each node only has a pointer to the following node. That means if you want to know what the value of 4th node in a linked list is, you have to start at the head and go through each node until you hit the 4th node. In an array, you can go straight to the 4th slot of an array and get the value at O(1) time. However, when it comes to dealing with the first value, a linked list is the better data structure in that removing or adding a value at the beginning is done at O(1) time instead of O(n) time that it takes for an array. The reason it takes O(n) time for an array is that since each value is assigned an index in an array, when you add a value to the beginning (or remove a value), you have to then go through the entire and change their indexes. Compare this to a linked list where all you have to do is reassign where the ‘head’ is pointing to. If you want to add a value to the front, you create a new node with that value, make that the new head, and point its pointer to the previous head.
How do I implement it?
Now that you know why and when to use a linked list, how do you create one in JavaScript? As mentioned, linked lists aren’t a native data structure in JavaScript, so to implement it, you need to create a custom class for it. Now this will mean that the differences and benefits mentioned above may not be completely accurate since, under the hood, it would be treated as a different data structure.
In order to implement this, we’ll use the ES6 class function to create a class for a linked list and a class for a node.
class LinkedList {
constructor() {
this.head = null;
}
}class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
In the above code snippet, you’ll see a new linked list is instantiated as an empty linked list. A new node is instantiated with a value, with the pointer pointing to a null value by default. In order to create a new linked list with the values 1, 2, 3 you would do something like the following:
// Create a linked list: 1 -> 2 -> 3 -> null// This creates the new empty linked list
let exampleLinkedList = new LinkedList();// Create the 3 nodes
let node1 = new Node(1);
let node2 = new Node(2);
let node3 = new Node(3);// Setting the first node as the head of the linked list
exampleLinkedList.head = node1;// Setting the pointers of each node
node1.next = node2;
node2.next = node3;
The above would result in a nested hash that would resemble a linked list in JavaScript.
Now that you know what a linked list is, feel free to look into the doubly and circular linked lists and see if you can implement those in JavaScript!
