Doubly Linked List in JavaScript: A Comprehensive Overview
Understanding the Doubly Linked List:
Unlike a singly linked list where each node only points to its successor, a Doubly Linked List (DLL) offers a more robust structure. In DLL, each node points both ways — to its predecessor and successor, enhancing traversal capabilities.
Crafting a Node in JavaScript:
class Node {
constructor(data, next = null, prev = null) {
this.data = data;
this.next = next;
this.prev = prev;
}
}
Operation Explanations:
1. Adding a Node:
- At the Beginning: To insert a node at the start, the
prev
pointer of the current head must reference the new node. Simultaneously, thenext
pointer of the new node should point to the existing head, effectively promoting the new node to be the head.
function addAtBeginning(data) {
let newNode = new Node(data, this.head);
if (this.head) this.head.prev = newNode;
this.head = newNode;
if (!this.tail) this.tail = newNode; // if the list was empty
}
- At the End: Inserting at the end involves adjusting the
next
pointer of the current tail and ensuring theprev
pointer of the new node points back to the current tail. If the list was empty, both head and tail would point to the new node.
function addAtEnd(data) {
let newNode = new Node(data, null, this.tail);
if (this.tail) this.tail.next = newNode;
this.tail = newNode;
if (!this.head) this.head = newNode; // if the list was empty
}
- In the Middle:This requires a bit more care since we need to ensure continuity in both forward and backward directions.
function addInMiddle(data, afterValue) {
let current = this.head;
while (current && current.data !== afterValue) {
current = current.next;
}
if (current) {
let newNode = new Node(data, current.next, current);
if (current.next) current.next.prev = newNode;
current.next = newNode;
if (!newNode.next) this.tail = newNode; // if newNode is now the last node
}
}
2. Deleting a Node:
The dual pointers in DLL require us to ensure the continuity of both next
and prev
pointers when performing deletions.
a. Deleting the Head:
Remove the current head and promote its successor as the new head. Ensure to reset its prev
pointer.
function deleteFromBeginning() {
if (!this.head) return;
this.head = this.head.next;
if (this.head) this.head.prev = null;
else this.tail = null; // if the list is now empty
}
b. Deleting the Tail:
This is more straightforward in DLLs compared to singly linked lists. Shift the tail pointer to its predecessor and nullify its next
pointer.
function deleteFromEnd() {
if (!this.tail) return;
this.tail = this.tail.prev;
if (this.tail) this.tail.next = null;
else this.head = null; // if the list is now empty
}
c. Deleting a Specific Node:
Find the node, then adjust the next
pointer of its predecessor and the prev
pointer of its successor.
function deleteNode(data) {
let current = this.head;
while (current && current.data !== data) {
current = current.next;
}
if (current) {
if (current.prev) current.prev.next = current.next;
else this.head = current.next;
if (current.next) current.next.prev = current.prev;
else this.tail = current.prev;
}
}
3. Reversing a Doubly Linked List:
Reversing a DLL involves swapping the next
and prev
pointers for all nodes and updating the head and tail pointers.
function reverse() {
let current = this.head;
let temp = null;
while (current) {
temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev;
}
temp = this.head;
this.head = this.tail;
this.tail = temp;
}
Conclusion:
Doubly Linked Lists, with their bidirectional traversal capabilities, offer a significant advantage over singly linked lists, especially when backward navigation within the list becomes essential. However, it’s worth noting that this comes at the expense of additional memory for the prev
pointer. As always, it’s essential to weigh the trade-offs based on specific requirements and scenarios.
No Comment! Be the first one.