Delete from End of Doubly Linked List in DSA C

Mental Model

To remove the last item, find the tail and unlink it from the list, updating the previous node to be the new tail.

Analogy: Imagine a train of connected cars. To remove the last car, you detach it from the second last car, making the second last car the new end of the train.

head -> 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 ← tail
null ← 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 -> null

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5, delete from end

Goal: Remove the last node (5) and update the list tail

Step 1: start at head and move forward to find last node

1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 -> null

Why: We need to find the last node to remove it

Step 2: last node (5) found, update previous node's next to null

1 ↔ 2 ↔ 3 ↔ 4 -> null  5 (removed)

Why: Disconnect last node from the list

Step 3: update tail pointer to previous node (4)

1 ↔ 2 ↔ 3 ↔ 4 ← tail -> null

Why: New tail is the node before the removed node

Result:

1 ↔ 2 ↔ 3 ↔ 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;

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

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

// Function to delete node from end
void deleteFromEnd(Node** head_ref) {
    if (*head_ref == NULL) {
        return; // empty list
    }
    Node* temp = *head_ref;
    // move to last node
    while (temp->next != NULL) {
        temp = temp->next; // advance to tail
    }
    if (temp->prev != NULL) {
        temp->prev->next = NULL; // unlink last node
    } else {
        *head_ref = NULL; // list had one node, now empty
    }
    free(temp); // free memory
}

// Function to 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(" -> null\n");
}

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

    deleteFromEnd(&head);

    printList(head);
    return 0;
}

while (temp->next != NULL) { temp = temp->next; }

advance temp to last node to find tail

if (temp->prev != NULL) { temp->prev->next = NULL; } else { *head_ref = NULL; }

unlink last node and update tail or empty list

free(temp);

free memory of removed node

Output

1 ↔ 2 ↔ 3 ↔ 4 -> null

Complexity Analysis

Time: O(n) because we traverse the list from head to tail once to find the last node

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

vs Alternative: Compared to singly linked list, doubly linked list allows easier backward traversal but still requires O(n) to find tail if no tail pointer is maintained

Edge Cases

empty list

function returns immediately without changes

DSA C

if (*head_ref == NULL) { return; }

list with one node

node is removed and head is set to NULL

DSA C

else { *head_ref = NULL; }

When to Use This Pattern

When you need to remove the last element from a doubly linked list, look for a pattern that finds the tail and updates the previous node's next pointer to null.

Common Mistakes

Mistake: Not updating the previous node's next pointer to null, leaving a dangling pointer
Fix: Set temp->prev->next = NULL before freeing the last node

Mistake: Not handling the case when the list has only one node
Fix: Check if temp->prev is NULL and update head to NULL accordingly

Summary

Deletes the last node from a doubly linked list by unlinking it and updating pointers.

Use when you want to remove the tail element from a doubly linked list.

The key is to find the last node, unlink it from its previous node, and update the tail reference.