Insert at End of Doubly Linked List in DSA C

Mental Model

A doubly linked list has nodes connected both forward and backward. To add a new node at the end, we link it after the last node and update pointers.

Analogy: Imagine a train where each carriage is connected to the one before and after. Adding a new carriage at the end means hooking it to the last carriage and making sure both know about each other.

head -> [1] ↔ [2] ↔ [3] ↔ null
null ← [1] ↔ [2] ↔ [3] ← tail

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3, insert value 4 at end

Goal: Add a new node with value 4 at the end of the doubly linked list

Step 1: Create new node with value 4

head -> [1] ↔ [2] ↔ [3] ↔ null    [4] (new node, prev=null, next=null)
null ← [1] ↔ [2] ↔ [3] ← tail

Why: We need a new node ready to be linked at the end

Step 2: Traverse from head to last node (3)

head -> [1] ↔ [2] ↔ [3] (current) ↔ null    [4] (new node)
null ← [1] ↔ [2] ↔ [3] ← tail

Why: We must find the last node to attach the new node after it

Step 3: Set last node's next pointer to new node

head -> [1] ↔ [2] ↔ [3] -> [4] (new node)
null ← [1] ↔ [2] ↔ [3] ←-> [4]

Why: Link last node forward to new node

Step 4: Set new node's prev pointer to last node

head -> [1] ↔ [2] ↔ [3] ↔ [4]
null ← [1] ↔ [2] ↔ [3] ←-> [4]

Why: Link new node backward to last node

Step 5: Set new node's next pointer to null (end)

head -> [1] ↔ [2] ↔ [3] ↔ [4] -> null
null ← [1] ↔ [2] ↔ [3] ←-> [4] ← tail

Why: Mark new node as the last node

Result:

head -> [1] ↔ [2] ↔ [3] ↔ [4] -> null
null ← [1] ↔ [2] ↔ [3] ←-> [4] ← tail

Annotated Code

DSA C

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

// Node structure for doubly linked list
typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

// Function to create a new node with given data
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// Function to insert a node at the end of the doubly linked list
void insertAtEnd(Node** head_ref, int data) {
    Node* newNode = createNode(data); // create new node

    if (*head_ref == NULL) {
        *head_ref = newNode; // list empty, new node is head
        return;
    }

    Node* temp = *head_ref;
    while (temp->next != NULL) {
        temp = temp->next; // advance to last node
    }

    temp->next = newNode; // link last node forward
    newNode->prev = temp; // link new node backward
}

// Function to print the doubly linked list
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d", temp->data);
        if (temp->next != NULL) {
            printf(" ↔ ");
        }
        temp = temp->next;
    }
    printf(" -> null\n");
}

int main() {
    Node* head = NULL;

    // Create initial list 1 ↔ 2 ↔ 3
    insertAtEnd(&head, 1);
    insertAtEnd(&head, 2);
    insertAtEnd(&head, 3);

    // Insert 4 at end
    insertAtEnd(&head, 4);

    // Print final list
    printList(head);

    return 0;
}

Node* newNode = createNode(data); // create new node

create new node with given data

if (*head_ref == NULL) { *head_ref = newNode; // list empty, new node is head return; }

handle empty list by making new node the head

while (temp->next != NULL) { temp = temp->next; // advance to last node }

traverse to last node in list

temp->next = newNode; // link last node forward

link last node's next to new node

newNode->prev = temp; // link new node backward

link new node's prev to last node

Output

1 ↔ 2 ↔ 3 ↔ 4 -> null

Complexity Analysis

Time: O(n) because we traverse the list from head to last node once

Space: O(1) because we only create one new node and use constant extra space

vs Alternative: Compared to inserting at the beginning which is O(1), inserting at end requires traversal making it O(n)

Edge Cases

empty list

new node becomes the head and only node

DSA C

if (*head_ref == NULL) {
        *head_ref = newNode; // list empty, new node is head
        return;
    }

single element list

new node is linked after the single node correctly

DSA C

while (temp->next != NULL) {
        temp = temp->next; // advance to last node
    }

When to Use This Pattern

When you need to add an element at the end of a doubly linked list, use traversal to find the last node and update pointers to insert.

Common Mistakes

Mistake: Not updating the new node's prev pointer to point back to the last node
Fix: Set newNode->prev = temp after linking last node's next to new node

Mistake: Not handling empty list case, causing null pointer errors
Fix: Check if head is NULL and assign new node as head before traversal

Summary

Adds a new node at the end of a doubly linked list by updating next and prev pointers.

Use when you want to append data to the tail of a doubly linked list.

The key is to find the last node and link the new node both forward and backward.