Insert at Beginning of Doubly Linked List in DSA Python - Time & Space Complexity

Time Complexity: Insert at Beginning of Doubly Linked List

O(1)

Understanding Time Complexity

We want to know how the time to insert a new node at the start of a doubly linked list changes as the list grows.

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

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):
        self.head = None

    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        if self.head is not None:
            self.head.prev = new_node
        self.head = new_node

This code adds a new node at the start of a doubly linked list by adjusting pointers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Assigning pointers to link the new node at the start.
• How many times: These pointer assignments happen once per insertion, no loops or recursion.

How Execution Grows With Input

Each insertion requires the same fixed number of steps, no matter how big the list is.

Input Size (n)	Approx. Operations
10	3-4 pointer assignments
100	3-4 pointer assignments
1000	3-4 pointer assignments

Pattern observation: The number of steps stays the same regardless of list size.

Final Time Complexity

Time Complexity: O(1)

This means inserting at the beginning takes a constant amount of time no matter how large the list is.

Common Mistake

[X] Wrong: "Inserting at the beginning takes longer as the list grows because we have to move all nodes."

[OK] Correct: We only change a few pointers at the start; we do not move or touch the other nodes.

Interview Connect

Knowing that insertion at the start of a doubly linked list is quick helps you explain efficient data structure operations clearly.

Self-Check

"What if we had to insert at the end of the doubly linked list without a tail pointer? How would the time complexity change?"