Create and Initialize Doubly Linked List in DSA Python - 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 it takes grows as we add more items.

We ask: How does the work increase when 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.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self, values):
        self.head = None
        self.tail = None
        for value in values:
            new_node = Node(value)
            if not self.head:
                self.head = new_node
                self.tail = new_node
            else:
                self.tail.next = new_node
                new_node.prev = self.tail
                self.tail = new_node

This code creates a doubly linked list from a list of values by adding nodes one by one at the end.

Identify Repeating Operations

• Primary operation: Looping through each value in the input list to create and link nodes.
• How many times: Exactly once for each value in the input list.

How Execution Grows With Input

Each new value causes one node to be created and linked, so the work grows directly with the number of values.

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 work increases evenly as the list gets longer, doubling the input doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to create the list grows in a straight line with the number of items you add.

Common Mistake

[X] Wrong: "Creating the list takes the same time no matter how many items there are."

[OK] Correct: Each item requires a new node and linking, so more items mean more work.

Interview Connect

Understanding how creating a linked list scales helps you explain your code clearly and shows you know how data structures behave as they grow.

Self-Check

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