算法(4th ed)(135):基础——背包、队列和栈 5.3.6

阅读数:25 2019 年 11 月 6 日 07:35

算法(4th ed)(135):基础——背包、队列和栈 5.3.6

(链表:其他位置的插入和删除操作)

总的来说,我们已经展示了在链表中如何通过若干指令实现以下操作,其中我们可以通过first 链接访问链表的首结点并通过 last 链接访问链表的尾结点:

  • 在表头插入结点;
  • 从表头删除结点;
  • 在表尾插入结点。

其他操作,例如以下几种,就不那么容易实现了:

  • 删除指定的结点;
  • 在指定结点前插入一个新结点。

例如,我们怎样才能删除链表的尾结点呢?last 链接帮不上忙,因为我们需要将链表尾结点的前一个结点中的链接(它指向的正是 last)值改为 null。在缺少其他信息的情况下,唯一的解决办法就是遍历整条链表并找出指向 last 的结点(请见下文以及练习 1.3.19)。这种解决方案并不是我们想要的,因为它所需的时间和链表的长度成正比。实现任意插入和删除操作的标准解决方案是使用双向链表,其中每个结点都含有两个链接,分别指向不同的方向。我们将实现这些操作的代码留做练习(请见练习 1.3.31)。我们的所有实现都不需要双向链表。

评论

发布