Delete by Value in Doubly Linked List in DSA C++ - Execution Trace

Concept Flow - Delete by Value in Doubly Linked List

Start at head

↓

Check if list empty?

Yes→Stop: Nothing to delete

No↓

Traverse nodes

↓

Node value == target?

No→Move to next node

Yes↓

Adjust prev and next pointers

↓

Delete node

↓

Stop or continue if multiple deletions allowed

Start from the head, traverse nodes until the target value is found, then adjust pointers of previous and next nodes to remove the target node from the list.

Execution Sample

DSA C++

void deleteByValue(Node*& head, int val) {
  if (head == nullptr) return;
  Node* prev = nullptr;
  Node* current = head;
  while (current != nullptr) {
    if (current->data == val) {
      if (prev == nullptr) {
        // deleting head
        head = current->next;
        if (head != nullptr) {
          head->prev = nullptr;
        }
      } else {
        prev->next = current->next;
        if (current->next != nullptr) {
          current->next->prev = prev;
        }
      }
      delete current;
      return;
    }
    prev = current;
    current = current->next;
  }
}

This code searches for the node with the given value and deletes it by adjusting pointers.

Execution Table

Step	Operation	Current Node Value	Pointer Changes	Visual State
1	Start at head	10	None	10 <-> 20 <-> 30 <-> 40 <-> 50
2	Check current node value == 30?	10	None	10 <-> 20 <-> 30 <-> 40 <-> 50
3	Move to next node	20	None	10 <-> 20 <-> 30 <-> 40 <-> 50
4	Check current node value == 30?	20	None	10 <-> 20 <-> 30 <-> 40 <-> 50
5	Move to next node	30	None	10 <-> 20 <-> 30 <-> 40 <-> 50
6	Found node with value 30	30	prev->next = current->next (20->next = 40) next->prev = current->prev (40->prev = 20)	10 <-> 20 <-> 40 <-> 50
7	Delete node 30	30	Node 30 removed	10 <-> 20 <-> 40 <-> 50
8	Stop traversal	N/A	None	10 <-> 20 <-> 40 <-> 50

💡 Node with value 30 found and deleted; traversal stops.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 6	Final
current	Node(10)	Node(20)	Node(30)	Node(30)	nullptr
head	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)
list size	5 nodes	5 nodes	5 nodes	4 nodes	4 nodes

Key Moments - 3 Insights

Why do we update both prev->next and next->prev pointers when deleting a node?

Because the list is doubly linked, both the previous node's next pointer and the next node's prev pointer must be updated to bypass the deleted node, as shown in step 6 of the execution_table.

What happens if the node to delete is the head node?

If the head node is deleted, the head pointer must be updated to the next node. This is shown in the code and is important to handle to keep the list accessible.

Why does traversal stop after deleting the node?

Because the function is designed to delete only the first occurrence of the value, so after deletion at step 7, traversal stops as noted in step 8.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'current' after step 5?

A Node with value 20

B Node with value 30

C Node with value 40

D nullptr

💡 Hint

Check the 'Current Node Value' column at step 5 in the execution_table.

At which step do the pointers get updated to remove the node?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look at the 'Pointer Changes' column to find when prev->next and next->prev are changed.

If the node with value 30 was not found, what would happen to the 'current' pointer?

A It would become nullptr after traversing all nodes

B It would stay at head

C It would point to the last node indefinitely

D It would point to the deleted node

💡 Hint

Refer to the variable_tracker showing 'current' progression through the list.

Concept Snapshot

Delete by Value in Doubly Linked List:
- Start at head and traverse nodes
- Compare each node's value with target
- If found, update prev->next and next->prev pointers
- Remove node from memory
- Stop after first deletion or continue if multiple deletions allowed

Full Transcript

To delete a node by value in a doubly linked list, start at the head and move through each node checking its value. When the node with the target value is found, adjust the previous node's next pointer to skip the current node, and adjust the next node's previous pointer to skip the current node as well. Then delete the current node to remove it from memory. The traversal stops after deleting the first matching node. If the node to delete is the head, the head pointer must be updated to the next node. This process ensures the list remains connected and valid after deletion.

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