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

Time Complexity: Creating a Singly Linked List from Scratch

O(n^2)

Understanding Time Complexity

When we create a singly linked list from scratch, we add nodes one by one. Understanding how the time needed grows as we add more nodes helps us write better code.

We want to know: How does the time to build the list change as the list gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

This code creates a singly linked list and adds new nodes at the end one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop inside the append method that moves through the list to find the last node.
• How many times: For each new node added, the loop runs once for each existing node in the list until it reaches the end.

How Execution Grows With Input

As the list grows, adding a new node takes longer because we must walk through all existing nodes to find the end.

Input Size (n)	Approx. Operations
10	About 1 + 2 + ... + 10 = 55 steps
100	About 1 + 2 + ... + 100 = 5,050 steps
1000	About 1 + 2 + ... + 1000 = 500,500 steps

Pattern observation: The total steps grow roughly with the square of the number of nodes, because each append walks through the list.

Final Time Complexity

Time Complexity: O(n2)

This means that adding n nodes one by one like this takes time proportional to n squared, because each new node requires walking through the whole list so far.

Common Mistake

[X] Wrong: "Appending a node always takes the same time, so building the whole list is O(n)."

[OK] Correct: Without keeping track of the last node, each append must walk through the entire list, making later appends slower and total time grow faster than just n.

Interview Connect

Knowing how linked list operations scale helps you explain trade-offs clearly. This skill shows you understand how data structures work under the hood, which is valuable in real coding tasks.

Self-Check

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