Reverse a Doubly Linked List in DSA C - Time & Space Complexity

Time Complexity: Reverse a Doubly Linked List

O(n)

Understanding Time Complexity

We want to understand how the time needed to reverse a doubly linked list changes as the list gets bigger.

Specifically, how does the work grow when the number of nodes increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void reverseDoublyLinkedList(Node** head) {
    Node* current = *head;
    Node* temp = NULL;
    while (current != NULL) {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
        current = current->prev;
    }
    if (temp != NULL) {
        *head = temp->prev;
    }
}
    

This code reverses the links of a doubly linked list so the last node becomes the first.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that visits each node once.
• How many times: It runs once for every node in the list, so n times if there are n nodes.

How Execution Grows With Input

As the list grows, the number of steps grows directly with the number of nodes.

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

Pattern observation: The work grows in a straight line with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to reverse the list grows directly with the number of nodes.

Common Mistake

[X] Wrong: "Reversing a doubly linked list takes more than linear time because of the two pointers per node."

[OK] Correct: Each node is visited once, and swapping pointers is a constant-time operation, so the total time is still linear.

Interview Connect

Understanding this helps you explain how pointer changes affect performance and shows you can analyze linked list operations clearly.

Self-Check

"What if we tried to reverse the list recursively instead of iteratively? How would the time complexity change?"