1

假设我有一个带有哨兵的单链表。要在 O(1) 时间内删除最后一个元素，我需要维护最后 2 个元素的句柄。但是维护最后两个元素的句柄会使添加操作复杂化。

有没有办法在 O(1) 中删除带有哨兵的单链表的最后一个元素，而无需维护最后两个元素的句柄？我将非常感谢 java 中的任何示例代码。

谢谢。

4

2 回答 2

3

以正常方式实现的单链表将是一个O(N)操作。

保留最后一个元素的句柄并不复杂，单链表实现通常会这样做，以便您可以在O(1). 但是，面对“删除最后一个”操作，保持到最后一个元素的链接O(1)是不可能的。

想想看。假设我有某个地方可以保存指向最后一个节点和倒数第二个节点的指针。当我删除最后一个节点时，我需要：

  1. next将第二个到最后一个节点中的指针更新为空，
  2. 更新last指针以指向倒数第二个节点。
  3. 更新secondToLast指针以指向它之前的节点。

但是我如何在不从头开始遍历列表的情况下完成最后一步......这是一个O(N)操作？

现在我想你可以对你的链表进行编码，以便删除最后一个元素是O(1) 你第一次这样做，并且O(N)在随后的时间......直到你在最后添加一个新元素。但除非你有一个不寻常的用例，否则这种“优化”是不值得的。

你可能最好使用java.util.LinkedList它使用双向链表，并且有一个removeLast()方法是O(1).`

于 2012-07-08T01:23:58.677 回答
2

不，从末尾删除仅适用于双向链表。您需要反向指针将新的 NULL 终止符放在前一个链接上。我建议将列表进行双重链接以满足您的要求。

你在做自己的容器吗？为什么不使用双向链接的 java.util.LinkedList？

于 2012-07-08T01:23:05.613 回答