Delete by Value in Doubly Linked List in DSA C

Mental Model

We find the node with the given value and remove it by linking its previous and next nodes directly.

Analogy: Imagine a train with cars linked together. Removing a car means connecting the car before it directly to the car after it, skipping the removed car.

null ← 1 ↔ 2 ↔ 3 ↔ 4 -> null
           ↑
         current

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3 ↔ 4, delete value 3

Goal: Remove the node with value 3 and keep the list connected

Step 1: start at head node with value 1

null ← [1] ↔ 2 ↔ 3 ↔ 4 -> null

Why: We begin searching from the start of the list

Step 2: move to next node with value 2

null ← 1 ↔ [2] ↔ 3 ↔ 4 -> null

Why: Value 1 is not 3, so continue searching

Step 3: move to next node with value 3

null ← 1 ↔ 2 ↔ [3] ↔ 4 -> null

Why: Found the node with value 3 to delete

Step 4: link node with value 2 to node with value 4, skipping 3

null ← 1 ↔ 2 ↔ 4 -> null

Why: Remove node 3 by connecting its neighbors directly

Result:

null ← 1 ↔ 2 ↔ 4 -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure for doubly linked list
typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

// Create a new node with given data
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// Append node at the end
void append(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

// Delete first node with given value
void deleteByValue(Node** head, int value) {
    Node* curr = *head;
    while (curr != NULL && curr->data != value) {
        curr = curr->next; // advance curr to next node
    }
    if (curr == NULL) {
        return; // value not found, nothing to delete
    }
    if (curr->prev != NULL) {
        curr->prev->next = curr->next; // link previous node to next
    } else {
        *head = curr->next; // deleting head node
    }
    if (curr->next != NULL) {
        curr->next->prev = curr->prev; // link next node to previous
    }
    free(curr); // free memory of deleted node
}

// Print list forward
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d", temp->data);
        if (temp->next != NULL) {
            printf(" ↔ ");
        }
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    Node* head = NULL;
    append(&head, 1);
    append(&head, 2);
    append(&head, 3);
    append(&head, 4);

    printf("Original list:\n");
    printList(head);

    deleteByValue(&head, 3);

    printf("List after deleting value 3:\n");
    printList(head);

    return 0;
}

while (curr != NULL && curr->data != value) { curr = curr->next; // advance curr to next node }

search for node with target value

if (curr == NULL) { return; // value not found, nothing to delete }

stop if value not found

if (curr->prev != NULL) { curr->prev->next = curr->next; // link previous node to next } else { *head = curr->next; // deleting head node }

unlink node from previous or update head if first node

if (curr->next != NULL) { curr->next->prev = curr->prev; // link next node to previous }

unlink node from next

free(curr); // free memory of deleted node

release memory of removed node

Output

Original list:

1 ↔ 2 ↔ 3 ↔ 4

List after deleting value 3:

1 ↔ 2 ↔ 4

Complexity Analysis

Time: O(n) because we may need to traverse the entire list to find the value

Space: O(1) because we only use a few pointers and no extra data structures

vs Alternative: Compared to singly linked list deletion, doubly linked list allows direct access to previous node, making unlinking easier without extra traversal

Edge Cases

empty list

function returns immediately, no deletion

DSA C

if (curr == NULL) {
        return; // value not found, nothing to delete
    }

value not found in list

function returns without changes

DSA C

if (curr == NULL) {
        return; // value not found, nothing to delete
    }

deleting head node

head pointer updates to next node

DSA C

else {
        *head = curr->next; // deleting head node
    }

deleting tail node

previous node's next pointer set to NULL

DSA C

if (curr->next != NULL) {
        curr->next->prev = curr->prev; // link next node to previous
    }

When to Use This Pattern

When you need to remove a specific value from a list that can go forward and backward, use delete by value in doubly linked list to unlink nodes easily.

Common Mistakes

Mistake: Not updating the head pointer when deleting the first node
Fix: Check if the node to delete is head and update the head pointer accordingly

Mistake: Not updating the prev pointer of the next node after deletion
Fix: Always update the next node's prev pointer to skip the deleted node

Summary

Deletes the first node with a given value by reconnecting its neighbors in a doubly linked list.

Use when you want to remove a specific value from a doubly linked list efficiently.

The key is to link the previous and next nodes directly, skipping the node to delete.

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