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 O(1) because the pointers to the previous and next nodes are updated directly. - The only traversal required is to locate the insertion point if not directly known, but in the worst case, for an insertion operation itself, the complexity is O(1).