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

Time Complexity: Why Doubly Linked List Over Singly Linked List

O(1)

Understanding Time Complexity

We want to understand how using a doubly linked list changes the time it takes to do common operations compared to a singly linked list.

Which operations become faster or slower, and why?

Scenario Under Consideration

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

// Insert a new node after a given node in doubly linked list
void insertAfter(Node* prev_node, int new_data) {
    if (prev_node == NULL) return;
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = new_data;
    new_node->next = prev_node->next;
    new_node->prev = prev_node;
    if (prev_node->next != NULL) prev_node->next->prev = new_node;
    prev_node->next = new_node;
}

// Delete a given node from doubly linked list
void deleteNode(Node** head_ref, Node* del_node) {
    if (*head_ref == NULL || del_node == NULL) return;
    if (*head_ref == del_node) *head_ref = del_node->next;
    if (del_node->next != NULL) del_node->next->prev = del_node->prev;
    if (del_node->prev != NULL) del_node->prev->next = del_node->next;
    free(del_node);
}
    

This code shows how to insert and delete nodes when you have access to the node itself in a doubly linked list.

Identify Repeating Operations

Look at what repeats or dominates the work done.

• Primary operation: Adjusting pointers (prev and next) for nodes.
• How many times: Each insertion or deletion changes a fixed number of pointers, so constant time per operation.

How Execution Grows With Input

Since insertion and deletion here happen by changing a few pointers, the time does not grow with the list size.

Input Size (n)	Approx. Operations
10	5-6 pointer changes
100	5-6 pointer changes
1000	5-6 pointer changes

Pattern observation: The number of pointer changes stays the same no matter how big the list is.

Final Time Complexity

Time Complexity: O(1)

This means insertion or deletion at a known node happens in constant time, regardless of list size.

Common Mistake

[X] Wrong: "Doubly linked lists always take longer because they have more pointers to update."

[OK] Correct: Actually, having two pointers lets you delete or insert nodes faster when you have direct access, because you don't need to find the previous node by traversing.

Interview Connect

Understanding when doubly linked lists improve operation speed shows you can choose the right data structure for the task, a key skill in coding interviews.

Self-Check

"What if we only had a singly linked list and wanted to delete a node given only that node? How would the time complexity change?"