Create and Initialize Doubly Linked List in DSA C - Time & Space Complexity

Time Complexity: Create and Initialize Doubly Linked List

O(n)

Understanding Time Complexity

When we create and initialize a doubly linked list, we want to know how the time needed grows as we add more nodes.

We ask: How long does it take to build the list as its size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

struct Node* createList(int n) {
    struct Node* head = NULL;
    struct Node* temp = NULL;
    for (int i = 0; i < n; i++) {
        struct Node* newNode = malloc(sizeof(struct Node));
        newNode->data = i;
        newNode->prev = temp;
        newNode->next = NULL;
        if (temp != NULL) temp->next = newNode;
        else head = newNode;
        temp = newNode;
    }
    return head;
}
    

This code creates a doubly linked list with n nodes, linking each new node to the previous one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that runs n times to create and link nodes.
• How many times: Exactly once for each node from 0 to n-1, so n times.

How Execution Grows With Input

Each new node requires a fixed number of steps to create and link it. So, as n grows, the total steps grow in a straight line.

Input Size (n)	Approx. Operations
10	About 10 node creations and linkings
100	About 100 node creations and linkings
1000	About 1000 node creations and linkings

Pattern observation: The work grows directly with n; doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to create the list grows linearly with the number of nodes.

Common Mistake

[X] Wrong: "Creating each node takes constant time, so the whole list creation is constant time."

[OK] Correct: Even though each node is made quickly, you must do it n times, so total time grows with n, not stays the same.

Interview Connect

Understanding how list creation scales helps you explain efficiency clearly and shows you know how data structures behave as they grow.

Self-Check

"What if we added nodes at the head instead of the tail? How would the time complexity change?"