Delete by Value in Doubly Linked List in DSA Typescript - 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 that holds 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 order and quick insertions or deletions matter.

Why it matters

Without the ability to delete nodes by value, managing data in a list would be inefficient and error-prone. Imagine a playlist where you want to remove a specific song; without this operation, you'd have to rebuild the entire list. This method keeps data organized and allows programs to update information quickly, improving performance and user experience.

Where it fits

Before learning this, you should understand what a doubly linked list is and how nodes connect. After mastering deletion by value, you can explore more complex operations like sorting, reversing, or merging doubly linked lists.

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 over it, keeping the list intact.

Think of it like...

It's like removing a book from a shelf where each book has a bookmark pointing to the book before and after it. To remove one book, you take out its bookmarks and connect the bookmarks of the neighboring books directly.

Head ⇄ Node1 ⇄ Node2 ⇄ Node3 ⇄ Tail

If deleting Node2:
Head ⇄ Node1 ⇄ Node3 ⇄ Tail

The arrows from Node1 and Node3 are rewired to skip Node2.

Build-Up - 6 Steps

1

Foundation

Understanding Doubly Linked List Structure

Concept: Learn how nodes connect forward and backward in a doubly linked list.

Each node has three parts: a value, a pointer to the next node, and a pointer to the previous node. The list starts with a head node and ends with a tail node. This two-way connection allows easy movement in both directions.

Result

You can move from any node to its neighbors in both directions.

Understanding the two-way links is essential because deletion requires updating both previous and next pointers to maintain the list's integrity.

2

Foundation

Basic Node Removal in Doubly Linked List

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

To remove a node, update the previous node's next pointer to the current node's next, and the next node's previous pointer to the current node's previous. Then, disconnect the current node's pointers.

Result

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

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

3

Intermediate

Searching Node by Value in Doubly Linked List

🤔Before reading on: do you think searching for a value requires checking every node or just some nodes? Commit to your answer.

Concept: Learn how to find the first node that contains a specific value.

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

Result

You get the reference to the node with the target value or null if not found.

Understanding linear search in the list is crucial because deletion by value depends on locating the correct node first.

4

Intermediate

Combining Search and Removal by Value

🤔Before reading on: do you think you can delete a node by value without searching first? Commit to yes or no.

Concept: Learn to delete a node by first searching for its value, then removing it.

Use the search method to find the node with the target value. If found, remove it by updating the neighbors' pointers as in node removal. Handle special cases like deleting head or tail nodes.

Result

The node with the given value is removed, and the list remains connected.

Knowing that deletion by value is a two-step process (search then remove) helps avoid mistakes like trying to remove a node without knowing its position.

5

Advanced

Handling Edge Cases in Deletion by Value

🤔Before reading on: do you think deleting the head or tail node requires special pointer updates? Commit to yes or no.

Concept: Learn how to correctly delete nodes at the start or end 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 tail pointer to the previous node and set its next pointer to null. For middle nodes, update both neighbors as usual.

Result

Deletion works correctly even when removing the first or last node.

Handling edge cases prevents list corruption and runtime errors, ensuring robust deletion logic.

6

Expert

Optimizing Deletion with Sentinel Nodes

🤔Before reading on: do you think sentinel nodes simplify deletion logic or add unnecessary complexity? Commit to your answer.

Concept: Learn how using dummy head and tail nodes (sentinels) can simplify deletion by avoiding null checks.

Sentinel nodes are extra nodes at the start and end that do not hold data. They ensure that every real node has both previous and next nodes, so deletion code doesn't need to check for null pointers. This reduces bugs and makes code cleaner.

Result

Deletion code becomes simpler and less error-prone, especially for edge cases.

Understanding sentinel nodes reveals how small structural changes can greatly improve code safety and maintainability.

Under the Hood

Internally, each node stores memory addresses (pointers) to its neighbors. Deletion by value involves traversing these pointers to find the target node, then rewiring the previous node's next pointer and the next node's previous pointer to bypass the target node. The target node's pointers are then cleared to help garbage collection. This pointer manipulation keeps the list connected without the removed node.

Why designed this way?

Doubly linked lists were designed to allow efficient two-way traversal and easy insertion or deletion at any position. The double pointers enable quick updates without scanning the entire list again. Alternatives like singly linked lists only have one pointer, making backward traversal and some deletions slower or more complex.

Head ⇄ Node1 ⇄ Node2 ⇄ Node3 ⇄ Tail

Delete Node2:
Node1.next = Node3
Node3.prev = Node1
Node2.next = null
Node2.prev = null

Myth Busters - 3 Common Misconceptions

Quick: Do you think deleting a node by value removes all nodes with that value or just the first one? Commit to your answer.

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

Reality: The standard delete by value operation removes only the first node found with that value.

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

Quick: Do you think you can delete a node by value 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 previous and next pointers must be updated to maintain list integrity; otherwise, the list breaks.

Why it matters: Failing to update both pointers can cause broken links, leading to crashes or infinite loops during traversal.

Quick: Do you think deleting the head node is 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; no special handling needed.

Reality: Deleting the head requires updating the head pointer of the list and possibly setting the new head's previous pointer to null.

Why it matters: Ignoring this causes the list head to point to a removed node, breaking access to the list.

Expert Zone

1

Deleting by value can be optimized by maintaining a hash map of values to nodes for faster lookup in large lists.

2

Sentinel nodes reduce conditional checks but add slight memory overhead; choosing to use them depends on performance vs. simplicity tradeoffs.

3

In concurrent environments, deletion requires careful locking or atomic operations to avoid race conditions and corrupted pointers.

When NOT to use

Deleting by value is inefficient for very large lists with many duplicates; in such cases, using balanced trees or hash-based structures is better. Also, if frequent deletions happen at known positions, direct node references or indices are preferred.

Production Patterns

In real systems, doubly linked lists with deletion 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 managing ordered elements with dynamic insertions and removals.

Connections

Hash Tables

Builds-on

Knowing how to delete by value in linked lists helps understand how hash tables handle collisions using chaining with linked lists.

Memory Management

Underlying principle

Understanding pointer updates during deletion connects to how memory is allocated and freed, preventing leaks and dangling pointers.

Supply Chain Logistics

Analogous process

Removing an item from a supply chain involves rerouting shipments around the removed node, similar to rewiring pointers in a doubly linked list.

Common Pitfalls

#1 Forgetting to update the previous pointer of the next node when deleting.

Wrong approach:

if (node.prev) node.prev.next = node.next;
// Missing: node.next.prev = node.prev;

Correct approach:

if (node.prev) node.prev.next = node.next;
if (node.next) node.next.prev = node.prev;

Root cause:

Misunderstanding that both neighbors must update their pointers to maintain the list's double linkage.

#2 Not handling deletion when the node to remove is the head.

Wrong approach:

if (node.prev) node.prev.next = node.next;
if (node.next) node.next.prev = node.prev;
// Missing: updating list head if node is head

Correct approach:

if (node === head) head = node.next;
if (node === tail) tail = node.prev;
if (node.prev) node.prev.next = node.next;
if (node.next) node.next.prev = node.prev;

Root cause:

Assuming all nodes have a previous node and ignoring the special role of the head pointer.

#3 Trying to delete a node by value without searching first.

Wrong approach:

function deleteByValue(value) {
// Directly remove without finding node
node.prev.next = node.next;
node.next.prev = node.prev;
}

Correct approach:

function deleteByValue(value) {
let node = head;
while (node && node.value !== value) {
node = node.next;
}
if (!node) return;
if (node === head) head = node.next;
if (node === tail) tail = node.prev;
if (node.prev) node.prev.next = node.next;
if (node.next) node.next.prev = node.prev;
}

Root cause:

Confusing deletion by reference with deletion by value, missing the search step.

Key Takeaways

Deleting by value in a doubly linked list requires first finding the node with that value, then updating the pointers of its neighbors to exclude it.

Both the previous node's next pointer and the next node's previous pointer must be updated to maintain the list's integrity.

Special cases like deleting the head or tail nodes need careful pointer updates to avoid breaking the list.

Using sentinel nodes can simplify deletion logic by eliminating null checks for neighbors.

Understanding deletion by value connects to broader concepts like memory management, data structure efficiency, and real-world systems that manage ordered data.

Practice

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

easy

A. All nodes are deleted regardless of value

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

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

D. The list is reversed instead of deleting

Solution

1. Step 1: Identify 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 exclude the found node.

3. Final Answer:

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

4. Quick Check:

   Deleting by value removes matching node [OK]

Hint: Find node by value, then update previous and next links [OK]

Common Mistakes:

• Not updating previous node's next pointer
• Not updating next node's previous pointer
• Deleting all nodes instead of one

2. Which of the following is the correct TypeScript syntax to delete a node by value in a doubly linked list?

easy

A. function deleteNode(value) { /* code */ }

B. removeNode(value: number) => { /* code */ }

C. deleteNode(value: number): void { /* code */ }

D. delete node(value: number) { /* code */ }

Solution

1. Step 1: Check method declaration syntax in TypeScript class

   Methods inside classes use the syntax methodName(params): returnType { body }.

2. Step 2: Identify correct syntax for deleteNode method

   deleteNode(value: number): void { /* code */ } uses correct TypeScript method syntax with type annotation and void return.

3. Final Answer:

   deleteNode(value: number): void { /* code */ } -> Option C

4. Quick Check:

   TypeScript method syntax = deleteNode(value: number): void { /* code */ } [OK]

Hint: Use methodName(params): returnType { } inside class [OK]

Common Mistakes:

• Using arrow function syntax inside class method
• Missing type annotations
• Using invalid keywords like 'delete node'

3. Given the doubly linked list: 10 <-> 20 <-> 30 <-> 40, what is the list after deleting the node with value 30?

medium

A. 10 <-> 20 <-> 40

B. 10 <-> 30 <-> 40

C. 20 <-> 30 <-> 40

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

Solution

1. Step 1: Locate node with value 30

   Traverse the list: 10 -> 20 -> 30 found at third node.

2. Step 2: Remove node 30 and link 20 to 40

   Update 20's next pointer to 40 and 40's previous pointer to 20.

3. Final Answer:

   10 <-> 20 <-> 40 -> Option A

4. Quick Check:

   Deleted 30, list links updated [OK]

Hint: Remove node, link previous and next nodes directly [OK]

Common Mistakes:

• Not updating previous node's next pointer
• Not updating next node's previous pointer
• Deleting wrong node

4. What is wrong with this delete function snippet for doubly linked list?

deleteNode(value: number): void {
  let current = this.head;
  while (current !== null) {
    if (current.value === value) {
      current.prev.next = current.next;
      current.next.prev = current.prev;
      break;
    }
    current = current.next;
  }
}

medium

A. It does not handle deleting the head node correctly

B. It deletes all nodes with the value instead of one

C. It uses wrong variable names

D. It causes infinite loop

Solution

1. Step 1: Check handling of head node deletion

   If current is head, current.prev is null, so current.prev.next causes error.

2. Step 2: Identify missing head update

   Function does not update this.head when deleting the first node, causing broken list.

3. Final Answer:

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

4. Quick Check:

   Head deletion 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 pointer 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, then delete the node with value 25. What is the final list?

hard

A. 15 <-> 20

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

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

D. 10 <-> 15 <-> 20

Solution

1. Step 1: Delete node with value 5 (head node)

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

2. Step 2: Delete node with value 25 (tail node)

   Update 20.next to null, removing 25.

3. Final Answer:

   10 <-> 15 <-> 20 -> Option D

4. Quick Check:

   Deleted head and tail nodes correctly [OK]

Hint: Update head or tail pointers when deleting first or last nodes [OK]

Common Mistakes:

• Not updating head when deleting first node
• Not updating tail when deleting last node
• Breaking links between middle nodes