单链表删除为什么是 O(1)？

在本教程中，我们将讨论单链表的删除操作。

单链表中的节点如何被删除？

要从链表中删除一个节点，我们必须首先断开连接该节点与其前驱节点的链接。假设节点 P 必须被删除，而节点 Q 是指向 P 的节点。因此，我们需要移除 P 和 Q 之间的链接，然后 Q 将指向 P 原来指向的节点。

链表节点删除的不同类型

删除操作分为三种类型：

• 从链表头部删除
• 从链表尾部删除
• 在头部和尾部之间删除。

所有情况并非都需要 O(1) 时间。下面一节列出了各种操作的时间复杂度。

不同删除操作的时间复杂度

从头部删除

• 将头指针指向下一个节点。
• 时间复杂度为 **O(1)。**

从尾部删除

• 遍历到倒数第二个元素。
• 将下一个指针设置为 NULL。
• 时间复杂度将为 O(N)。

删除链表中间的某个节点

• 找到要删除元素的前一个元素。
• 修改前一个元素的 next 指针，将其指向要删除节点的下一个节点，从而将节点从列表中移除。
• 时间复杂度将为 O(N)。

什么时候单链表的删除需要 O(1) 时间？

因为我们不需要遍历链表，所以在三种情况下，单链表的删除是 O(1) 的。

首先，让我们将指向需要删除的节点的指针称为“previous”。那么我们需要做的是：

• current = previous->next
• previous->next = current->next
• current->next = NULL
• delete current

因为 current 是从单链表中删除的节点。

第二种情况：当需要删除第一个/起始/头节点时，我们称之为 head。那么我们需要做的是：

• head = head->next

因此，head 指向下一个节点。

第三种情况：当我们 AoNi 需要删除最后一个/末尾/尾节点时，我们称之为 tail。因此，我们必须相应地采取行动。

• tail = NULL

这只有在我们保留一个额外的指针（即 tail）来指向链表末尾节点时才可能。同时，我们只能执行一次，因为我们最终会丢失对最后一个节点的引用，并且在单链表中没有 O(1) 的方法来找到指向新最后一个节点的引用。因为双向链表包含前一个指针，所以它在这种情况下是允许的。

以下是单链表中各种删除过程的实现：

C++ 程序

输出

Original list: 15 25 35 45 
List after eliminating the first node: 25 35 45 
List after eliminating the last node: 25 35 
List after eliminating the specified node: 25