Insert at Specific Position in Doubly Linked List in DSA Python - Time & Space Complexity

Time Complexity: Insert at Specific Position in Doubly Linked List

O(n)

Understanding Time Complexity

When inserting a new item at a certain place in a doubly linked list, we want to know how the time needed changes as the list grows.

We ask: How does the number of steps grow 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

def insert_at_position(head, data, pos):
    new_node = Node(data)
    if pos == 0:
        new_node.next = head
        if head:
            head.prev = new_node
        return new_node
    current = head
    for _ in range(pos - 1):
        if current is None:
            return head
        current = current.next
    if current is None:
        return head
    new_node.next = current.next
    if current.next:
        current.next.prev = new_node
    current.next = new_node
    new_node.prev = current
    return head
    

This code inserts a new node at a given position in a doubly linked list by moving through the list to find the right spot.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that moves through the list nodes to reach the position before insertion.
• How many times: Up to pos - 1 times, which depends on the position where we insert.

How Execution Grows With Input

As the list gets longer, the steps to reach the insertion point grow roughly in direct proportion to the position.

Input Size (n)	Approx. Operations
10	Up to 9 steps to reach position
100	Up to 99 steps to reach position
1000	Up to 999 steps to reach position

Pattern observation: The time grows linearly with the position where we insert, which can be up to the size of the list.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert grows in a straight line with the list size or the position where we insert.

Common Mistake

[X] Wrong: "Inserting at any position in a doubly linked list always takes constant time because we have links both ways."

[OK] Correct: Even with links both ways, we must first find the position by moving through nodes, which takes time proportional to the position.

Interview Connect

Understanding how insertion time depends on position helps you explain and reason about linked list operations clearly, a skill valued in many coding discussions.

Self-Check

"What if we kept a pointer to the tail and inserted near the end? How would the time complexity change?"