单链表与双链表删除操作的时间复杂度及未知节点位置时的疑问

Great question—let’s break this down clearly, since the time complexity here depends entirely on one key factor: whether you already have a direct reference to the node you want to delete, or if you need to find the node first (because you don’t know its position).

1. When you have a direct reference to the target node #

• 单链表 (Singly Linked List):
  Normally, to delete the node, you have to traverse all the way from the head of the list to find its predecessor (since each node only points to the next one, not the previous). That traversal makes the time complexity O(n).
  There's a clever workaround though: if you only care about removing the value (not the exact node itself), you can copy the value from the node's next into the target node, then delete that next node. This cuts the time to O(1), but it’s a hack—not a true deletion of the original target node.
• 双链表 (Doubly Linked List):
  Every node has both a next and prev pointer, so you can directly update the predecessor’s next to skip the target node, and the successor’s prev to point back to the predecessor. No traversal needed here, so the deletion time is O(1).

2. When you don’t know the node’s position (need to find it first) #

This is the scenario you’re asking about, so let’s clarify your understanding:

• 单链表: You have to loop through the list from the head until you find the node you want to delete. That traversal takes O(n) time, and the deletion step (once you find it) adds either O(n) (if you have to backtrack for the predecessor) or O(1) with the workaround—but the traversal is the dominant cost. Overall, the total time complexity is O(n).
• 双链表: Even though deleting the node itself is O(1) once you have it, you still need to traverse the list to find the target node first. That traversal is O(n), which makes the overall deletion time O(n).

Checking your understanding #

Your reasoning is partially correct, but misses the critical distinction between "having the node reference" and "needing to find the node first":

• You’re right that singly linked lists require an O(n) traversal in the standard deletion scenario when you don’t have the predecessor.
• However, for doubly linked lists, if you don’t know the node’s position, you still have to traverse to locate it—so the overall deletion time is O(n), not O(1). The O(1) only applies when you already have direct access to the node you want to delete.

内容的提问来源于stack exchange，提问作者Loqa