Delete by Value in Doubly Linked List in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a doubly linked list?

A doubly linked list is a chain of nodes where each node has three parts: data, a pointer to the next node, and a pointer to the previous node. This allows traversal in both directions.

beginner

Why do we need to update both next and previous pointers when deleting a node in a doubly linked list?

Because each node links to both its next and previous nodes, deleting a node requires updating the previous node's next pointer and the next node's previous pointer to keep the list connected.

intermediate

What happens if the node to delete is the head of the doubly linked list?

If the node to delete is the head, we update the head pointer to the next node and set the new head's previous pointer to null.

intermediate

In C++, what is the importance of deleting the node after unlinking it from the doubly linked list?

Deleting the node frees the memory allocated for it, preventing memory leaks. Unlinking alone only removes it from the list but does not free memory.

beginner

What is the time complexity of deleting a node by value in a doubly linked list?

The time complexity is O(n) because we may need to traverse the list to find the node with the given value before deleting it.

When deleting a node by value in a doubly linked list, which pointers must be updated?

A No pointers need updating

B Only the head pointer

C Only the tail pointer

D Previous node's next and next node's previous pointers

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

If the node to delete is the last node in the doubly linked list, what should be updated?

A The previous node's next pointer to null

B The next node's previous pointer to null

C The head pointer

D No updates needed

The previous node's next pointer should be set to null because the last node is being removed.

What is the first step when deleting a node by value in a doubly linked list?

A Free the memory immediately

B Traverse the list to find the node with the value

C Update the tail pointer

D Delete the head node

You must first find the node with the given value by traversing the list.

What happens if the value to delete is not found in the doubly linked list?

A No deletion occurs; the list remains unchanged

B The head node is deleted

C The tail node is deleted

D The entire list is cleared

If the value is not found, no node is deleted and the list stays the same.

Why is a doubly linked list preferred over a singly linked list for deletion by value?

A Because it uses less memory

B Because it has faster insertion at the head

C Because it allows backward traversal to update previous pointers easily

D Because it does not require pointers

Doubly linked lists have pointers to previous nodes, making deletion easier by updating both sides.

Explain step-by-step how to delete a node by value in a doubly linked list.

Think about how links before and after the node change.

Describe how deleting the head node differs from deleting a middle node in a doubly linked list.

Focus on the special role of the head pointer.

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