1

这是在谈论使用链接列表实现字典时来自算法设计手册。

在此处输入图像描述

一方面，部分内容是“在插入时检查是否last->next仍然等于 NULL”。为什么我们必须检查它？如果我要插入一个元素，这将如何影响最后一项是否正确指向 NULL？如果我们正在正确地执行我们的实现，不是吗？我们不能说类似的话：

last->next = nodeToInsert;
last = last->next;

为什么那行不通？

其次，倒数第二段是否在讨论我们删除单链表中的最后一项并且必须识别新的最后一项的情况？并且我们只是（具有 O(n) 复杂性）遍历到倒数第二个项目并将其设置为最后一个并删除前一个？我们将它与预先存在的删除方法混合在一起，只是添加一个案例来判断它是否是最后一项？

4

3 回答 3

3

为什么我们要检查呢？

因为大概你并不总是在列表的末尾插入，所以last并不总是需要更新。

第二， ...

是的。

于 2013-01-13T19:05:59.433 回答
1

请注意，本节讨论的是作为排序列表实现的字典。

这意味着插入需要恰好在正确的点发生。您建议的代码添加到列表的末尾：

last->next = nodeToInsert;
last = last->next;

这对于未排序的列表是正确的，但对于已排序的列表则不正确。

另请注意，作者使用 last 作为普通链表的附加指针。

我认为您认为 last 是双向链表结构的一部分。如果是这样，那么您应该在插入期间对其进行更新是正确的。但是，由于它是一个独立的指针，需要文中描述的附加代码使其与链表保持一致。

于 2013-01-13T20:14:19.267 回答
0 
if(last->next != NULL) {   // insertion occurred at the tail end
    last = nodeToInsert;   // so update tail pointer to point to inserted node
}

尾端插入已经设置last->next。不再NULL是因为插入。这就是告诉我们last需要更新的内容（last实际上是现在lastButOne）。如果last->next仍然NULL如此，那么我们不需要做任何事情，因为插入发生在之前的某个地方last。你的书的措辞也许有点误导。现在这有意义吗？

于 2013-01-13T20:04:10.387 回答