Delete by Value in Doubly Linked List in DSA C - Time & Space Complexity

Time Complexity: Delete by Value in Doubly Linked List

O(n)

Understanding Time Complexity

When deleting a node by value in a doubly linked list, we want to know how long it takes as the list grows.

We ask: How does the time to find and delete a value change with list size?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void deleteByValue(Node** head, int value) {
    Node* current = *head;
    while (current != NULL && current->data != value) {
        current = current->next;
    }
    if (current == NULL) return; // value not found
    if (current->prev != NULL) current->prev->next = current->next;
    else *head = current->next;
    if (current->next != NULL) current->next->prev = current->prev;
    free(current);
}
    

This code searches for the first node with the given value and removes it from the doubly linked list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves through nodes to find the value.
• How many times: Up to n times, where n is the number of nodes in the list.

How Execution Grows With Input

As the list grows, the search may take longer because it might check more nodes.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The number of steps grows roughly in direct proportion to the list size.

Final Time Complexity

Time Complexity: O(n)

This means the time to delete by value grows linearly with the number of nodes in the list.

Common Mistake

[X] Wrong: "Deleting by value is always fast because we just remove one node."

[OK] Correct: You must first find the node, which can take time proportional to the list size if the value is near the end or missing.

Interview Connect

Understanding this helps you explain how searching affects deletion speed in linked lists, a common topic in coding interviews.

Self-Check

"What if the list was sorted? How would that change the time complexity of deleting by value?"

Practice

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

easy

A. Only the first node is deleted without checking value

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

C. All nodes are deleted regardless of 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:

   Deleting by value removes matching node [OK]

Hint: Find node by value, then fix links to remove it [OK]

Common Mistakes:

• Not updating previous node's next pointer
• Not updating next node's previous pointer
• Deleting wrong node without checking value

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 deleteByValue(Node** head, int val) { /* code */ }

B. int deleteByValue(Node head, int val) { /* code */ }

C. void deleteByValue(Node* head, int val) { /* code */ }

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

Solution

1. Step 1: Understand pointer usage for head modification

   Since deleting a node may change the head pointer, we pass a pointer to the head pointer (Node** head).

2. Step 2: Confirm function return type

   The function deletes a node and does not return a node or int, so return type is void.

3. Final Answer:

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

4. Quick Check:

   Use double pointer to modify head [OK]

Hint: Use Node** to allow head pointer changes [OK]

Common Mistakes:

• Passing head as single pointer when head may change
• Returning wrong type from delete function
• Not using void when no return needed

3. What will be the output list after deleting value 3 from the doubly linked list: 1 <-> 3 <-> 5 <-> 3 <-> 7?

medium

A. 1 <-> 3 <-> 5 <-> 7

B. 3 <-> 5 <-> 3 <-> 7

C. 1 <-> 5 <-> 7

D. 1 <-> 5 <-> 3 <-> 7

Solution

1. Step 1: Identify which node is deleted

   Deleting by value removes the first node with value 3, which is the second node in the list.

2. Step 2: Update links and list after deletion

   After removing the first 3, the list becomes 1 <-> 5 <-> 3 <-> 7, keeping the second 3 intact.

3. Final Answer:

   1 <-> 5 <-> 3 <-> 7 -> Option D

4. Quick Check:

   Only first matching node deleted [OK]

Hint: Delete only first matching node by value [OK]

Common Mistakes:

• Deleting all nodes with value 3 instead of first
• Not updating links correctly after deletion
• Deleting wrong node (like last 3 instead of first)

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

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

medium

A. Loops infinitely when value not found

B. Does not free memory of deleted node

C. Does not update head if first node is deleted

D. Deletes all nodes with matching value

Solution

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

   If the node to delete is the head, the head pointer must be updated to the next node, but this code does not do that.

2. Step 2: Confirm other parts are correct

   Memory is freed, loop ends correctly, and only one node is deleted, so no other errors.

3. Final Answer:

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

4. Quick Check:

   Update head pointer when deleting first node [OK]

Hint: Always update head if deleting first node [OK]

Common Mistakes:

• Forgetting to update head pointer
• Not freeing memory after deletion
• Incorrect loop causing infinite iteration

5. You have a doubly linked list with nodes: 10 <-> 20 <-> 30 <-> 40. You want to delete the node with value 10 and then insert a new node with value 5 at the head. What will be the final list?

hard

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

B. 10 <-> 5 <-> 20 <-> 30 <-> 40

C. 20 <-> 30 <-> 40 <-> 5

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

Solution

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

   Removing the head node 10 updates the head pointer to node 20, so list becomes 20 <-> 30 <-> 40.

2. Step 2: Insert new node with value 5 at head

   Create a new node with value 5, set its next to current head (20), update 20's prev to new node, and update head pointer to new node.

3. Step 3: Final list after operations

   The list is now 5 <-> 20 <-> 30 <-> 40.

4. Final Answer:

   5 <-> 20 <-> 30 <-> 40 -> Option A

5. Quick Check:

   Delete head, then insert new head [OK]

Hint: Delete head, then insert new node at head [OK]

Common Mistakes:

• Not updating head after deletion
• Not linking new node correctly at head
• Appending new node at tail instead of head