Question

The worst-case time complexity of inserting a node in a doubly linked list is:

• A. O(n log n)
• B. O(log n)
• C. O(n)
• D. O(1)

Hint:

Doubly linked lists allow constant-time insertion when the node reference is provided, unlike arrays that require shifting.

Answer 1

The Correct Option is D

In a doubly linked list, insertion at a known position is an O(1) operation, as it directly updates the previous and next node pointers. While locating the insertion point may necessitate traversal if not directly known, the insertion operation itself consistently maintains an O(1) time complexity.