Once you start exploring data structures outside of arrays, you’ll probably if not certainly bump into lists first.
A list is an abstract data type (a type for objects whose behaviour is defined by a set of value and a set of operations) that represents a countable number of ordered values, where the same value may occur more than once. Lists are basically containers, because they contain values/data that may appear more than once.
One of the most common implementation of lists abstractly is Linked Lists. A linked list is a linear data structure where each element (node) is a separate object. Each node is made up of two items; the data and a reference to the next node. There are different types of linked lists;
- Singly linked lists
- Doubly linked lists
- Circular linked lists
In this tutorial, we’ll be focusing on implementing the simplest of them, a Singly Linked List.
The diagram below shows a visual representation of a linked list. The list is made up of a number of nodes linked together. Each node has a Data field and a reference to the next node in the list, which we can call Next. This next reference creates a link between nodes and helps us iterate the list.
So how do we implement this data structure in javascript? First, we need to define what operations we want to perform and how these operations can effectively be used in the real world. We will take a look at the following operations;
- Inserting first node
- Inserting last node
- Inserting node at a specified position
- Retrieving node at a specified position
- Removing node at a specified position
- Destroying the linked list
- Printing all nodes
Let’s define the structure our Node class. Each node has a data and a next field. We set next to null by default since there could be only one element in our linked list and/or the tail node, which will always have a null next field.
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
Next we will define our LinkedList class. This is where we will implement all the operations mentioned above.
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
}
We initiate the fields head and size. We want to keep track of the head node and the size of the entire linked list. The same concept of size in arrays can also be used here, where we count the number of items in an array from index zero.
Insert First Node
Within our LinkedList class, let’s define a method insertFirstNode. Here, we will simply initiate our list with a node. We know for sure the list is empty so we set our node as the head.
You may never really have to actually insert a first node. You’ll most likely insert node at an index position. This method is a good example for easing into the upcoming actions.
// LinkedList.js
insertFirstNode(data) {
this.head = new Node(data, this.head);
this.size++;
}
Insert Last node
// LinkedList.js
insertLastNode(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
} else {
let currentNode = this.head;
while (currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = newNode;
}
this.size++;
}
This method, will insert a node at the end of the linked list. We will create a new node and check if a head node exists. If it doesn’t exist, we set the head to the new node (because the list is empty). If there’s a head, we’ll assume there are other nodes and loop till we get to the end of the linked list. Once we reach the end, we’ll set the this.next field of the current node (last node) to the new node we are inserting.
So, while this.next is true, set the current node to the next node. Once the loop is over, set the next node of the current node to the new node.
Insert Node at a Specified Position
//LinkedList.js
insertNodeAtIndex(data, index) {
if (this.size < index) {
console.log("index is greater than size of list");
return;
}
const node = new Node(data);
if (!this.head) {
this.head = node;
} else if (index === 0) {
const head = this.head;
this.head = node;
node.next = head;
} else {
let previousNode;
let currentNode = this.head;
let indexCounter = 0;
while (indexCounter < index) {
previousNode = currentNode;
currentNode = previousNode.next;
indexCounter++;
}
previousNode.next = node;
node.next = null;
if (currentNode) {
node.next = currentNode;
}
}
this.size++;
}
First we check if the the index number provided is larger than the total size of the linked list. If this is the case, we have an invalid operation and will exit.
We create a new node with the data given and first take care of two special cases;
- If there is no head node we simply set the our node to the head and increase the size of the list.
- If the given index is
0we replace the current head in the list with our node.
Else, we need to loop through the list till we get to the given index/position. We keep track of the previous and current nodes. When we arrive at the desired index, we set the next field of the previous node to our new node, and the next field of our new node the current node. We increase the size of the linked list. This also works for inserting a node at the end of list. In which case, current node will be null, and our new node will be the tail.
Retrieve Node at a Specified Position
// LinkedList.js
getNodeAtIndex(index) {
if (index > this.size) {
console.log("index is greater than size of list");
return;
}
let currentNode = this.head;
let counter = 0;
while (counter < index) {
currentNode = currentNode.next;
counter++;
}
console.log(`Node data at index(${index}) is ${currentNode.data}`);
}
Now that we know how to loop through a linked list, the rest of the implementation will be easier. To retrieve a node at a specified index, all we need to do is loop through the linked list till we get to the specified position. We keep track of the `current node` which will be returned at the end of the loop. I log my values to the console, but you can easily return them in your implementation.
Remove Node at a Specified Position
// LinkedList.js
removeNodeAtIndex(index) {
if (index > this.size) {
console.log("index is greater than size of list");
return;
}
if (!this.head) {
console.log("List is empty");
return;
}
if (index === 0) {
this.head = null;
} else {
let previousNode;
let currentNode = this.head;
let counter = 0;
while (counter < index) {
previousNode = currentNode;
currentNode = previousNode.next;
counter++;
}
if (currentNode.next) {
previousNode.next = currentNode.next;
} else {
previousNode.next = null;
}
}
this.size--;
console.log(
`Removed node at index(${index}) and current linked list is: })`
);
}
We will follow the same principle above to get to the specified index. We keep track of the previous node and current node. To remove the node, we set the next field of the previous node to the next node of our current node. Current node is the node we want to remove. We reduce the size of the list.
Destroy/Clear the Linked List
// LinkedList.js
clear() {
//for each of the nodes, remove at index
let index = 0;
while (index < this.size) {
console.log(`removing at index: ${index}`);
this.removeNodeAtIndex(index);
this.size--;
index++;
}
}
To clear the list, we can reuse our removeNodeAtIndex() method. We loop through the list, given the size, and call removeNodeAtIndex() . We decrease the size of the list as we loop through, or you could also set the size to zero outside the loop.
Printing All Nodes
Finally, we will implement a method to print all nodes. This is probably the easiest implementation since we only loop through the list and print.
// ListNode.js
printListData() {
let currentNode = this.head;
while (currentNode) {
console.log(currentNode.data);
currentNode = currentNode.next;
}
}
Manually Testing Our Code
We can test the above implementation by creating a LinkedList and calling the methods defined.
const linkedList = new LinkedList(); linkedList.insertFirstNode(5); linkedList.insertFirstNode(8); linkedList.insertLastNode(2); linkedList.insertFirstNode(90); linkedList.insertNodeAtIndex(34, 1); linkedList.insertNodeAtIndex(57, 4); linkedList.printListData(); linkedList.getNodeAtIndex(4); linkedList.removeNodeAtIndex(2); linkedList.printListData(); linkedList.clear(); linkedList.printListData();
The above test returns the following results;
90 34 8 5 57 2 Node data at index(4) is 57 Removed node at index(2) and current linked list is: }) 90 34 5 57 2 removing at index: 0 Removed node at index(0) and current linked list is: }) removing at index: 1 List is empty
And there you have it. I hope this implementation helped you understand Linked Lists much better. Thanks for reading!