Delete from Beginning

Removing the first node means: if head == NULL, there is nothing to delete; otherwise save head->next, free(head), and return the saved pointer as the new head. No loop is needed—O(1) time and O(1) extra space for the one pointer you keep.

C program (return new `head`)

The sample uses insert_begin (same idea as insert at beginning) to build 10 20 30 by inserting 30, then 20, then 10 at the head. Then it calls delete_begin three times. In main always assign head = delete_begin(head); so the list stays consistent.

delete_begin only frees the old head node (not a full free_list sweep).
After the last delete, head is NULL and the list is empty.

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

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

struct Node *insert_begin(struct Node *head, int data)
{
    struct Node *newNode = malloc(sizeof(struct Node));
    if (newNode == NULL)
        return head;

    newNode->data = data;
    newNode->next = head;
    return newNode;
}

struct Node *delete_begin(struct Node *head)
{
    if (head == NULL)
        return NULL;

    struct Node *next = head->next;
    free(head);
    return next;
}

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

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

    head = insert_begin(head, 30);
    head = insert_begin(head, 20);
    head = insert_begin(head, 10);

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

    head = delete_begin(head);
    head = delete_begin(head);
    head = delete_begin(head);

    print_list(head);   /* empty list: newline only */

    return 0;
}

Program output

10 20 30

First print_list shows the list. After three delete_begin calls, the second print_list prints only a newline (no numbers).

Overall program flow

Step	Operation	`head` points to	List state (values)
1	`head = NULL`	`NULL`	Empty list
2	`head = insert_begin(head, 30)`	Single node `30` at `0x1000`	`30`
3	`head = insert_begin(head, 20)`	New head `0x2000` → old head `0x1000`	`20 30`
4	`head = insert_begin(head, 10)`	New head `0x3000` → `0x2000` → `0x1000`	`10 20 30`
5	`print_list(head)`	`0x3000`	Output line: `10 20 30`
6	`head = delete_begin(head)`	Was second node `0x2000`	`20 30` (head `10` at `0x3000` freed)
7	`head = delete_begin(head)`	Was third node `0x1000`	`30` (node `20` at `0x2000` freed)
8	`head = delete_begin(head)`	`NULL`	Empty (node `30` at `0x1000` freed)
9	`print_list(head)`	`NULL`	Output: newline only

Each `delete_begin` call in detail

Call 1: delete_begin(0x3000) — list 10 → 20 → 30

Step	Operation	Variable	Value
1	`head == NULL`?	`head`	No
2	`next = head->next`	`next`	`0x2000`
3	`free(head)`	—	Block at `0x3000` released
4	`return next`	return value	`0x2000` (new `head`)

After call 1:

head → [20 | 0x1000] → [30 | NULL]

Call 2: delete_begin(0x2000) — list 20 → 30

Step	Operation	Variable	Value
1	`next = head->next`	`next`	`0x1000`
2	`free(head)`	—	Block at `0x2000` released
3	`return next`	return value	`0x1000`

After call 2:

head → [30 | NULL]

Call 3: delete_begin(0x1000) — single node 30

Step	Operation	Variable	Value
1	`next = head->next`	`next`	`NULL`
2	`free(head)`	—	Block at `0x1000` released
3	`return next`	return value	`NULL`

After call 3:

head → NULL

Memory layout (example addresses)

List before any delete_begin (after inserts)

Address	Node	`data`	`next`	Points to
`0x3000`	`n1` (head, inserted last)	10	`0x2000`	`n2`
`0x2000`	`n2` (inserted 2nd)	20	`0x1000`	`n3`
`0x1000`	`n3` (inserted first)	30	`NULL`	nowhere

Visual representation

Before the first delete (after building with insert_begin):

head (0x3000)
   │
   ▼
┌──────────────┐    ┌──────────────┐    ┌──────────────┐
│ data: 10     │    │ data: 20     │    │ data: 30     │
│ next: 0x2000 ┼───→│ next: 0x1000 ┼───→│ next: NULL   │
└──────────────┘    └──────────────┘    └──────────────┘
     n1                   n2                   n3
 (inserted last)     (inserted 2nd)      (inserted first)

Detailed step-by-step: call 3 (delete only node `30`)

Inside delete_begin when head is 0x1000 and that node is [30 | NULL]:

Line	Code	Before	After
1	`if (head == NULL)`	`head = 0x1000`	Skip `return NULL`
2	`struct Node *next = head->next;`	`0x1000->next` is `NULL`	`next = NULL`
3	`free(head);`	Heap block `0x1000`	Memory returned to allocator
4	`return next;`	`next = NULL`	In `main`: `head = NULL`

Complexity summary

Operation	Time	Extra space
`delete_begin`	`O(1)`	`O(1)` (pointer `next`)
`insert_begin` (used to build the demo list)	`O(1)` per call	`O(1)` per new node
`print_list`	`O(n)`	`O(1)`
Whole program (build + print + deletes + print)	Build `O(n)` for `n` head inserts (each `O(1)`); each delete `O(1)`; prints `O(n)`	`O(n)` nodes max on heap before deletes drain them

The key takeaway is that delete from the beginning is O(1) time: you only read the second pointer, free the old head, and return—no scan of the rest of the list.

Alternative: pass struct Node **head and set *head = (*head)->next after free(*head) (careful: save next before freeing).