Insert at Beginning (Doubly Linked List)

Inserting at the front of a DLL is O(1) when you maintain head and tail. Allocate a node, set newNode->next = head, newNode->prev = NULL, wire the old head’s prev to the new node (if the list was not empty), then move head. If the list was empty, the new node is both head and tail.

C program (insert_begin updates head and tail)

The sample passes &head and &tail so both pointers stay correct after each insert.

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

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

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

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

void free_list(struct Node *head)
{
    while (head != NULL) {
        struct Node *next = head->next;
        free(head);
        head = next;
    }
}

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

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

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

    free_list(head);
    return 0;
}

Pointer updates (non-empty list)

NULL ← [new] ↔ [old head] → …     new.prev = NULL, new.next = head
            ↑                      old_head.prev = new
         new head

Complexity

Output

After insert_begin(&head, &tail, 30), insert_begin(..., 20), and insert_begin(..., 10), then print_list(head):

Step-by-step execution table

Memory layout table

Pointer variables

• head = 0x1000 — points to Node A (first node).
• tail = 0x1010 — points to Node C (last node).

Traversal path for print_list(head)

Forward-only walk using next until NULL:

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

Output: 10 20 30

Key differences from circular linked list

Typical singly circular list (CLL) with a tail vs this open doubly linked list. See CLL Introduction for the ring model.

See also Insert at Beginning (SLL) · Insert at End (DLL) · DLL Introduction