周立功阐释高效的双向链表如何用

7         dlist_add(&head, &(head.p_prev),  &node);

8         // ……

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

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

1    int dlist_add_tail (dlist_head_t *p_head, dlist_node_t *p_node)

2    {

3         return dlist_add(p_head, p_head->p_prev, p_node);

为了实现dlist_add()函数，可以先查看添加一个结点到任意结点之后的情况，详见图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()函数实现

1    int dlist_add (dlist_head_t *p_head, dlist_node_t *p_pos, dlist_node_t *p_node)

2    {

3         if ((p_head == NULL) || (p_pos == NULL) || (p_node == NULL)){

4             return -1;

5         }

6         p_node->p_prev        = p_pos;                // 新结点的p_prev指向前结点

7         p_node->p_next        = p_pos->p_next;        // 新结点的p_next指向后结点

8         p_pos->p_next->p_prev = p_node;                    // 后结点的p_prev指向新结点

9         p_pos->p_next         = p_node;              // 前结点的p_next指向新结点

10        return 0;

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

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

int dlist_add_head (dlist_head_t *p_head, dlist_node_t *p_node);

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

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

1    int dlist_add_head (dlist_head_t *p_head, dlist_node_t *p_node)

2    {

3         return dlist_add(p_head, p_head, p_node);