Insert at End of Doubly Linked List in DSA C - Time & Space Complexity

Time Complexity: Insert at End of Doubly Linked List

O(n)

Understanding Time Complexity

We want to understand how the time needed to add a new item at the end of a doubly linked list changes as the list grows.

How does the number of steps grow when the list gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

void insertAtEnd(struct Node** head, int value) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    if (*head == NULL) {
        newNode->prev = NULL;
        *head = newNode;
        return;
    }

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

    temp->next = newNode;
    newNode->prev = temp;
}
    

This code adds a new node at the end of a doubly linked list by walking through the list to find the last node.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves through the list nodes to find the last node.
• How many times: It runs once for each node in the list until the last one is found, so roughly n times for a list of size n.

How Execution Grows With Input

As the list gets longer, the time to find the end grows roughly in a straight line with the number of nodes.

Input Size (n)	Approx. Operations
10	About 10 steps to reach the end
100	About 100 steps to reach the end
1000	About 1000 steps to reach the end

Pattern observation: The steps increase directly with the number of nodes, so doubling the list size roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert at the end grows linearly with the list size because we must walk through all nodes to find the end.

Common Mistake

[X] Wrong: "Inserting at the end is always fast and takes the same time no matter the list size."

[OK] Correct: Without a pointer to the last node, we must walk through the whole list, so bigger lists take more time.

Interview Connect

Understanding this helps you explain how linked lists work and why keeping track of the last node can speed up insertions.

Self-Check

"What if we kept a pointer to the last node? How would the time complexity change?"