Today we are going to implement a (Singly) Linked List data structure in JavaScript 🥳
What is a linked list?
In layman's terms, a linked list is a list of nodes, where each node holds two things:
- A value
- A pointer to the next node in the list.
The first node of the list is called 'head'.
The last node of the list is called 'tail'.
Head and tail are not separate nodes. They are just references to the first and last node in the list, respectively.
The last node of the list points to
null
. If the list is empty, then both head and tail point tonull
.
Creating a linked list in JavaScript
To define our linked list data structure, we are going to create a class
. We initialize head
and tail
references as null
. We also define some methods (append
, prepend
, delete
, getFirst
, getLast
and toArray
).
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
}
append() {}
prepend() {}
delete() {}
getFirst() {}
getLast() {}
toArray() {}
}
Append
Appends a node to the end of the list.
We create a new node object with 2 properties:
- A
value
property holding the provided value. - A
next
property pointing to the next node, which in this case isnull
, since we append (it's the last node in the list).
We then check if there is a tail
node and update it to point to the newly appended one. We implement an if
check, because in case the list is empty (when appending the first node), then tail
is and should be null
, because there is no next node to point to.
After this, we set the newly appended node as tail
.
Lastly, we check if head
reference is null
, which it is when first creating the list and set the newly appended node as head
.
And there you have it, a method to append new nodes to our linked list data structure!
append(value) {
// New node object
const newNode = {
value,
next: null
};
// Updating the previous tail node (last node) to point to the newly appended node
if (this.tail) {
this.tail.next = newNode;
}
// Setting the newly appended node as tail
this.tail = newNode;
// Setting the newly appended node as head, only if there is no head
if (!this.head) {
this.head = newNode;
}
}
Prepend
Prepends a node to the beginning of the list.
This method, like the previous one, is going to accept the value to be prepended. The implementation is simple:
We create a new node object with the provided value, but instead of setting next
property to null
like in the append
method, we set it to point to the currently first node (head
).
Then, we set the new node as head
, since it now sits at the beginning of our list and finally we check if tail is pointing to null
as we did before, so that we set it to point to the new node (in case we use prepend to add a node to an empty list).
prepend(value) {
// New node object, with pointing to the current head
const newNode = {
value,
next: this.head,
};
// Setting the newly prepended node as head
this.head = newNode;
// Setting the newly appended node as tail, only if there is no tail
if (!this.tail) {
this.tail = newNode;
}
}
Pretty straightforward, right? Let's now look at how we could implement a delete
method.
Delete
Deletes all nodes with a certain value
This is going to be a tad more complex. But stay with me, once you own the core logic, you are going to achieve a deeper understanding on how linked lists work :)
The logic is the following:
- If there is no
head
, just returnnull
, since the list is empty. - Create a current node reference, initialized with the
head
node. - Loop through all nodes in the list, find those that contain a certain value and "delete" them, by pointing their previous node's index to their next node, like this:
- At the end of each loop, increment current node reference, by setting it to the next one.
- Special handling for
head
andtail
nodes deletion, as discussed below.
We are first going to handle two cases: Empty list and head
deletion. We delete the head
node, by simply setting the next node as head
.
NOTE: A while
loop is used, because we need to find and delete all elements containing a certain value, not just the first occurence. In case we delete the head
and the new head
also qualifies for deletion, we should also delete that too. The same of course applies for each consecutive node, so a while
loop helps us with that.
delete(value) {
// If head is missing, the list is empty, therefore return null
if (!this.head) {
return null;
}
// Update head, by setting current head value to the next node
while (this.head && this.head.value === value) {
this.head.next;
}
}
The core deletion logic is the following:
-
Loop through all nodes, as long as their
next
property is notnull
(which is going to happend when we traverse thetail
). - If next node qualifies for deletion, set current node to point to the node following the next node.
- In any other case just increment the current node reference, simply by reassigning it to the next node.
// Initializing currentNode reference as current head
let currentNode = this.head;
// Loop through every node that points to another one
while (currentNode.next) {
// Checking whether next node's value qualifies for deletion
if (currentNode.next.value === value) {
// Set current node's next property to next node's next property,
// effectively leaving no node pointing to the next node (node in the 'middle')
currentNode.next = currentNode.next.next;
}
// If node doesn't qualify for deletion, set current node to the next one
else {
currentNode = currentNode.next;
}
}
Finally handle tail
node deletion like this:
// Update tail, by setting current tail value to the last non-deleted node
if (this.tail.value === value) {
this.tail = currentNode;
}
Our deletion code now should look like this:
delete(value) {
// If head is missing, the list is empty, therefore return null
if (!this.head) {
return null;
}
// Update head, by setting current head value to the next node
while (this.head && this.head.value === value) {
this.head.next;
}
// Initializing currentNode reference as current head
let currentNode = this.head;
// Loop through every node that points to another one
while (currentNode.next) {
// Checking whether next node's value qualifies for deletion
if (currentNode.next.value === value) {
// Set current node's next property to next node's next property,
// effectively leaving no node pointing to the next node (node in the 'middle')
currentNode.next = currentNode.next.next;
}
// If node doesn't qualify for deletion, set current node to the next one
else {
currentNode = currentNode.next;
}
}
// Update tail, by setting current tail value to the last non-deleted node
if (this.tail.value === value) {
this.tail = currentNode;
}
}
Getters
Return current head or tail node
Those methods are trivial, just return current head
and tail
:
getFirst() {
return this.head;
}
getLast() {
return this.tail;
}
toArray
Converts list to array
Finally, this method is going to convert our list to an Array
for visualization purposes 😎
We are essentially going to push every node Object
to an Array
and return it. I hope that the code is self-explaining:
toArray() {
const elements = [];
let currentNode = this.head;
while (currentNode) {
elements.push(currentNode);
currentNode = currentNode.next;
}
return elements;
}
Final code
This is our final LinkedList class
:
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
}
append(value) {
// New node object
const newNode = {
value,
next: null
};
// Updating the previous tail node (last node) to point to the newly appended node
if (this.tail) {
this.tail.next = newNode;
}
// Setting the newly appended node as tail
this.tail = newNode;
// Setting the newly appended node as head, only if there is no head
if (!this.head) {
this.head = newNode;
}
}
prepend(value) {
// New node object, with pointing to the current head
const newNode = {
value,
next: this.head
};
// Setting the newly prepended node as head
this.head = newNode;
// Setting the newly appended node as tail, only if there is no tail
if (!this.tail) {
this.tail = newNode;
}
}
delete(value) {
// If head is missing, the list is empty, therefore return null
if (!this.head) {
return null;
}
// Update head, by setting current head value to the next node
while (this.head && this.head.value === value) {
this.head.next;
}
// Initializing currentNode reference as current head
let currentNode = this.head;
// Loop through every node that points to another one
while (currentNode.next) {
// Checking whether next node's value qualifies for deletion
if (currentNode.next.value === value) {
// Set current node's next property to next node's next property,
// effectively leaving no node pointing to the next node (node in the 'middle')
currentNode.next = currentNode.next.next;
}
// If node doesn't qualify for deletion, set current node to the next one
else {
currentNode = currentNode.next;
}
}
// Update tail, by setting current tail value to the last non-deleted node
if (this.tail.value === value) {
this.tail = currentNode;
}
}
getFirst() {
return this.head;
}
getLast() {
return this.tail;
}
toArray() {
const elements = [];
let currentNode = this.head;
while (currentNode) {
elements.push(currentNode);
currentNode = currentNode.next;
}
return elements;
}
}
Linked List vs Array
Pros
- When using a Linked List, there is no need to specify its length in advance, which is the case when dealing with Arrays. That happens, because Arrays need a continuous area of allocated memory, whereas Linked Lists don't suffer from that constraint, simply because they use pointers to defined their nodes.
NOTE: However, JavaScript and most modern programming languages implement an abstract data type called 'Dynamic Arrays'. These are essentially automatically resizable arrays, that allow us to effeciently use them while writing code at a higher level. Under the hood, the underlying JavaScript engine creates a "real" Array which is typically bigger in size and accommodates all our values. When it gets full, a new one is created and all the old elements are copied over it.
- Another use case where Linked Lists shine is when we often add new elements at the beginning or anywhere except for the end of it. When using Arrays, you have to shift all elements to the right, in order to prepend or instert a new one, thus wasting lots of computing resources. When using a Linked List, you just need to change the previous node's pointer to point to the new node.
Cons
- Accessing elements in a LL is of O(n) time complexity (linear), whereas accessing elements in an Array is of O(1) time complexity (constant), provided that we know the index of the element we are trying to access, of course. This happens because in a LL we have to traverse every node until we find the one we are searching for.
Thanks for reading, hope I was clear enough. Feel free to provide feedback in case I missed something! 😊
Top comments (0)