Delete by Value in Doubly Linked List in DSA C++ - 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 want to remove specific items.

Why it matters

Without the ability to delete by value, you would have to rebuild or ignore unwanted data manually, which is inefficient and error-prone. This operation allows programs to manage collections of data flexibly, like removing a contact from a phone list or deleting a song from a playlist. It keeps data structures clean and up-to-date, which is essential for responsive and correct software.

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, or reversing the list. This concept builds your skills in manipulating linked data structures and prepares you for more complex data handling.

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 connected to the one before and after it. Removing a carriage means uncoupling it and reconnecting the two neighboring carriages so the train stays whole.

Head ⇄ Node1 ⇄ Node2 ⇄ Node3 ⇄ Tail

To delete Node2:
Head ⇄ Node1 ⇄ Node3 ⇄ Tail

The links from Node1 and Node3 are updated to skip Node2.

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 contains three parts: the data value, a pointer to the previous node, and a pointer to the next node. The first node's previous pointer is null, and the last node's next pointer is null. This two-way connection allows easy forward and backward traversal.

Result

You can move through the list in both directions, from head to tail and tail to head.

Knowing the two-way links is essential because deletion requires updating both neighbors, unlike singly linked lists.

2

Foundation

Basic Node Removal Concept

Concept: Removing a node means changing the pointers of its neighbors to exclude it.

To remove a node, you set the previous node's next pointer to the node after the one being removed, and the next node's previous pointer to the node before the one being removed. Then, the removed node is disconnected and can be deleted.

Result

The list remains connected without the removed node, and no dangling pointers remain.

Understanding pointer updates prevents breaking the list or losing access to parts of it.

3

Intermediate

Searching for Node by Value

Concept: Before deleting, you must find the node containing the target value.

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

Result

You identify the exact node to remove or know it doesn't exist.

Knowing how to search efficiently is key to targeted deletion without affecting other nodes.

4

Intermediate

Handling Edge Cases in Deletion

🤔Before reading on: do you think deleting the head node requires the same pointer updates as deleting a middle node? Commit to your answer.

Concept: Deleting nodes at the start or end of the list needs special care because neighbors may be null.

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

The list remains valid with correct head and tail pointers after deletion.

Recognizing edge cases prevents null pointer errors and keeps the list structure intact.

5

Intermediate

Implementing Delete by Value in C++

🤔Before reading on: do you think deleting a node requires freeing its memory immediately or can it be left as is? Commit to your answer.

Concept: Write code to find and remove the first node with the given value, updating pointers and freeing memory.

```cpp #include struct Node { int data; Node* prev; Node* next; Node(int val) : data(val), prev(nullptr), next(nullptr) {} }; class DoublyLinkedList { public: Node* head; Node* tail; DoublyLinkedList() : head(nullptr), tail(nullptr) {} void append(int val) { Node* newNode = new Node(val); if (!head) { head = tail = newNode; } else { tail->next = newNode; newNode->prev = tail; tail = newNode; } } void deleteByValue(int val) { Node* current = head; while (current) { if (current->data == val) { if (current->prev) { current->prev->next = current->next; } else { head = current->next; } if (current->next) { current->next->prev = current->prev; } else { tail = current->prev; } delete current; return; } current = current->next; } } void printList() { Node* temp = head; while (temp) { std::cout << temp->data << " <-> "; temp = temp->next; } std::cout << "null" << std::endl; } }; int main() { DoublyLinkedList dll; dll.append(1); dll.append(2); dll.append(3); dll.append(4); dll.printList(); dll.deleteByValue(3); dll.printList(); dll.deleteByValue(1); dll.printList(); dll.deleteByValue(4); dll.printList(); dll.deleteByValue(5); // value not in list dll.printList(); return 0; } ```

Result

Initial list: 1 <-> 2 <-> 3 <-> 4 <-> null After deleting 3: 1 <-> 2 <-> 4 <-> null After deleting 1: 2 <-> 4 <-> null After deleting 4: 2 <-> null After deleting 5 (not found): 2 <-> null

Knowing to free memory after unlinking prevents memory leaks and keeps the program efficient.

6

Advanced

Performance and Complexity Considerations

🤔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 how the doubly linked list structure affects the speed and complexity of deletion by value.

Searching for the node by value takes O(n) time because you may need to check each node. Deletion itself is O(1) once the node is found because you have direct access to previous and next nodes. Compared to singly linked lists, doubly linked lists avoid needing to track the previous node during traversal, simplifying deletion.

Result

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

Understanding time complexity helps choose the right data structure for performance-sensitive applications.

7

Expert

Handling Multiple Occurrences and Safe Deletion

🤔Before reading on: do you think deleting all nodes with a given value requires the same code as deleting just one? Commit to your answer.

Concept: Extend deletion to remove all nodes with the target value safely, avoiding pointer errors during iteration.

When deleting multiple nodes, you must be careful because deleting a node changes the list structure. Use a temporary pointer to store the next node before deleting the current one. Continue until all matching nodes are removed. This prevents skipping nodes or accessing deleted memory.

Result

All nodes with the target value are removed, and the list remains intact.

Knowing how to safely delete multiple nodes prevents subtle bugs and crashes in real-world programs.

Under the Hood

Each node stores two pointers: one to the previous node and one to the next. When deleting a node, the program updates these pointers in the neighboring nodes to bypass the deleted node. The deleted node's memory is then freed to avoid leaks. The head or tail pointers are updated if the deleted node is at the ends. This pointer manipulation happens at the memory address level, ensuring the list remains a continuous chain.

Why designed this way?

Doubly linked lists were designed to allow easy traversal in both directions and efficient insertion or deletion at any point. The two pointers per node add memory overhead but simplify operations compared to singly linked lists, which require tracking previous nodes during deletion. This tradeoff favors flexibility and speed in many applications.

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

Deleting middle node:
Prev node's Next pointer ──▶ Next node
Next node's Prev pointer ◀── Prev node
Deleted node disconnected and freed.

Myth Busters - 4 Common Misconceptions

Quick: Do you think deleting a node by value always removes all nodes with that value? Commit to yes or no.

Common Belief: Deleting by value removes every node that matches the value in the list.

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

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

Quick: Do you think you can delete a node without updating both previous and next pointers? Commit to yes or no.

Common Belief: You only need to update the next pointer of the previous node to delete a node.

Reality: You must update both the previous node's next pointer and the next node's previous pointer to maintain list integrity.

Why it matters: Failing to update both pointers breaks the list, causing traversal errors and potential crashes.

Quick: Do you think deleting a node automatically frees its memory without explicit code? Commit to yes or no.

Common Belief: Once a node is removed from the list, its memory is automatically freed by the system.

Reality: In languages like C++, you must explicitly delete the node to free memory; otherwise, it causes memory leaks.

Why it matters: Memory leaks degrade performance and can crash programs, especially in long-running applications.

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 requires the same pointer updates as deleting any other node.

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

Why it matters: Ignoring head pointer updates can leave the list head pointing to deleted memory, causing undefined behavior.

Expert Zone

1

Deleting nodes in a multithreaded environment requires locks or atomic operations to avoid race conditions.

2

When deleting nodes during iteration, always store the next node before deletion to avoid accessing freed memory.

3

In some implementations, sentinel (dummy) nodes simplify deletion logic by avoiding null checks at head or tail.

When NOT to use

Deleting by value is inefficient for large lists with many duplicates because it requires linear search. Alternatives like balanced trees or hash tables provide faster search and deletion. For real-time systems, consider data structures with guaranteed operation times.

Production Patterns

In production, delete by value is often combined with search optimizations or indexing. Systems may batch deletions or mark nodes as deleted (lazy deletion) to improve performance. Doubly linked lists are used in undo-redo stacks, browser history, and memory management where quick bidirectional traversal and deletion are needed.

Connections

Singly Linked List Deletion

Similar operation but with only one pointer per node, requiring tracking the previous node during traversal.

Understanding doubly linked list deletion clarifies why singly linked lists need extra steps to delete nodes, highlighting tradeoffs in data structure design.

Garbage Collection in Programming Languages

Deleting nodes manually contrasts with automatic memory management in garbage-collected languages.

Knowing manual deletion deepens appreciation for garbage collection and the risks of memory leaks in unmanaged environments.

Train Carriage Coupling Systems

Physical analogy where removing a carriage requires uncoupling and reconnecting neighbors, similar to pointer updates.

This connection shows how abstract data structures mirror real-world mechanical systems, aiding intuitive understanding.

Common Pitfalls

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

Wrong approach:

current->prev->next = current->next;
// Missing: current->next->prev = current->prev;

Correct approach:

current->prev->next = current->next;
if (current->next) {
current->next->prev = current->prev;
}

Root cause:

Assuming only one pointer needs updating leads to broken backward links and traversal errors.

#2 Not handling deletion of the head node separately.

Wrong approach:

if (current->prev) {
current->prev->next = current->next;
} else {
// No update to head pointer
}

Correct approach:

if (current->prev) {
current->prev->next = current->next;
} else {
head = current->next;
}

Root cause:

Ignoring that the head pointer must move when the first node is deleted causes invalid list start.

#3 Deleting a node without freeing its memory.

Wrong approach:

current->prev->next = current->next;
current->next->prev = current->prev;
// Missing: delete current;

Correct approach:

current->prev->next = current->next;
current->next->prev = current->prev;
delete current;

Root cause:

Confusing unlinking from the list with memory deallocation causes memory leaks.

Key Takeaways

Deleting by value in a doubly linked list requires finding the node and updating both neighbors' pointers to maintain list integrity.

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

Memory management is crucial; after unlinking a node, its memory must be freed to prevent leaks.

The operation runs in linear time due to searching but updates pointers in constant time, balancing flexibility and performance.

Understanding these details prevents common bugs and prepares you for advanced data structure manipulation.

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 without checking 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 data matches the value to delete.

2. Step 2: Update links to remove the node

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

3. Final Answer:

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

4. Quick Check:

   Delete by value removes matching node [OK]

Hint: Find node, update previous and next pointers [OK]

Common Mistakes:

• Not updating both previous and next pointers
• Deleting node without checking value
• Deleting all nodes instead of one

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

easy

A. void deleteNode(Node* &head, int val) { /* code */ }

B. void deleteNode(int val) { /* code */ }

C. Node deleteNode(int val) { /* code */ }

D. int deleteNode(Node* head, int val) { /* code */ }

Solution

1. Step 1: Understand parameter passing for head pointer

   Head pointer must be passed by reference to allow modification if the first node is deleted.

2. Step 2: Check function return type

   Deletion functions usually return void as they modify the list in place.

3. Final Answer:

   void deleteNode(Node* &head, int val) { /* code */ } -> Option A

4. Quick Check:

   Pass head by reference and return void [OK]

Hint: Pass head by reference to modify list [OK]

Common Mistakes:

• Passing head by value causing no list update
• Returning Node instead of void
• Missing head pointer parameter

3. What is the output of the following code snippet after deleting value 20 from the doubly linked list?

struct Node {
  int data;
  Node* prev;
  Node* next;
};

// List: 10 <-> 20 <-> 30
// deleteNode(head, 20);
// printList(head);

medium

A. 10 <-> null

B. 10 <-> 20 <-> 30 <-> null

C. 20 <-> 30 <-> null

D. 10 <-> 30 <-> null

Solution

1. Step 1: Identify node to delete

   Node with value 20 is in the middle of the list 10 <-> 20 <-> 30.

2. Step 2: Update links after deletion

   After deleting 20, 10's next points to 30, and 30's prev points to 10.

3. Final Answer:

   10 <-> 30 <-> null -> Option D

4. Quick Check:

   Middle node deleted, links updated [OK]

Hint: Deleting middle node links neighbors directly [OK]

Common Mistakes:

• Not updating previous pointer of next node
• Not updating next pointer of previous node
• Leaving deleted node linked

4. Identify the bug in this delete by value function for doubly linked list:

void deleteNode(Node* &head, int val) {
  Node* temp = head;
  while (temp != nullptr && temp->data != val) {
    temp = temp->next;
  }
  if (temp == nullptr) return;
  if (temp->prev != nullptr) temp->prev->next = temp->next;
  if (temp->next != nullptr) temp->next->prev = temp->prev;
  delete temp;
}

medium

A. Does not check for null head pointer

B. Deletes all nodes with matching value

C. Does not update head if first node is deleted

D. Deletes node without freeing memory

Solution

1. Step 1: Check head update when deleting first node

   If the node to delete is the head, head pointer must be updated to next node.

2. Step 2: Verify code for head update

   Code does not update head pointer when temp->prev is nullptr (first node).

3. Final Answer:

   Does not update head if first node is deleted -> Option C

4. Quick Check:

   Head update missing for first node deletion [OK]

Hint: Update head if deleting first node [OK]

Common Mistakes:

• Forgetting to update head pointer
• Not handling empty list
• Deleting without checking node existence

5. Given a doubly linked list with nodes: 5 <-> 10 <-> 15 <-> 20, what will be the list after deleting value 5 and then value 20?

hard

A. 10 <-> 15 <-> null

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

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

D. 15 <-> null

Solution

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

   Update head to 10, set 10's prev to nullptr. List becomes 10 <-> 15 <-> 20.

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

   Update 15's next to nullptr. List becomes 10 <-> 15.

3. Final Answer:

   10 <-> 15 <-> null -> Option A

4. Quick Check:

   Deleted head and tail nodes correctly [OK]

Hint: Update head and 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