If you need to delete a specific item by value in a doubly linked list and you must locate it first, what is the expected time complexity?

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

Answer: (C)

When deleting by value in a doubly linked list, you first have to find the node that contains that value. The only way to do that in a plain list is to traverse from the head, checking each node’s value until you find a match or reach the end. This search touches nodes one by one, so the time grows linearly with the number of nodes, n. Once you’ve found the node, removing it is just updating pointers in constant time, but that doesn’t change the overall cost because the search was the dominant part. So the expected time complexity for this operation is O(n). The other options would require faster-than-linear search or additional indexing, which a standard doubly linked list doesn’t provide.