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

Time Complexity: Insert at End of Doubly Linked List

O(n)

Understanding Time Complexity

We want to understand how the time needed to add a new item at the end of a doubly linked list changes as the list grows.

Specifically, 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

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

    def insert_at_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        temp = self.head
        while temp.next:
            temp = temp.next
        temp.next = new_node
        new_node.prev = temp

This code adds a new node with given data at the end of a doubly linked list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves through the list to find the last node.
• How many times: It runs once for each node in the list until the end is reached.

How Execution Grows With Input

As the list gets longer, the time to reach the end grows roughly in direct proportion to the number of nodes.

Input Size (n)	Approx. Operations
10	About 10 steps to reach the end
100	About 100 steps to reach the end
1000	About 1000 steps to reach the end

Pattern observation: The steps increase linearly as the list size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert at the end grows linearly with the number of nodes in the list.

Common Mistake

[X] Wrong: "Inserting at the end is always fast and takes constant time."

[OK] Correct: Without a pointer to the last node, we must walk through the whole list, so time grows with list size.

Interview Connect

Understanding this helps you explain how linked lists work and why keeping track of the last node can speed up insertions.

Self-Check

"What if we kept a pointer to the tail (last node) of the list? How would the time complexity change?"