Delete by Value in Doubly Linked List in DSA Javascript - Deep Dive

Overview - Delete by Value in Doubly Linked List

What is it?

A doubly linked list is a chain of nodes where each node points to both its previous and next node. Deleting by value means finding the first node with a specific value and removing it from the list. This operation updates the links so the list stays connected without the removed node. It helps manage data dynamically when you need to remove specific items.

Why it matters

Without the ability to delete nodes by value, managing data in a linked list would be inefficient and error-prone. You would have to rebuild the entire list or only remove nodes by position, which is less flexible. This operation allows programs to update data structures smoothly, like removing a contact from a phonebook or deleting a task from a to-do list.

Where it fits

Before learning this, you should understand what a doubly linked list is and how nodes connect. After this, you can learn about other operations like insertion, searching, and reversing lists. This fits into the broader study of dynamic data structures and memory management.

Mental Model

Core Idea

Deleting by value in a doubly linked list means finding the node with that value and carefully rewiring its neighbors to skip it, keeping the list connected.

Think of it like...

Imagine a train where each carriage is linked to the one before and after. Removing a carriage by its number means uncoupling it and reconnecting the remaining carriages so the train stays whole.

Head ⇄ Node1 ⇄ Node2 ⇄ Node3 ⇄ Node4 ⇄ null

If we delete Node3 by value:
Head ⇄ Node1 ⇄ Node2 ⇄ Node4 ⇄ null

The links from Node2 now point directly to Node4, skipping Node3.

Build-Up - 7 Steps

1

Foundation

Understanding Doubly Linked List Structure

Concept: Learn how nodes in a doubly linked list connect to both previous and next nodes.

Each node has three parts: value, pointer to previous node, and pointer to next node. The first node's previous pointer is null, and the last node's next pointer is null. This allows moving forward and backward through the list.

Result

You can visualize the list as a chain where each link connects two neighbors in both directions.

Understanding the two-way connections is essential because deletion must update both sides to keep the list intact.

2

Foundation

Basic Node Removal in Doubly Linked List

Concept: Learn how to remove a node when you already have a reference to it.

To remove a node, set its previous node's next pointer to its next node, and its next node's previous pointer to its previous node. Then disconnect the node itself.

Result

The node is removed, and the list remains connected without gaps.

Knowing how to remove a node by reference prepares you to handle deletion by value, which first requires finding the node.

3

Intermediate

Searching Node by Value in Doubly Linked List

Concept: Learn how to find the first node with a given value by traversing the list.

Start from the head and move forward node by node, comparing each node's value with the target. Stop when you find a match or reach the end.

Result

You get a reference to the node to delete or null if not found.

Searching is necessary because deletion by value depends on locating the correct node first.

4

Intermediate

Deleting Node by Value with Edge Cases

🤔Before reading on: Do you think deleting the head node requires different steps than deleting a middle node? Commit to your answer.

Concept: Learn how to handle deletion when the node is at the head, tail, or middle of the list.

If the node to delete is the head, update the head pointer to the next node and set its previous pointer to null. If it's the tail, update the previous node's next pointer to null. For middle nodes, update both neighbors as usual.

Result

The list updates correctly regardless of the node's position.

Handling edge cases prevents broken links and errors when deleting nodes at the ends of the list.

5

Intermediate

Implementing Delete by Value in JavaScript

🤔Before reading on: Do you think the delete function should return a boolean indicating success or the deleted node? Commit to your answer.

Concept: Write a complete JavaScript function to delete the first node with a given value from a doubly linked list.

class Node { constructor(value) { this.value = value; this.prev = null; this.next = null; } } class DoublyLinkedList { constructor() { this.head = null; this.tail = null; } append(value) { const newNode = new Node(value); if (!this.head) { this.head = newNode; this.tail = newNode; return; } this.tail.next = newNode; newNode.prev = this.tail; this.tail = newNode; } deleteByValue(value) { let current = this.head; while (current) { if (current.value === value) { 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; } current.next = null; current.prev = null; return true; // Deleted successfully } current = current.next; } return false; // Value not found } printList() { let current = this.head; let result = ''; while (current) { result += current.value + ' <-> '; current = current.next; } result += 'null'; console.log(result); } } // Example usage: const list = new DoublyLinkedList(); list.append(1); list.append(2); list.append(3); list.append(4); list.printList(); // 1 <-> 2 <-> 3 <-> 4 <-> null list.deleteByValue(3); list.printList(); // 1 <-> 2 <-> 4 <-> null list.deleteByValue(1); list.printList(); // 2 <-> 4 <-> null list.deleteByValue(4); list.printList(); // 2 <-> null list.deleteByValue(5); // false

Result

The list prints before and after deletions showing the node with the given value removed correctly.

Implementing the full function solidifies understanding of traversal, edge cases, and pointer updates in deletion.

6

Advanced

Performance and Complexity of Delete by Value

🤔Before reading on: Do you think deleting by value in a doubly linked list is faster than in a singly linked list? Commit to your answer.

Concept: Analyze the time complexity and compare with singly linked lists.

Deleting by value requires searching the list, which takes O(n) time in the worst case. The actual removal is O(1) because you have direct access to previous and next nodes. In singly linked lists, removal is slower because you must track the previous node during search. Doubly linked lists make deletion easier once the node is found.

Result

Delete by value runs in linear time overall, but pointer updates are constant time.

Understanding complexity helps choose the right data structure for performance needs.

7

Expert

Handling Multiple Nodes with Same Value

🤔Before reading on: Should delete by value remove all nodes with that value or just the first? Commit to your answer.

Concept: Explore strategies to delete all nodes matching a value versus just the first occurrence.

The basic deleteByValue removes only the first found node. To remove all, you must continue searching after each deletion. Careful pointer updates and traversal are needed to avoid skipping nodes or breaking the list. This requires looping until no nodes with the value remain.

Result

You can remove all matching nodes safely without corrupting the list.

Knowing how to extend deletion to multiple nodes prevents bugs in real applications where duplicates exist.

Under the Hood

Internally, each node stores two pointers: one to the previous node and one to the next. When deleting a node, the program updates the previous node's next pointer to skip the deleted node and point to the deleted node's next. Similarly, it updates the next node's previous pointer to point back to the deleted node's previous. This rewiring removes the node from the chain without losing access to the rest of the list. Memory for the removed node can then be reclaimed by the system.

Why designed this way?

Doubly linked lists were designed to allow easy traversal in both directions and efficient insertion and deletion at any point. The two pointers per node add memory overhead but simplify operations compared to singly linked lists. This tradeoff was chosen to optimize flexibility and speed for dynamic data management.

┌─────────┐     ┌─────────┐     ┌─────────┐
│ Prev    │◄───▶│ Prev    │◄───▶│ Prev    │
│ Value   │     │ Value   │     │ Value   │
│ Next    │───▶│ Next    │───▶│ Next    │
└─────────┘     └─────────┘     └─────────┘

Deleting middle node:

Before:
NodeA.next -> NodeB
NodeB.prev -> NodeA
NodeB.next -> NodeC
NodeC.prev -> NodeB

After:
NodeA.next -> NodeC
NodeC.prev -> NodeA
NodeB disconnected

Myth Busters - 4 Common Misconceptions

Quick: Does deleting a node by value always remove all nodes with that value? Commit to yes or no.

Common Belief: Deleting by value removes all nodes with that value automatically.

Reality: The standard delete by value removes only the first node found with that value unless explicitly coded to remove all.

Why it matters: Assuming all nodes are removed can cause bugs where duplicates remain unexpectedly, leading to incorrect program behavior.

Quick: Is it safe to delete a node without updating both previous and next pointers? Commit to yes or no.

Common Belief: Updating only one pointer (either previous or next) is enough to remove a node.

Reality: Both pointers must be updated to maintain list integrity; otherwise, the list can become broken or inaccessible.

Why it matters: Failing to update both pointers can cause runtime errors or data loss when traversing the list.

Quick: Is deleting the head node the same as deleting a middle node? Commit to yes or no.

Common Belief: Deleting the head node is the same as deleting any other node.

Reality: Deleting the head requires updating the head pointer of the list itself, which is a special case.

Why it matters: Ignoring this can leave the head pointer pointing to a deleted node, causing crashes or infinite loops.

Quick: Is deleting by value faster in doubly linked lists than singly linked lists? Commit to yes or no.

Common Belief: Doubly linked lists always delete by value faster than singly linked lists.

Reality: Searching for the value takes the same time in both (O(n)), but deletion is easier in doubly linked lists once the node is found.

Why it matters: Misunderstanding this can lead to wrong performance expectations and poor data structure choices.

Expert Zone

1

Deleting nodes in a doubly linked list requires careful handling of edge cases like empty lists, single-node lists, and tail nodes to avoid null pointer errors.

2

When deleting multiple nodes by value, traversing forward while deleting can skip nodes if not handled properly; using a temporary pointer to the next node before deletion avoids this.

3

Memory management after deletion is crucial in languages without automatic garbage collection; forgetting to free memory leads to leaks.

When NOT to use

Deleting by value in doubly linked lists is inefficient for very large lists with frequent deletions by value because searching is O(n). In such cases, consider using hash tables or balanced trees for faster lookups and deletions.

Production Patterns

In real systems, doubly linked lists with delete by value are used in LRU caches to quickly remove least recently used items, in undo-redo stacks where nodes represent states, and in GUI frameworks for managing ordered elements with dynamic insertions and deletions.

Connections

Hash Tables

Alternative data structure for fast value-based deletion

Understanding delete by value in linked lists highlights why hash tables are preferred when fast lookup and deletion by value are needed, as they offer average O(1) time.

Memory Management

Linked list deletion requires careful memory handling

Knowing how deletion affects pointers and memory helps understand manual memory management in low-level programming and prevents leaks or crashes.

Supply Chain Logistics

Process of removing an item from a linked chain

Removing a node from a doubly linked list is like rerouting shipments in a supply chain when a warehouse is closed, ensuring the flow continues smoothly without disruption.

Common Pitfalls

#1 Deleting a node without updating the head pointer when the node is the head.

Wrong approach:

if (current.value === value) {
current.prev.next = current.next;
current.next.prev = current.prev;
return true;
}

Correct approach:

if (current.value === value) {
if (current.prev) {
current.prev.next = current.next;
} else {
this.head = current.next;
}
if (current.next) {
current.next.prev = current.prev;
}
return true;
}

Root cause:

Not handling the special case where the node to delete is the head, so the head pointer remains pointing to a removed node.

#2 Continuing traversal after deleting a node without saving the next node first.

Wrong approach:

while (current) {
if (current.value === value) {
// delete current
current = current.next;
} else {
current = current.next;
}
}

Correct approach:

while (current) {
let nextNode = current.next;
if (current.value === value) {
// delete current
}
current = nextNode;
}

Root cause:

After deletion, current.next may be null or invalid, causing traversal to skip nodes or crash.

#3 Only updating one pointer (prev or next) when deleting a node.

Wrong approach:

current.prev.next = current.next; // but not updating current.next.prev

Correct approach:

current.prev.next = current.next;
current.next.prev = current.prev;

Root cause:

Forgetting that both neighbors must update their pointers to maintain list integrity.

Key Takeaways

Deleting by value in a doubly linked list involves finding the node and updating both previous and next pointers to remove it safely.

Special cases like deleting the head or tail require updating the list's head or tail pointers to avoid broken links.

Searching for the node takes linear time, but the actual removal is constant time due to direct access to neighbors.

Careful pointer updates prevent list corruption and runtime errors during deletion.

Extending deletion to multiple nodes with the same value requires careful traversal to avoid skipping nodes.

Practice

1. What happens when you delete a node by value in a doubly linked list?

easy

A. The node with the matching value is removed and links are updated

B. All nodes are deleted regardless of value

C. Only the first node is deleted no matter the value

D. The list is reversed instead of deleting

Solution

1. Step 1: Locate the node with the given value

   Traverse the list from head to tail to find the node whose value matches the target.

2. Step 2: Remove the node and update links

   Adjust the previous node's next pointer and the next node's previous pointer to bypass the deleted node.

3. Final Answer:

   The node with the matching value is removed and links are updated -> Option A

4. Quick Check:

   Delete by value means remove matching node [OK]

Hint: Delete node by value means remove matching node and fix links [OK]

Common Mistakes:

• Deleting all nodes instead of one
• Not updating previous or next pointers
• Deleting wrong node when multiple have same value

2. Which of the following is the correct way to check if the current node's value matches the target value in JavaScript?

easy

A. if (current.value != target) {}

B. if (current.value == target) {}

C. if (current.value = target) {}

D. if (current.value === target) {}

Solution

1. Step 1: Understand JavaScript equality operators

   Use === for strict equality to avoid type coercion and ensure exact match.

2. Step 2: Identify correct syntax for comparison

   if (current.value === target) correctly compares values and types.

3. Final Answer:

   if (current.value === target) {} -> Option D

4. Quick Check:

   Use strict equality (===) for value comparison [OK]

Hint: Use === for exact value and type match in JavaScript [OK]

Common Mistakes:

• Using single = which assigns instead of compares
• Using == which allows type coercion
• Using != which checks inequality

3. Consider this doubly linked list: 10 <-> 20 <-> 30 <-> 40. After deleting the node with value 30, what is the new list?

medium

A. 10 <-> 20 <-> 30 <-> 40

B. 10 <-> 20 <-> 40

C. 20 <-> 30 <-> 40

D. 10 <-> 30 <-> 40

Solution

1. Step 1: Identify node to delete

   The node with value 30 is located between 20 and 40.

2. Step 2: Remove node 30 and update links

   Set 20's next pointer to 40 and 40's previous pointer to 20, skipping 30.

3. Final Answer:

   10 <-> 20 <-> 40 -> Option B

4. Quick Check:

   Deleted 30, linked 20 and 40 directly [OK]

Hint: Remove node and link neighbors directly [OK]

Common Mistakes:

• Not updating previous pointer of next node
• Leaving deleted node linked in list
• Deleting wrong node

4. Given this code snippet to delete a node by value, what is the error?

function deleteByValue(head, value) {
  let current = head;
  while (current !== null) {
    if (current.value === value) {
      current.prev.next = current.next;
      current.next.prev = current.prev;
      break;
    }
    current = current.next;
  }
  return head;
}

medium

A. It uses assignment instead of comparison

B. It never breaks the loop

C. It does not handle deleting the head node correctly

D. It returns null always

Solution

1. Step 1: Analyze deletion of head node

   If the node to delete is the head, current.prev is null, so current.prev.next causes error.

2. Step 2: Identify missing head update

   Code should update head to current.next if deleting head node to avoid broken list.

3. Final Answer:

   It does not handle deleting the head node correctly -> Option C

4. Quick Check:

   Deleting head needs special handling [OK]

Hint: Check if node is head before updating prev pointers [OK]

Common Mistakes:

• Not checking if current.prev is null
• Not updating head when deleting first node
• Assuming all nodes have prev and next

5. You have a doubly linked list: 5 <-> 10 <-> 15 <-> 20 <-> 25. You want to delete the node with value 5 (head) and then the node with value 25 (tail). What is the final list?

hard

A. 10 <-> 15 <-> 20

B. 5 <-> 10 <-> 15 <-> 20

C. 10 <-> 15 <-> 20 <-> 25

D. 15 <-> 20

Solution

1. Step 1: Delete head node with value 5

   Update head to 10 and set 10.prev to null.

2. Step 2: Delete tail node with value 25

   Update 20.next to null, removing 25.

3. Final Answer:

   10 <-> 15 <-> 20 -> Option A

4. Quick Check:

   Removed head and tail nodes correctly [OK]

Hint: Update head or tail pointers when deleting ends [OK]

Common Mistakes:

• Not updating head when deleting first node
• Not updating tail when deleting last node
• Leaving dangling pointers