Key takeaways
A linked list consists of nodes, each containing a value and a reference to the next node, allowing dynamic size management compared to arrays.
Common operations include appending, prepending, inserting at specific indices, and deleting nodes.
Implement methods like
toArray()
to convert the linked list to an array for easier processing and display.Enhance linked list functionality with methods for checking size, emptiness, and searching for nodes by value.
In JavaScript, creating a linked list is quite simple. A data structure called a linked list comprises a series of entries, each of which points to the element after it in the sequence. Linked lists are more dynamic and don’t have a set size like arrays.
We will use two classes: the LinkedList
class is used to manage the linked list, and Node
class is used to represent individual list components. The LinkedList
class has methods to search for nodes by value, delete nodes based on their value, append nodes to the end of the list, and convert the linked list to an array for simple manipulation and display.
We'll explore various operations that can be performed on a linked list using JavaScript classes. In this Answer, we'll delve into the details of appending nodes to extend the list, prepending nodes to add elements at the beginning, and deleting nodes based on their values.
Let's look at how we are going to add a node in the linked list below:
// Node classclass Node {constructor(value) {this.value = value;this.nextNode = null;}}// Linked List classclass LinkedList {constructor() {this.headNode = null; // The first node in the listthis.tailNode = null; // The last node in the list}// Add a node at the endappend(value) {const newNode = new Node(value);if (!this.headNode) {this.headNode = newNode;this.tailNode = newNode;} else {this.tailNode.nextNode = newNode;this.tailNode = newNode;}}// Add a node at the startprepend(value) {const newNode = new Node(value);newNode.nextNode = this.headNode;this.headNode = newNode;if (!this.tailNode) {this.tailNode = newNode;}}// Add a node at a specified indexinsertAt(value, index) {if (index < 0) {throw new Error("Index out of bounds");}const newNode = new Node(value);if (index === 0) {this.prepend(value);return;}let currentNode = this.headNode;let currentIndex = 0;while (currentNode && currentIndex < index - 1) {currentNode = currentNode.nextNode;currentIndex++;}if (!currentNode) {throw new Error("Index out of bounds");}newNode.nextNode = currentNode.nextNode;currentNode.nextNode = newNode;if (!newNode.nextNode) {this.tailNode = newNode;}}// Convert a linked list to JS arraytoArray() {const resultArray = [];let currentNode = this.headNode;while (currentNode) {resultArray.push(currentNode.value);currentNode = currentNode.nextNode;}return resultArray;}}// Example usageconst customList = new LinkedList();customList.append(100);customList.append(200);customList.append(300);console.log("original linkedlist");console.log(customList.toArray()); // Output: [100, 200, 300]customList.append(400);console.log("element added at the end");console.log(customList.toArray()); // Output: [100, 200, 300, 400]customList.prepend(50);console.log("element added at node 0");console.log(customList.toArray()); // Output: [50, 100, 200, 300, 400]customList.insertAt(150, 2);console.log("Element added at index 2:");console.log(customList.toArray()); // Output: [50, 100, 150, 200, 300, 400]
Let's break down the code written above:
Lines 2–7: We are defining a Node
class. Each Node
has two properties: value
to store the actual data and nextNode
to reference the next node in the sequence. Initially, nextNode
is set to null
.
Line 10: We are defining and creating a LinkedList
class with multiple methods. It is one of the main classes and it manages the nodes, allowing you to create, modify, and traverse the list.
Lines 11–14: The LinkedList
class has a constructor that initializes two properties: headNode
and tailNode
. These properties represent the first and last nodes of the list, respectively. Initially, when a linked list is created, both headNode
and tailNode
are set to null
, indicating an empty list.
Line 17: We define an append
method. The append(value)
method is used to add a new node to the end of the linked list. It creates a new Node
with the provided value
.
Lines 19–21: If the list is empty (i.e., headNode
is null
), the new node becomes both the headNode
and the tailNode
.
Lines 22–25: If the list is not empty, the new node is linked to the current tailNode
and the tailNode
is updated to the new node.
Line 29: We define the prepend
method. The prepend(value)
method adds a new node to the beginning of the linked list.
Line 30: It creates a new newNode
with the provided value
.
Lines 31–32: The new node is linked to the current headNode
and then it becomes the new headNode
.
Lines 33–35: If the list was empty, the new node also becomes the tailNode
.
Lines 38–69: We are writing a function InsertAt
to insert at a specific index in our linked list.
Lines 40–42: We first check if the provided index is less than 0
. If it is, it throws an error because the index is out of bounds.
Lines 46–48: If the index is 0
, it calls the prepend
method to add the node at the beginning of the list.
Lines 51–57: Then we initialize currentNode
to headNode
and currentIndex
to 0. Then, it iterates through the list to find the node just before the specified index.
Lines 59–61: After the loop, if currentNode
is null
, it means the index was out of bounds and it throws an error.
Lines 63–64: The nextNode
property of the new node is set to the node currently at the specified index. Then, the nextNode
property of the node at index - 1
is updated to the new node.
Lines 66–68: If the new node is inserted at the end of the list, update the tailNode
to be the new node.
Let's look at how we are going to delete an element from the linked list below:
// Node classclass Node {constructor(value) {this.value = value;this.nextNode = null;}}// Linked List classclass LinkedList {constructor() {this.headNode = null; // The first node in the listthis.tailNode = null; // The last node in the list}// Add a node at the endappend(value) {const newNode = new Node(value);if (!this.headNode) {this.headNode = newNode;this.tailNode = newNode;} else {this.tailNode.nextNode = newNode;this.tailNode = newNode;}}// Add a node at the startprepend(value) {const newNode = new Node(value);newNode.nextNode = this.headNode;this.headNode = newNode;if (!this.tailNode) {this.tailNode = newNode;}}// Delete a nodedelete(value) {if (!this.headNode) {return;}if (this.headNode.value === value) {this.headNode = this.headNode.nextNode;if (!this.headNode) {this.tailNode = null;}return;}let currentNode = this.headNode;while (currentNode.nextNode) {if (currentNode.nextNode.value === value) {currentNode.nextNode = currentNode.nextNode.nextNode;if (!currentNode.nextNode) {this.tailNode = currentNode;}return;}currentNode = currentNode.nextNode;}}// Convert a linked list to JS arraytoArray() {const resultArray = [];let currentNode = this.headNode;while (currentNode) {resultArray.push(currentNode.value);currentNode = currentNode.nextNode;}return resultArray;}}// Example usageconst customList = new LinkedList();customList.append(100);customList.append(200);customList.append(300);customList.prepend(50);console.log("original linkedlist");console.log(customList.toArray()); // Output: [50, 100, 200, 300]customList.delete(200);console.log(customList.toArray()); // Output: [50, 100, 300]
Line 39: We create the delete
method. The delete(value)
method removes a node with the specified value
from the linked list.
Lines 40–42: It first checks if the list is empty (i.e., head
is null
) and, if so, returns without any action.
Lines 43–49: If the node to be deleted is the headNode
, it simply updates the headNode
to the next node. If the node to be deleted is also the tailNode
, it updates the tailNode
.
Lines 50–60: It iterates through the list, finds the node to delete, and updates the next
reference of the previous node to skip the node to be deleted. Lines 54–56 are responsible for updating the tailNode
reference when deleting a node from the linked list.
Line 76: We define a toArray
method. The toArray()
method converts the linked list into a regular JavaScript array for easy display or further processing.
Lines 79–84: These iterate through the list and collect the value
from each node in an array.
Let's look at some of the other operations, like getSize()
, isEmpty()
and find node by its value from the linked list below:
// Node classclass Node {constructor(value) {this.value = value;this.nextNode = null;}}// Linked List classclass LinkedList {constructor() {this.headNode = null; // The first node in the listthis.tailNode = null; // The last node in the listthis.size = 0; // Initialize size to 0}// Add a node at the endappend(value) {const newNode = new Node(value);if (!this.headNode) {this.headNode = newNode;this.tailNode = newNode;} else {this.tailNode.nextNode = newNode;this.tailNode = newNode;}this.size++; // Increment size}// Convert a linked list to JS arraytoArray() {const resultArray = [];let currentNode = this.headNode;while (currentNode) {resultArray.push(currentNode.value);currentNode = currentNode.nextNode;}return resultArray;}// Get the size of the linked listgetSize() {return this.size;}// Check if the linked list is emptyisEmpty() {return this.size === 0;}// Find a node by its valuefind(value) {let currentNode = this.headNode;while (currentNode) {if (currentNode.value === value) {return currentNode;}currentNode = currentNode.nextNode;}return null;}}// Example usageconst customList = new LinkedList();customList.append(100);customList.append(200);customList.append(300);console.log("Original linked list:");console.log(customList.toArray()); // Output: [100, 200, 300]console.log("Size of the linked list:", customList.getSize()); // Output: 3console.log("Is the linked list empty?", customList.isEmpty()); // Output: falseconst foundNode = customList.find(150);console.log("Found node:", foundNode ? foundNode.value : "Node not found"); // Output: Node not found
Lines 42–44: We are returning the size of the linked list.
Lines 47–49: We are checking whether the linked list is empty. If it is empty, then we are returning false
.
Lines 52–62: We are finding a node by its value. If the value exists in the linked list, then we return "Found node"
; otherwise, it returns "Node not found”
.
Implementing a linked list in JavaScript provides a fundamental understanding of data structures and their manipulation. By leveraging classes to manage nodes and perform operations like appending, prepending, and deleting, developers can create efficient and flexible data structures tailored to their specific needs.
Free Resources