算法与数据结构——双向链表

周立功教授数年之心血之作《程序设计与数据结构》以及《面向AMetal框架与接口的编程（上）》，书本内容公开后，在电子行业掀起一片学习热潮。经周立功教授授权，本公众号特对《程序设计与数据结构》一书内容进行连载，愿共勉之。

第三章为算法与数据结构，本文为3.3 双向链表。

>>> 3.3  双向链表

单向链表的添加、删除操作，都必须找到当前结点的上一个结点，以便修改上一个结点的p_next指针完成相应的操作。由于单向链表的结点没有指向其上一个结点的指针，因此只有从头结点开始遍历链表。当某一结点的p_next指向当前结点时，表明它为当前结点的上一个结点。显然每次都要从头开始遍历，其效率极为低下。在单向链表中，之所以可以直接获取单向链表中当前结点的下一个结点，是因为结点中包含了指向下一个结点的指针p_next。如果在双向链表的结点中再增加一个指向它的前一个结点的前向指针p_prev，则一切问题将迎刃而解。那么，既有指向下一个结点的指针，又有指向前一个结点的指针的链表称之为双向链表，示意图详见图3.15。

图3.15  双向链表示意图

与单向链表一样，双向链表也定义了一个头结点，基于单向链表将应用数据与链表结构相关数据完全分离的设计思想，则双向链表结点仅保留p_next和p_prev指针。其数据结构定义如下：

其中，dlist是double list 的缩写，表明该结点是双向链表结点。由此可见，虽然前向指针使得寻找链表的上一个结点变得非常容易，但由于结点中新增了一个指针，因此其内存开销将会是单向链表的两倍。在实际应用中，应该权衡效率与内存空间，在内存资源非常紧缺的场合，如果结点的添加、删除操作很少，一点效率的影响可以接受，则选择使用单向链表。而不是一味地追求效率，认为双向链表比单向链表好，始终选择使用双向链表。

在图3.15中，头结点的p_prev和尾结点的p_next直接被设置为了NULL，此时，如果要直接由头结点找到尾结点，或者由尾结点找到头结点，都必须遍历整个链表。可以对这两个指针稍加利用，使头结点的p_prev指向尾结点，尾结点的p_next指向头结点，此时，该双向链表就成了一个循环双向链表，示意图详见图3.16。

图3.16  循环双向链表示意图

由于循环双向链表的效率更高，可以直接从头结点找到尾结点，或者从尾结点找到头结点，且没有额外的内存空间消耗，仅仅是使用了两个不打算使用的指针，算是废物利用，因此下面介绍的双向链表均视为循环双向链表。

类似于单向链表，虽然头结点与普通结点的内容完全相同，但它们的含义却有所区别，头结点是链表的头，代表了整个链表，拥有此头结点，就表示其拥有了整个链表。为了便于区分头结点与普通结点，可以单独定义一个头结点类型。比如：

当需要使用双向链表时，首先需要使用该类型定义一个头结点。比如： 

由于此时还没有添加其它任何结点，仅存在一个头结点，因此该头结点既是第一个结点（头结点），又是最后一个结点（尾结点）。按照循环链表的定义，尾结点的p_next指向头结点，头结点的p_prev指向尾结点，仅有一个结点的示意图详见图3.17。

图3.17  空链表

显然，仅有头结点时，其p_next和p_prev都指向本身。即：

为了避免用户直接操作成员，需要定义一个初始化函数，专门用于初始化链表头结点中各个成员的值，其函数原型（dlist.h）为：

其中，p_head指向待初始化的链表头结点。其调用形式如下：

dlist_init()函数的实现详见程序清单3.33。

程序清单3.33  双向链表初始化函数

与单向链表类似，将提供一些基础的操作接口，它们的函数原型如下：

对于dlist_prev_get()和dlist_next_get()，在链表结点中已经存在指向前驱后后继的指针，详见程序清单3.34。

程序清单3.34  得到结点前驱和后继的函数实现

dlist_tail_get()函数用于得到链表的尾结点，在循环双向链表中，头结点的p_reev即指向了尾结点，详见程序清单3.35。

程序清单3.35  dlist_tail_get()函数实现

dlist_begin_get()函数用于得到第一个用户结点，详见程序清单3.36。

程序清单3.36  dlist_begin_get()函数实现

dlist_end_get()用于得到链表的结束位置，当双向链表设计为循环双向链表时，则头结点的p_prev和尾结点的p_next都被有效地利用了，任何有效结点的p_next和p_prev都不再为NULL。显然，不能再以NULL作为结束位置了，当从第一个结点开始顺序访问链表的各个结点