我不太明白为什么像维基百科文章所说的那样，在单个链表的末尾删除需要O(1)个时间。
单个链表由节点组成。节点包含某种类型的数据，以及对下一个节点的引用。链接表中最后一个节点的引用为null
-------------- -------------- --------------
| data | ref | -> | data | ref | -> ... -> | data | ref |
-------------- -------------- --------------
我可以移除O(1)中的最后一个节点。但是在这种情况下，您不会将新的最后一个节点(即前一个节点)的引用设置为null，因为它仍然包含对删除的最后一个节点的引用。所以我想知道，他们在运行时间分析中是否忽略了这一点?或者它认为你不需要改变它，因为引用，嗯，只是指向什么，这样被视为空?
因为如果它不被忽略，我会认为删除是O(n)。因为您必须遍历整个列表以获得新的最后一个节点，并将其引用也设置为null。只有在双链表中才会是O(1)
编辑-也许这个观点能让我们更清楚一些。但是我看到了"删除一个节点"成功地删除节点本身，并将前面的引用设置为null。
我不确定我在Wikipedia文章中看到它说可以在O(1)时间内删除单链表的最后一个条目，但该信息在大多数情况下是不正确的。给定链表中的任何单个节点，总是可以在O(1)时间内通过围绕该新节点重新连接列表来删除它之后的节点。因此，如果给你一个指向链表倒数第二个节点的指针，那么你可以在O(1)时间内删除链表的最后一个元素。
然而，如果你没有任何额外的指针进入列表，除了一个头指针，那么你不能删除列表的最后一个元素，而不扫描到列表的末尾，这将需要Θ(n)时间，正如你所注意到的。你是完全正确的，只是删除最后一个节点，而不首先改变指向它的指针，这将是一个非常糟糕的主意，因为如果你这样做，现有的列表将包含一个指向已释放对象的指针。
更一般地说，在单链表中插入或删除的代价是O(1)，假设你有一个指向你想要插入或删除的节点的指针。然而，你可能需要做额外的工作(直到Θ(n))来找到那个节点。
希望这对你有帮助!
在ANY位置的ANY节点的添加/删除为0(1)。代码只是使用固定成本(少量指针计算和malloc/free)来添加/删除节点。此算术代价对于任何特定情况都是固定的。
然而，到达(索引)所需节点的代价是O(n)。
文章只是列出了多个子类别的添加/删除(添加在中间，开始，结束)，以表明添加在中间的成本不同于添加在开始/结束的成本(但各自的成本仍然是固定的)。
如果考虑固定悬空节点的成本，仍然可以在0(1)内完成，并使用哨兵节点作为结束(该页也有描述)。
你的"空"列表从一个哨兵开始
Head -> [Sentinel]
添加一些东西
Head -> 1 -> 2 -> 3 -> [Sentinel]
现在通过将节点3标记为无效来删除尾部(3)，然后删除到旧哨兵的链接，并为其释放内存:
Head -> 1 -> 2 -> 3 -> [Sentinel]
Head -> 1 -> 2 -> [Sentinel] -> [Sentinel]
Head -> 1 -> 2 -> [Sentinel]
0(1)简单地表示"不变成本"。这并不意味着一次操作。这意味着无论其他参数(如列表大小)如何变化，"最多C"操作都是固定的。事实上，在这个有时令人困惑的大世界里，哦:0(1)== 0(22)。
相比之下，删除整个链表的代价是O(n)，因为代价随着链表的大小(n)而变化。
为了将来的参考，我必须说，经过一些研究，我发现针对这个问题提供的论据没有一个是相关的。答案是，我们简单地决定将堆栈的顶部作为链表的头部(而不是尾部)。这将在push例程中引入一个细微的变化，但是弹出和推送都将保持0(1)。
如果在单个链表中给出了要删除的节点的指针，那么只需将下一个节点复制到要删除的节点上，就可以在常量时间内删除该节点。
M pointer to node to delete
M.data=M.next.data
M.next=M.next.next
否则，如果你需要搜索节点，那么你不能比O(n)更好
是的，即使您不维护指向"前一个元素"的指针，您也可以在O(1)时间内完成此操作。
假设你有这样一个列表，其中"头"one_answers"尾"是静态指针，"尾"是一个标记为结束的节点。您可以正常使用"next == NULL"，但在这种情况下，您必须忽略值:
head -> 1 -> 2 -> 3 -> 4 -> 5 -> End <- tail
现在，你得到了一个指向节点3的指针，但不是它的前一个节点。你也有头和尾指针。下面是一些类似python的代码，假设有一个SingleLinkedList类。
class SingleLinkedList:
# ... other methods
def del_node(self, node): # We "trust" that we're only ever given nodes that are in this list.
if node is self.head:
# Simple case of deleting the start
self.head = node.next
# Free up 'node', which is automatic in python
elif node.next is self.tail
# Simple case of deleting the end. This node becomes the sentinel
node.value = None
node.next = None
# Free up 'self.tail'
self.tail = node
else:
# Other cases, we move the head's value here, and then act
# as if we're deleting the head.
node.value = self.head.value
self.head = self.head.next
new_head = self.head.next
# Free up 'self.head'
self.head = new_head
唉，这会重新排序列表，和移动值，这可能适合您的应用程序，也可能不适合。
例如，你可以有一个指针指向最后一个元素之前("second from end")和删除时:1. 删除"second from end"元素的*next。2. 将second from end设置为NULL