Linked List in JavaScript: A Comprehensive Look
In the realm of data structures, the linked list occupies a prime position due to its flexibility and dynamic nature. But what exactly is it? Why is it preferred in some cases over the traditional array? Let’s dive deeper.
Understanding the Linked List:
A linked list is a collection of elements, termed as “nodes”, where each node is connected to the next one via a link. Each node in this list consists of two main parts:
- The data: The value or content the node is supposed to carry.
- The next: A pointer or reference to the next node in the sequence.
Linked lists are particularly valuable in situations where:
- Memory utilization needs to be optimized.
- The data set size is unpredictable.
- Insertions and deletions are frequent.
Anatomy of a Linked List:
Head: This is the starting point. The head is a reference to the first node in the list.
Tail: This is the endpoint. The tail is a reference to the last node in the list, and its ‘next’ property always points to null
, indicating the end of the list.
Crafting a Node in JavaScript:
class Node {
constructor(data, next = null) {
this.data = data; // The actual content of the node.
this.next = next; // Reference to the next node. 'null' by default.
}
}
Operation Explanations:
1. Adding a Node:
a. At the Beginning: This involves repositioning the current head to follow the new node.
function addAtBeginning(data) {
let newNode = new Node(data);
newNode.next = this.head;
this.head = newNode; // Reset the head to the new node.
}
b. At the End: This necessitates traversing to the end and appending a new node.
function addAtEnd(data) {
let newNode = new Node(data);
if (!this.head) {
this.head = newNode; // If the list is empty, set head as the new node.
return;
}
let tail = this.head;
while (tail.next) {
tail = tail.next; // Find the last node.
}
tail.next = newNode; // Add the new node to the end.
}
c. In the Middle: Here, we place the new node after a specific existing node.
function addInMiddle(data, after) {
let newNode = new Node(data);
let current = this.head;
while (current && current.data !== after) {
current = current.next; // Traverse till we find the node after which we need to insert.
}
if (current) {
newNode.next = current.next; // Adjust the links.
current.next = newNode;
}
}
2. Deleting a Node:
Deletion in a linked list involves readjusting pointers to ensure no node is accidentally lost.
a. Deleting the Head:
function deleteFromBeginning() {
if (!this.head) return;
this.head = this.head.next;
}
b. Deleting the Tail:
function deleteFromEnd() {
if (!this.head) return;
if (!this.head.next) {
this.head = null;
return;
}
let penultimate = this.head;
while (penultimate.next.next) {
penultimate = penultimate.next;
}
penultimate.next = null;
}
c. Deleting a Specific Node:
function deleteNode(data) {
if (!this.head) return;
if (this.head.data === data) {
this.head = this.head.next;
return;
}
let current = this.head;
while (current.next && current.next.data !== data) {
current = current.next;
}
if (current.next) {
current.next = current.next.next;
}
}
3. Reversing a Linked List:
This operation inverts the direction of the linked list. Every ‘next’ reference is reversed. It’s often asked in interviews as a test of one’s understanding of pointer manipulation.
function reverse() {
let current = this.head;
let prev = null;
let next = null;
while (current) {
next = current.next; // Backup next node
current.next = prev; // Reverse the pointer
prev = current; // Move prev to this node
current = next; // On to the next node
}
this.head = prev; // Reset the head to the end of the list
}
Wrapping Up:
The linked list, with its dynamic size and efficient insertion/removal capabilities, often becomes the preferred choice in numerous applications, from simple data storage to complex algorithms like garbage collection. When working with data structures in JavaScript or any other language, understanding the intricacies of linked lists provides an essential foundation.