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

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

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

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

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

1    int main(int argc, char *argv[])

2    {

3         dlist_head_t head;

4         dlist_node_t node;

5

6         dlist_init(&head);

7         dlist_add_tail(&head, &node);

8          // ……

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

图3.18  添加结点示意图

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

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

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

● 尾结点的p_next由指向头结点变为指

向新结点；

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

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

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

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

2    {

3         if (p_head == NULL){

4               return -1;

5         }

6         p_node -> p_prev         = p_head->p_prev;  // 新结点的p_prev指向尾结点

7         p_node -> p_next         = p_head;                // 新结点的p_next指向头结点

8         p_head -> p_prev->p_next    = p_node;             // 尾结点的p_next指向新结点

9         p_head -> p_prev         = p_node;                // 头结点的p_prev指向新结点

10        return 0;

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

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

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

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

1    int main(int argc, char *argv[])

2    {

3         dlist_head_t head;

4         dlist_node_t node;

5

6         dlist_init(&head);

7         dlist_add(&head, &(head.p_p