24
Data Structure with JavaScript: Linked List
Hello, devs.
Today I want to dive deep into a very specific data structure to hold a collection that's called Linked List.
First I'll briefly explain the array problem and how linked lists came to solve those problems and then we'll how to implement that in JavaScript.
I already can say that as a JS dev I don't see big use cases because we have natively a pretty decent way of handling collections. However, as a software engineer, I consider it very important to have a base understanding of it in case I need it in the future.
Knowledge is power and never useless.
Arrays are one of the most efficient ways of storing data collections like a list of friends on Instagram for example.
In JavaScript when we want to create a list of something, all we need is a very simple open/close square bracket ([]) and push as many elements you want to it.
However in some other languages, especially the ones which are focus on performance the approach is different. There, if you need a list, you have to specify the size of your list, which sometimes is a problem because we often handle dynamic data.
And it makes sense to have this approach. If you have little memory and need to write some code that compiles a very low machine language (like binary) if you say that your list will have only 3 elements, for example, the compiler can say:
Hey, for this list here can be allocated only a few bytes because we know in advance it'll only contain a max of 3 elements
Also, if you want to insert or remove an element in some specific position, you need to entirely move the list and these operations could be tedious and expensive.
In JS we don't suffer much about that because the language was designed in that way and we also have native array methods (very well optimized I suppose) that remove or add an element and regen the list, like the method Array.prototype.splice().
const months = ['Jan', 'March', 'April', 'June'];
// insert exactly in the index one (1, 0) the string `Feb`
months.splice(1, 0, 'Feb');
console.log(months); // Array ["Jan", "Feb", "March", "April", "June"]
// removes everything from the index 3 til the last el ("April" and "June")
months.splice(3, months.length)
console.log(months); // ["Jan", "Feb", "March"]Linked list implementation tries to solve the max number of elements we can store in a list and how to easily navigate through a list by change the data structure used from arrays to simple linked objects (node).
Every node will have 2 properties:
-
element: the data we want to store in our list; -
next: a link to another node or the value null (non-existing next node).
Maybe the best way to visualize it is by imagining a train.
In a train we always have the "head" which and from there it's connected the first "wagon", then a second "wagon" is connected to the first until the end of the train.
If we want to remove a defective wagon, for example, all we need to do is find this wagon, link the previous wagon to the next wagon, and done.
The principle is the same when we want to add a new "wagon". All we need is to find where we want to add it, connect the previous and the next wagon into the new one.
In other words, linked lists are all about creating and modifying connections between nodes.
In the next section, we'll step-by-step implement all those additions and removals and you'll that it's a relatively simple concept.
Before any implementation, let's take a look in the API we'll need for this kind of list:
-
.append(element)- method used to append a new element to the end of the list; -
.indexOf(element)- method used to known where in the index our element was added; -
.insertAt(position, element)- method used to add an element in a specific position; -
.remove(element)- method used to remove an element from the list; -
.removeAt(position)- method used to remove an element in some specific position; -
.toString()- method used to have an overview of our list.
Once again, instead using JS classes/prototype, I'm going to use my favorite pattern Factory with some placeholders for our API already:
function LinkedListFactory() {
return {
append,
indexOf,
insertAt,
remove,
removeAt,
toString,
};
function append(element) {}
function indexOf(element) {}
function insertAt(position, element) {}
function remove(element) {}
function removeAt(position) {}
function toString() {}
}Before implementing the methods, we'll need to create 2 variables that will be used in almost all methods:
-
head- variable to hold our very first element, where everything will start. It'll start with the valuenull; -
length- a control variable to easily hold the list size. It'll start with the value0.
function LinkedListFactory() {
let head = null;
let length = 0;
return {
append,
indexOf,
insertAt,
remove,
removeAt,
toString,
};
function append(element) {}
function indexOf(element) {}
function insertAt(position, element) {}
function remove(element) {}
function removeAt(position) {}
function toString() {}
}In the append method, we first need to create an internal basic structure which we can call "node".
A node is a simple object which will hold the element we're adding to the list and the next element (the link itself).
Since append will always add an element to the end of the list, next will always be null:
function append(element) {
const node = {
element,
next: null
}
}The first scenario is when our list is empty, or, when head is null. For this case, we'll assign our newly created node to the head:
function append(element) {
const node = {
element,
next: null,
};
if (head === null) {
head = node;
}
}Now, we have to consider the other cases (if not head or second to last node case).
Since we want to append an element to the end of our list, we have to iterate through all nodes until .next equal to null.
function append(element) {
const node = {
element,
next: null,
};
if (head === null) {
head = node;
} else {
let currentNode = head;
while (currentNode.next !== null) {
currentNode = currentNode.next;
}
}
}Now that we encountered the last element, all we need to do is link the .next property of this element to our newly created node:
function append(element) {
const node = {
element,
next: null,
};
if (head === null) {
head = node;
} else {
let currentNode = head;
while (currentNode.next !== null) {
currentNode = currentNode.next;
}
currentNode.next = node;
}
}Finally, we'll need, for both cases (head or not), increment 1 to our list size (length) so it's important to be outside the condition
function append(element) {
const node = {
element,
next: null,
};
if (head === null) {
head = node;
} else {
let currentNode = head;
while (currentNode.next !== null) {
currentNode = currentNode.next;
}
currentNode.next = node;
}
length++;
}
This method is meant to find where a given element is placed in our list.
First, we'll need two controller variables: nodeIndex and currentElement. The first will be used as return value but also to know where we are in the iteration and the second to do the comparison if the element is the one we're looking for:
function indexOf(element) {
let nodeIndex = 0;
let currentNode = head;
}Remember when I told you that head might be null or the .next of the last node will be null? We'll use this condition to loop through all nodes.
function indexOf(element) {
let nodeIndex = 0;
let currentNode = head;
while (currentNode) {
if (element === currentNode.element) {
return nodeIndex;
}
nodeIndex++;
currentNode = currentNode.next;
}
}Now, until currentNode is not null, we'll first check if the element is the one we're looking for. If so, we can straight return the value of nodeIndex.
If not, then we'll need to increment 1 to nodeIndex and assign currentNode to currentNode.next, or in other words, simply moving to the next node to run the comparison over again.
Finally, if we can't find the element the user is looking for, we have to give an indication we couldn't.
Traditionally, for cases like that such methods return -1 but nothing stops us of returning other value like null for example:
function indexOf(element) {
let nodeIndex = 0;
let currentNode = head;
while (currentNode) {
if (element === currentNode.element) {
return nodeIndex;
}
nodeIndex++;
currentNode = currentNode.next;
}
return -1
}In this operation, we'll do a similar operation as we did for indexOf (controlling the index) plus we'll have to tweak the node connections.
Imagine the following scenario: we have 4 nodes linked in our list and we want to insert a new element in position 2 (second position because it's a 0-based index).
We basically will need:
- Loop through the nodes;
- Find who is in the position 2;
- make this node
.nextpoint to the element we're inserting - make our new node
.nextpoint to the element we just found.next
It might seem a lit bit confusing but I'll drive you step-by-step in the implementation itself.
The first validation we need to do is if the position the user is asking to add exists in our list. We need to ensure the if we don't add an element in the position 4 if we only have 1 element in our list:
function insertAt(position, element) {
const isPositionInTheRange = position > -1 && position <= length;
if(!isPositionInTheRange){
return false
}
}Tip: the variable which holds this logic is just a semantic way of describing (in English) a condition.
Like in the other methods, we'lll need to iterate over our list to see where we need to add this element. This means we'll need to create a controller variable and our node:
function insertAt(position, element) {
const isPositionInTheRange = position > -1 && position <= length;
if(!isPositionInTheRange){
return false
}
// Our brand new node
const node = {
element,
next: null
}
// Controller to iterate over the list
let currentNode = head;
}Our first case here is that the user wants to add an element at the first position (head). All we need to do is to say that the new node .next will be the current element and the head now will be the new node:
function insertAt(position, element) {
const isPositionInTheRange = position > -1 && position <= length;
if (!isPositionInTheRange) {
return false;
}
const node = {
element,
next: null,
};
let currentNode = head;
const isHeadPosition = position === 0;
if (isHeadPosition) {
// Assign currentNode (head) to `node.next`
node.next = currentNode;
// Replace the current head with this node
head = node;
} else {
}
}
Now we need to handle the case where the position is after the head.
First, we'll need 2 controller variables, index (for iterate based on that) and previousNode (for re-create the links when we find the position):
function insertAt(position, element) {
const isPositionInTheRange = position > -1 && position <= length;
if (!isPositionInTheRange) {
return false;
}
const node = {
element,
next: null,
};
let currentNode = head;
const isHeadPosition = position === 0;
if (isHeadPosition) {
node.next = currentNode;
head = node;
} else {
let previousNode = null;
let index = 0;
}
}Then, we'll iterate using index. While index is less then the desired position, we'll update our controllers previousNode and currentNode:
function insertAt(position, element) {
const isPositionInTheRange = position > -1 && position <= length;
if (!isPositionInTheRange) {
return false;
}
const node = {
element,
next: null,
};
let currentNode = head;
const isHeadPosition = position === 0;
if (isHeadPosition) {
node.next = currentNode;
head = node;
} else {
let previousNode = null;
let index = 0;
while (index++ < position){
previousNode = currentNode;
currentNode = currentNode.next;
}
}
}Remember: index++ will first evaluate the number and only then increment 1.
This step is only necessary to walk through our list until the position matches the one we want to change.
When we reach that, all we need to do is re-do the links between the previousNode <-> new node <-> currentNode:
function insertAt(position, element) {
const isPositionInTheRange = position > -1 && position <= length;
if (!isPositionInTheRange) {
return false;
}
const node = {
element,
next: null,
};
let currentNode = head;
const isHeadPosition = position === 0;
if (isHeadPosition) {
node.next = currentNode;
head = node;
} else {
let previousNode = null;
let index = 0;
while (index++ < position){
previousNode = currentNode;
currentNode = currentNode.next;
}
previousNode.next = node;
node.next = currentNode;
}
}
Finally, we need to add +1 in our list length, not matter where in the list it was inserted and return true to inform for the user that the operation succeeded:
function insertAt(position, element) {
const isPositionInTheRange = position > -1 && position <= length;
if (!isPositionInTheRange) {
return false;
}
const node = {
element,
next: null,
};
let currentNode = head;
const isHeadPosition = position === 0;
if (isHeadPosition) {
node.next = currentNode;
head = node;
} else {
let previousNode = null;
let index = 0;
while (index++ < position){
previousNode = currentNode;
currentNode = currentNode.next;
}
previousNode.next = node;
node.next = currentNode;
}
length++;
return true;
}The removeAt method has a very similar implementation as we just saw in the insertAt, we'll need to:
- iterate over the list;
- find the correspondent element in that position;
- connect the previous element into the next;
- decrease the list size
Starting, once again let's first validate if the request position contains an element:
function removeAt(position){
const isPositionInTheRange = position > -1 && position < length;
if(!isPositionInTheRange){
return null
}
}Then, we need to create controller variable currentNode to iterate through:
function removeAt(position){
const isPositionInTheRange = position > -1 && position < length;
if(!isPositionInTheRange){
return null
}
let currentNode = head;
}Again we'll have 2 situations: head or not head. If head, all we need to do is to reassign head to be the currentNode (in this case the head element itself) to it's .next value:
function removeAt(position){
const isPositionInTheRange = position > -1 && position < length;
if(!isPositionInTheRange){
return null
}
let currentNode = head;
if(position === 0){
head = currentNode.next;
}
}
In case you're not aware, by just removing all references from this element the garbage collector will understand that it is no longer needed and prune it from the memory.
Now, we need to remove elements which are not the head. For that, let's create two other controller variables, index and previousNode:
function removeAt(position){
const isPositionInTheRange = position > -1 && position < length;
if(!isPositionInTheRange){
return null
}
let currentNode = head;
if(position === 0){
head = currentNode.next;
} else {
let index = 0;
let previousNode = null;
}
}And once again, iterate over all elements until we reach the position we want to:
function removeAt(position){
const isPositionInTheRange = position > -1 && position < length;
if(!isPositionInTheRange){
return null
}
let currentNode = head;
if(position === 0){
head = currentNode.next;
} else {
let index = 0;
let previousNode = null;
while(index++ < position){
previousNode = currentNode;
currentNode = currentNode.next
}
}
}Now, we recreate the node links by linking previousNode.next into the currentNode.next:
function removeAt(position){
const isPositionInTheRange = position > -1 && position < length;
if(!isPositionInTheRange){
return null
}
let currentNode = head;
if(position === 0){
head = currentNode.next;
} else {
let index = 0;
let previousNode = null;
while(index++ < position){
previousNode = currentNode;
currentNode = currentNode.next
}
previousNode.next = currentNode.next;
}
}
And finally, we need to subtract 1 from the list length and return the element we're removing so the user can do something with it:
function removeAt(position){
const isPositionInTheRange = position > -1 && position < length;
if(!isPositionInTheRange){
return null
}
let currentNode = head;
if(position === 0){
head = currentNode.next;
} else {
let index = 0;
let previousNode = null;
while(index++ < position){
previousNode = currentNode;
currentNode = currentNode.next
}
previousNode.next = currentNode.next;
}
length--;
return currentNode.element;
}This method will be quite simple to implement. That's because we already have a method which find an index from an element (indexOf) and also have a method to remove an element from a position (removeAt):
function remove(element){
const elementIndex = indexOf(element);
return removeAt(elementIndex);
}This method is purely to give to whoever is using this linked list the notion of all elements present in the list.
Once again we'll need to navigate through all nodes and concatenate the element value into a string:
function toString() {
let result = "";
let current = head;
while (current) {
result += `${current.element}${current.next ? ", " : ""}`;
current = current.next;
}
return result;
}Obs.: This will work only for primitive values. If you want to support elements as
objects,functions, etc. you'll need to enhance the concatenation and data parsing.
function LinkedListFactory() {
let head = null;
let length = 0;
return {
append,
indexOf,
insertAt,
remove,
removeAt,
toString,
};
function append(element) {
const node = {
element,
next: null,
};
if (head === null) {
head = node
} else {
let currentNode = head;
while (currentNode.next !== null) {
currentNode = currentNode.next;
}
currentNode.next = node;
}
length++;
}
function indexOf(element) {
let nodeIndex = 0;
let currentNode = head;
while (currentNode) {
if (element === currentNode.element) {
return nodeIndex;
}
nodeIndex++;
currentNode = currentNode.next;
}
return -1;
}
function insertAt(position, element) {
const isPositionInTheRange = position > -1 && position <= length;
if (!isPositionInTheRange) {
return false;
}
const node = {
element,
next: null,
};
let currentNode = head;
const isHeadPosition = position === 0;
if (isHeadPosition) {
node.next = currentNode;
head = node;
} else {
let previousNode = null;
let index = 0;
while (index++ < position) {
previousNode = currentNode;
currentNode = currentNode.next;
}
previousNode.next = node;
node.next = currentNode;
}
length++;
return true;
}
function removeAt(position) {
const isPositionInTheRange = position > -1 && position < length;
if (!isPositionInTheRange) {
return null;
}
let currentNode = head;
if (position === 0) {
head = currentNode.next;
} else {
let index = 0;
let previousNode = null;
while (index++ < position) {
previousNode = currentNode;
currentNode = currentNode.next;
}
previousNode.next = currentNode.next;
}
length--;
return currentNode;
}
function removeAt(position) {
const isPositionInTheRange = position > -1 && position < length;
if (!isPositionInTheRange) {
return null;
}
let currentNode = head;
if (position === 0) {
head = currentNode.next;
} else {
let index = 0;
let previousNode = null;
while (index++ < position) {
previousNode = currentNode;
currentNode = currentNode.next;
}
previousNode.next = currentNode.next;
}
length--;
return currentNode.element;
}
function remove(element) {
const elementIndex = indexOf(element);
return removeAt(elementIndex);
}
function toString() {
let result = "";
let current = head;
while (current) {
result += `${current.element}${current.next ? ", " : ""}`;
current = current.next;
}
return result;
}
}
const linkedList = LinkedListFactory();
linkedList.append(1);
linkedList.append(10);
linkedList.append(-1);
linkedList.append(40);
linkedList.append(-123);
console.log(linkedList.toString()); // 1, 10, -1, 40, -123
console.log(linkedList.removeAt(3)); // 40
console.log(linkedList.toString()); // 1, 10, -1, -123
console.log(linkedList.indexOf(1)); // 0
console.log(linkedList.remove(1)); // 1
console.log(linkedList.toString()); // 10, -1, -123I hope I could explain to you what's linked list about and how to simply implement one.
There are also two variants of it: "doubly linked" (next and previous link) and circular, but I think it'll be better in another article.
Again, because we're in a JS environment I don't see a strong usage to it but it's important to know that exists in case we get in contact with it in other languages.
If you have any comments on that, please tweet me so we can build knowledge together!
Cheers.
24