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

时，尾结点的下一个结点就是链表头结点（head），因此结束位置就是头结点本身。dlist_end_get()的实现详见程序清单3.37。

程序清单3.37  dlist_end_get()函数实现

3.3.1 添加结点

假定还是将结点添加到链表尾部，其函数原型为：

其中，p_head为指向链表头结点的指针，p_node为指向待添加结点的指针，其使用范例详见程序清单3.38。

程序清单3.38  dlist_add_tail()函数使用范例

为了实现该函数，可以先查看添加结点前后链表的变化，详见图3.18。

图3.18  添加结点示意图

由此可见，添加一个结点至链表尾部，需要4个指针（图中虚线箭头）：

• 新结点的p_prev指向尾结点；

• 新结点的p_next指向头结点；

• 尾结点的p_next由指向头结点变为指向新结点；

• 头结点的p_prev由指向尾结点修改为指向新结点。

通过这些操作后，当结点添加到链表尾部后，就成为了新的尾结点，详见程序清单3.39。

程序清单3.39  dlist_add_tail()函数实现

实际上循环链表，无论是头结点、尾结点还是普通结点，其本质上都是一样的，均为p_next成员指向下一个结点，p_prev成员指向其上一个结点。因此，对于添加结点而言，无论将结点添加到链表头、链表尾还是其它任意位置，其操作方法完全相同。为此，需要提供一个更加通用的函数，可以将结点添加到任意结点之后，其函数原型为：

其中，p_head为指向链表头结点的指针，p_pos指定了添加的位置，新结点即添加在该指针指向的结点之后；p_node为指向待添加结点的指针。比如，同样将结点添加到链表尾部，其使用范例详见程序清单3.40。

程序清单3.40  dlist_add()函数使用范例

由此可见，将尾结点作为结点添加的位置，同样可以将结点添加至尾结点之后，即添加到链表尾部。显然，也就没有必要再编写dlist_add_tail()实现代码了，使用dlisd_add()即可，修改dlist_add_tail()函数的实现，详见程序清单3.41。

程序清单3.41  dlist_add_tail()函数实现

为了实现dlist_add()函数，可以先查看添加一个结点到任意结点之后的情况，详见图3.19。图中展示的是一种通用的情况，由于结点的添加位置（头、尾或其它任意位置）与添加结点的方法没有关系，因此没有特别标明头结点和尾结点。

图3.19  添加结点示意图

其实，对比图3.18和图3.19可以发现，图3.18展示的只是图3.19的一个特例，即恰好图3.19中的新结点之前的结点就是尾结点，添加结点的过程同样需要修改4个指针的值。为便于描述，将新结点前的结点称之为前结点，新结点之后的结点称之为后结点。显然，在添加新结点之前，前结点的下一个结点即为后结点。对设置4个指针值的描述如下：

• 新结点的p_prev指向前结点；

• 新结点的p_next指向后结点；

• 前结点的p_next由指向后结点变为指向新结点；

• 后结点的p_prev由指向前结点修改为指向新结点。

对比将结点添加到链表尾部的描述，只要将描述中的"前结点"换为"尾结点"，"后结点"换为"头结点"，它们的含义则完全一样，显然将结点添加到链表尾部只是这里的一个特例，添加结点的函数实现详见程序清单3.42。

程序清单3.42  dlist_add()函数实现

尽管上面的函数在实现时并没有用到参数p_head，但还是将p_head参数传进来了，因为实现其它的功能时将会用到p_head参数，比如，判断p_pos是否在链表中。

有了该函数，添加结点到任意位置就非常灵活了，比如，提供一个添加结点到链表的头部，使其作为链表的第一个结点的函数，其函数原型为：

此时，头结点即为新添加结点的前结点，直接调用dlist_add()即可实现，其实现范例详见程序清单3.43。

程序清单3.43  dlist_add_head()函数实现

3.3.2  删除结点

基于添加结点到任意位置的思想，需要实现一个删除任意结点的函数。其函数原型为：

其中，p_head为指向链表头结点的指针， p_node为指向待删除结点的指针，使用范例详见程序清单3.44。

程序清单3.44  dlist_del()使用范例程序

为了实现dlisd_del()函数，可以先查看删除任意结点的示意图，图 3.20（1）为删除节点前的示意图，图 3.20（2）为删除节点后的示意图。

图 3.20添加结点示意图

由此可见，仅需要修改两个指针的值：

• 将"删除结点"的前结点的p_next修改为指向"删除结点"的后结点；

• 将"删除结点"的后结点的p_prev修改为指向"删除结点"的前结点。