Why Doubly Linked List Over Singly Linked List in DSA Python - Performance Analysis

Time Complexity: Why Doubly Linked List Over Singly Linked List

O(n) insertion, O(1) deletion

Understanding Time Complexity

We want to understand how operations like insertion, deletion, and traversal behave in doubly linked lists compared to singly linked lists.

Which list type performs faster for different tasks and why?

Scenario Under Consideration

Analyze the time complexity of inserting and deleting nodes in a doubly linked list.

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
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def delete_node(self, node):
        if not self.head or not node:
            return
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
        if node.next:
            node.next.prev = node.prev
    

This code inserts a node at the end and deletes a given node in a doubly linked list.

Identify Repeating Operations

Look at the loops and pointer updates that repeat.

• Primary operation: Traversing the list to find the last node for insertion.
• How many times: The while loop runs once per node until the end, so up to n times for n nodes.
• Deletion: No loop needed if node is known; just pointer updates.

How Execution Grows With Input

Traversal to the end grows linearly with the number of nodes.

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

Pattern observation: The time to insert at end grows directly with list size.

Final Time Complexity

Time Complexity: O(n) for insertion at end, O(1) for deletion if node is known.

This means insertion at the end takes longer as the list grows, but deleting a known node is quick because we can access neighbors directly.

Common Mistake

[X] Wrong: "Doubly linked lists always take twice as long because they have two pointers."

[OK] Correct: Actually, doubly linked lists let us delete nodes faster without traversal, saving time in many cases despite extra pointers.

Interview Connect

Understanding when to use doubly linked lists shows you know how to balance speed and memory in real problems.

Self-Check

"What if we kept a tail pointer in the doubly linked list? How would that change the insertion time complexity?"