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.