《算法基础》——3.3　双向链表

本节书摘来自华章计算机《算法基础》一书中的第3章，第3.3节，作者：（美）罗德·斯蒂芬斯（Rod Stephens）著，更多章节内容可以访问云栖社区“华章计算机”公众号查看

3.3　双向链表

在一个双向链表中，单元格具有指向下一个单元格和前一个单元格的链接。指向前一个单元格的链接通常被称为Prev或Previous。
具有首哨兵和尾哨兵的双向链表往往会很方便，因为程序可以很容易地从链表的任意一端进行操作。例如，可以在O(1)时间里从任意一端添加或删除项。
图3-6显示了一个有顶部和底部哨兵的双向链表：

用于操作双向链表的算法和操作单向链表的方法很像，除了在双向链表里需要一些额外的工作去管理链表的第二类链接集合。例如，下面的伪代码展示了在给定单元格之后插入新单元格的算法：

这些算法真正棘手的部分是了解在当前链表中哪些链接已经被更新。例如，在前面的算法中，倒数第二个语句设置Prev链接应该指向新的单元格。也许会使用以下的语句来做到这一点：

不过，在执行这个语句时，after_me.Next已经被更新为指向新的单元格，所以这是行不通的。该算法需要使用new_cell.Next来代替它。
图3-7展示了该过程：