Delete from End (DLL)

Delete from End (Doubly Linked List)

With a tail pointer, removing the last node is O(1): move tail to tail->prev, set its next to NULL, and free the old tail. This is a major advantage over a singly linked list, where delete-at-end usually requires an O(n) walk to find the predecessor unless you use extra tricks.

C program

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

struct Node {
    int data;
    struct Node *prev;
    struct Node *next;
};

void insert_end(struct Node **head, struct Node **tail, int data)
{
    struct Node *n = malloc(sizeof(struct Node));
    if (n == NULL)
        return;
    n->data = data;
    n->next = NULL;
    if (*head == NULL) {
        n->prev = NULL;
        *head = *tail = n;
        return;
    }
    n->prev = *tail;
    (*tail)->next = n;
    *tail = n;
}

void delete_end(struct Node **head, struct Node **tail)
{
    if (*head == NULL)
        return;
    if (*head == *tail) {
        free(*head);
        *head = *tail = NULL;
        return;
    }
    struct Node *t = *tail;
    *tail = t->prev;
    (*tail)->next = NULL;
    free(t);
}

void print_list(struct Node *head)
{
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

int main(void)
{
    struct Node *head = NULL;
    struct Node *tail = NULL;

    insert_end(&head, &tail, 10);
    insert_end(&head, &tail, 20);
    insert_end(&head, &tail, 30);

    print_list(head);   /* 10 20 30 */

    delete_end(&head, &tail);
    delete_end(&head, &tail);
    delete_end(&head, &tail);

    print_list(head);   /* empty */

    return 0;
}

Output

First print_list(head) after three insert_end calls:

10 20 30

After three delete_end calls, the second print_list prints only a newline (empty list).

Step-by-step execution table

Each delete_end removes the current last node; tail moves backward via prev.

Step	Operation	List state (forward)	List state (backward)	`head`	`tail`
0	(after `insert_end` ×3)	`10 → 20 → 30`	`30 → 20 → 10`	Node `10`	Node `30`
1	`delete_end()`	`10 → 20`	`20 → 10`	Node `10`	Node `20`
2	`delete_end()`	`10`	`10`	Node `10`	Node `10`
3	`delete_end()`	empty	empty	`NULL`	`NULL`

Memory layout table (before first delete)

Address	Node	`data`	`prev`	`next`	Points to (`prev` / `next`)
`0x1000`	Node A	10	`NULL`	`0x1008`	`prev`: `NULL`, `next`: Node B
`0x1008`	Node B	20	`0x1000`	`0x1010`	`prev`: Node A, `next`: Node C
`0x1010`	Node C	30	`0x1008`	`NULL`	`prev`: Node B, `next`: `NULL`

Pointer variables (initial list)

head = 0x1000 — Node A (first).
tail = 0x1010 — Node C (last).

Traversal path for `print_list(head)` (before deletes)

Start at head (0x1000) → Node A [10]
    ↓ (next)
Node B [20]
    ↓ (next)
Node C [30]
    ↓ (next)
NULL → Stop

Output: 10 20 30

Comparison: `delete_end` (DLL) vs SLL delete-at-end

Feature	DLL with `tail`	SLL with only `head`
Find predecessor of tail	`O(1)` via `tail->prev`	`O(n)` walk from head
Update last link	`(*tail)->prev` becomes new `tail`; set `next = NULL`	Second-last node’s `next = NULL`
Time	`O(1)`	`O(n)` without extra pointers

Key operations in `delete_end`

Code / idea	Purpose
`if (head == tail)`	Single node: `free` and null both pointers
`*tail = t->prev`	New last node is the old tail’s predecessor
`(*tail)->next = NULL`	Open chain ends at the new tail
`free(t)`	Release the removed last node

Compare Delete from End (SLL) — linear scan without prev. · Delete from Beginning (DLL)