Insert at End (DLL)

Insert at End (Doubly Linked List)

With a tail pointer, appending is O(1): link the old tail’s next to the new node, set the new node’s prev to the old tail, set next to NULL, then advance tail. An empty list treats the new node as both head and tail.

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 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_end(&head, &tail, 10);
    insert_end(&head, &tail, 20);
    insert_end(&head, &tail, 30);

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

    free_list(head);
    return 0;
}

Complexity

Operation	Time
`insert_end` (with `tail`)	`O(1)`

Output

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

10 20 30

Step-by-step execution table

Step	Operation	List state (forward)	List state (backward)	`head` points to	`tail` points to
1	`insert_end(10)`	`10`	`10`	Node `10`	Node `10`
2	`insert_end(20)`	`10 → 20`	`20 → 10`	Node `10`	Node `20`
3	`insert_end(30)`	`10 → 20 → 30`	`30 → 20 → 10`	Node `10`	Node `30`

Memory layout table

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

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

Traversal path for `print_list(head)`

Forward 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

Comparison: `insert_begin` vs `insert_end`

Feature	`insert_begin` (previous example)	`insert_end` (this example)
Insertion position	At the beginning (`head`)	At the end (`tail`)
Final `head`	Points to last inserted (`10`)	Points to first inserted (`10`)
Final `tail`	Points to first inserted (`30`)	Points to last inserted (`30`)
Node order	Reverse of insertion order	Same as insertion order
Time complexity	`O(1)`	`O(1)` with `tail` pointer
Code symmetry	Updates `head` pointer	Updates `tail` pointer

Key operations in `insert_end`

Line / idea	Operation	Purpose
`n->next = NULL`	Set `next` to `NULL`	Marks new node as last in the chain
`if (*head == NULL)`	Check empty list	First-node case: `head` and `tail` both become `n`
`n->prev = *tail`	Link to current tail	Maintain backward link from new last node
`(*tail)->next = n`	Link current tail to new node	Maintain forward link into the new tail
`*tail = n`	Update `tail` pointer	New last node for the next append

The output 10 20 30 shows the list printed in the same order as insertion (10 first, then 20, then 30), demonstrating successful insertions at the end.

Unlike a singly linked list with only head, you do not need a full scan to find the last node when tail is maintained. See Insert at End (SLL) · Insert at Beginning (DLL)