Introduction
A linked list is a data structure that consists of a group of nodes that together represent a sequence. Each node in a linked list contains data and a reference to the next node in the sequence. This allows for the efficient insertion and removal of elements from any position in the sequence.
In this article, we will explain how we can implement a linked list in JavaScript.
Creating Linked List in JavaScript
In JavaScript, a linked list can be implemented using objects and arrays. Each node in the list can be represented as an object, with the data and the reference to the next node in the sequence being stored as properties. For example, the following code creates a linked list with three nodes:
let node1 = {
data: "node1 data",
next: null,
};
let node2 = {
data: "node2 data",
next: node1,
};
let node3 = {
data: "node3 data",
next: node2,
};
console.log(node3);
Output
{
data: 'node3 data',
next: { data: 'node2 data', next: { data: 'node1 data', next: null } }
}
In this code, the node1
object contains the data "node1 data" and a reference to null
, indicating that it is the last node in the sequence. The node2
object contains the data "node2 data" and a reference to node1
, indicating that it is the second-to-last node in the sequence. Similarly, the node3
object contains the data "node3 data" and a reference to node2
, indicating that it is the first node in the sequence.
Accessing Linked List in JavaScript
To access the elements of the linked list, you can use a loop to iterate over the nodes. For example, the following code uses a while
loop to print the data of each node in the linked list:
let currentNode = node3;
while (currentNode != null) {
console.log(currentNode.data);
currentNode = currentNode.next;
}
Output
node3 data
node2 data
node1 data
In this code, the currentNode
variable is initialized to node3
, which is the first node in the linked list. The while
loop then runs until the currentNode
variable is null
, indicating that there are no more nodes in the sequence. In each iteration of the loop, the data
property of the currentNode
object is printed to the console, and then the currentNode
variable is updated to the next
node in the sequence.
Using the class
approach
There are several approaches to using linked lists in JavaScript. One approach is to create a linked list class, which provides methods for inserting and removing nodes from the sequence. For example, the following code defines a LinkedList
class with add()
and remove()
methods:
class LinkedList {
constructor() {
this.head = null;
}
add(data) {
let newNode = {
data: data,
next: this.head,
};
this.head = newNode;
}
remove(data) {
let currentNode = this.head;
let previousNode = null;
while (currentNode != null) {
if (currentNode.data === data) {
if (previousNode != null) {
previousNode.next = currentNode.next;
} else {
this.head = currentNode.next;
}
return true;
}
previousNode = currentNode;
currentNode = currentNode.next;
}
return false;
}
}
In this code, the LinkedList
class has a constructor()
method that initializes the head
property to null
, indicating that the linked list is empty. The add()
method accepts a data
argument, which is the data that should be stored in the new node. The method creates a new node object with the data
property set to the data
argument, and the next
property set to the current head
of the linked list. The newNode
object is then assigned as the new head
of the linked list.
The remove()
method also accepts a data
argument, which is the data of the node that should be removed from the linked list. The method first initializes the currentNode
and previousNode
variables to the head
of the linked list. The while
loop then iterates over the nodes in the linked list, until the currentNode
is null
. In each iteration, the method checks if the data
property of the currentNode
object is equal to the data
argument. If it is, the currentNode
object is removed from the linked list by updating the next
property of the previousNode
object to point to the next
node in the sequence. If the currentNode
object is the head
of the linked list, then the head
property is updated to the next
node in the sequence.
To use the LinkedList
class, you can create an instance of the class and call the add()
and remove()
methods on the instance. For example, the following code creates a LinkedList
instance, adds some nodes to the list, and then removes a node from the list:
let list = new LinkedList();
list.add("node1 data");
list.add("node2 data");
list.add("node3 data");
list.remove("node2 data");
console.log(list);
Output
LinkedList {
head: { data: 'node3 data', next: { data: 'node1 data', next: null } }
}
In this code, the list
variable is initialized to a new LinkedList
instance. The add()
method is then called three times, passing in the data for each node that should be added to the linked list. Finally, the remove()
method is called, passing in the data of the node that should be removed from the list.
Using a utility function approach
Another approach to using linked lists in JavaScript is to create a utility function that generates a linked list from an array of data. For example, the following code defines a createLinkedList()
function that takes an array of data and returns a linked list containing the data from the array:
function createLinkedList(dataArray) {
let head = null;
for (let i = dataArray.length - 1; i >= 0; i--) {
let newNode = {
data: dataArray[i],
next: head,
};
head = newNode;
}
return head;
}
In this code, the createLinkedList()
function accepts an array of data as its only argument. The function then iterates over the data array in reverse order, creating a new node object for each element in the array. The newNode
object is then assigned as the new head
of the linked list. Finally, the function returns the head
of the linked list.
To use the createLinkedList()
function, you can call the function and pass in an array of data as the argument. For example, the following code creates a linked list from an array of numbers, and then uses a while
loop to print the data of each node in the linked list:
let numbers = [1, 2, 3, 4, 5];
let list = createLinkedList(numbers);
let currentNode = list;
while (currentNode != null) {
console.log(currentNode.data);
currentNode = currentNode.next;
}
Output
1
2
3
4
5
In this code, the numbers
array contains the data that should be stored in the linked list. The createLinkedList()
function is called, passing in the numbers
array as the argument. The currentNode
variable is initialized to the head
of the linked list returned by the createLinkedList()
function. The while
loop then iterates over the nodes in the linked list, printing the data
property of each node to the console.
Using a utility function to create a linked list from an array of data can be useful when you have a large amount of data that you want to store in a linked list. It allows you to easily create a linked list from the data, without having to manually create each node and link it to the next node in the sequence.
Summary
There are several ways to use linked lists in JavaScript. You can create a linked list class with methods for inserting and removing nodes, or you can create a utility function that generates a linked list from an array of data. Whether you choose to use a class or a utility function, linked lists can be a useful data structure for managing and organizing data in your JavaScript programs.
References
Classes - JavaScript | MDN (mozilla.org)
Object.prototype.constructor - JavaScript | MDN (mozilla.org)