Creating a Singly Linked List from Scratch in DSA C - Complexity Walkthrough

Time Complexity: Creating a Singly Linked List from Scratch

O(n)

Understanding Time Complexity

When we create a singly linked list from scratch, we add nodes one by one. Understanding time complexity helps us see how the work grows as we add more nodes.

We want to know: How much time does it take to build the whole list as it gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

struct Node* createList(int arr[], int n) {
    struct Node* head = NULL;
    struct Node* tail = NULL;
    for (int i = 0; i < n; i++) {
        struct Node* newNode = malloc(sizeof(struct Node));
        newNode->data = arr[i];
        newNode->next = NULL;
        if (head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    return head;
}
    

This code creates a singly linked list by adding each element from an array to the end of the list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop runs through each element of the input array once.
• How many times: Exactly n times, where n is the number of elements.

How Execution Grows With Input

Each new node is created and linked once per element, so the work grows directly with the number of elements.

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

Pattern observation: The number of operations grows linearly as the input size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to create the list grows in direct proportion to the number of elements we add.

Common Mistake

[X] Wrong: "Adding each node to the end takes constant time, so the whole list creation is faster than linear."

[OK] Correct: While adding to the end is constant time here because we keep a tail pointer, if we did not keep track of the tail, each addition would require traversing the list, making it slower.

Interview Connect

Knowing how list creation scales helps you explain your code clearly and shows you understand how data structures work under the hood. This skill is useful in many coding tasks and interviews.

Self-Check

"What if we did not keep a tail pointer and instead found the end of the list each time we added a node? How would the time complexity change?"