In a doubly linked list, what is the time complexity of deleteNode when you must search for the item to delete?

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

Answer: (B)

The key idea is that the costly part is finding the node to delete. In a doubly linked list, once you have the node, removing it is just updating a couple of pointers, which is done in constant time. But to delete you must locate the target, and you may need to visit every node as you traverse from the head (or tail) to find a match. That search can take linear time in the number of nodes, n. So the overall time complexity of deleting a node when you must search for it is O(n). Note that even though removing once found is O(1), you can’t avoid the initial scan, and on average you may scan about half the list, but it still scales linearly with n.