How to use Traversal Method In Javascript
In this approach, we first find the length of the doubly linked list by traversing it. Then we traverse the list again to find the middle node using the length. Finally, we delete the middle node by adjusting the pointers of the previous and next nodes of the middle node to skip over it.
Example: The example below shows the demonstration to delete middle of doubly linked list using length based approach.
class Node {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
}
printList() {
let current = this.head;
while (current !== null) {
process.stdout.write(`${current.data} <-> `);
current = current.next;
}
process.stdout.write("null\n");
}
deleteMiddleLengthBased() {
// Find the Length of the List
let length = 0;
let current = this.head;
while (current !== null) {
length++;
current = current.next;
}
// Find the Middle Node
let middleIndex = Math.floor(length / 2);
current = this.head;
for (let i = 0; i < middleIndex; i++) {
current = current.next;
}
// Delete the Middle Node
if (current === this.head) {
this.head = current.next;
} else {
current.prev.next = current.next;
}
if (current === this.tail) {
this.tail = current.prev;
} else {
current.next.prev = current.prev;
}
current = null;
}
}
// Example usage
let list = new DoublyLinkedList();
list.head = new Node(3);
list.head.next = new Node(2);
list.head.next.prev = list.head;
list.head.next.next = new Node(4);
list.head.next.next.prev = list.head.next;
list.head.next.next.next = new Node(6);
list.head.next.next.next.prev = list.head.next.next;
list.head.next.next.next.next = new Node(9);
list.head.next.next.next.next.prev = list.head.next.next.next;
list.tail = list.head.next.next.next.next;
console.log("Before deletion:");
list.printList();
list.deleteMiddleLengthBased();
console.log("After deletion:");
list.printList();
Output
Before deletion: 3 <-> 2 <-> 4 <-> 6 <-> 9 <-> null After deletion: 3 <-> 2 <-> 6 <-> 9 <-> null
Time Complexity: O(n)
Space complexity: O(1)
JavaScript Program to Delete Middle of Doubly Linked List
We are given a doubly linked list and we have to write a JavaScript program to delete the middle node of the list and print the newly formed linked list after the deletion.
Example:
Input: 1 <-> 2 <-> 3 <-> 4 <-> 5
Output: 1 <-> 2 <-> 4 <-> 5
Below are the different approaches to delete the middle of a doubly linked list:
Table of Content
- Using Two-pointer approach
- Using Traversal Method
Contact Us