Delete from Beginning (Doubly Linked List)

Remove the head: advance head, set the new head’s prev to NULL, free the old node. If the list had one node, clear both head and tail. O(1) time.

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_begin(struct Node **head, struct Node **tail)
{
    if (*head == NULL)
        return;
    struct Node *h = *head;
    if (*head == *tail) {
        free(h);
        *head = *tail = NULL;
        return;
    }
    *head = h->next;
    (*head)->prev = NULL;
    free(h);
}

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_begin(&head, &tail);
    delete_begin(&head, &tail);
    delete_begin(&head, &tail);

    print_list(head);   /* empty */

    return 0;
}

Output

First print_list(head) after building the list with three insert_end calls:

10 20 30

After three delete_begin calls, the second print_list(head) prints only a newline (empty list; head and tail are NULL).

Step-by-step execution table

List starts as 10 → 20 → 30 with head at 10 and tail at 30. Each delete_begin removes the current first node.

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_begin() 20 → 30 30 → 20 Node 20 Node 30
2 delete_begin() 30 30 Node 30 Node 30
3 delete_begin() empty empty NULL NULL

Memory layout table (before first delete)

Example addresses for 10 20 30 — nodes A, B, C:

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

After each delete_begin, the old head block is freed; addresses above are invalid for freed nodes.

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_begin vs delete_end

Feature delete_begin delete_end
Removes Current first node (head) Current last node (tail)
Updates head → old head->next; new head’s prev = NULL tail → old tail->prev; new tail’s next = NULL
Time (with head/tail) O(1) O(1) in DLL (uses prev)
Single-node list head and tail both set NULL Same

Key operations in delete_begin

Code / idea Purpose
if (*head == *tail) One node: free it and clear both head and tail
*head = h->next Advance head to the second node
(*head)->prev = NULL New front has no predecessor
free(h) Release the old first node

See Delete from Beginning (SLL) · Delete from End (DLL)