本文共 4001 字，大约阅读时间需要 13 分钟。

双向链表，是一种常用的数据结构。在C语言中，双向链表的实现，通常采用下面的数据结构：

typedef struct dlist_node_t {    struct dlist_node_t* pprev;    struct dlist_node_t* pnext;    void* pdata;} dlist_node_t;typedef struct dlist_t {    dlist_node_t* phead;    dlist_node_t* ptail;} dlist_t;

dlist_t 是双向链表的数据结构，其有两个指针：一个指向头部节点，一个执行尾部节点。

每个节点，用dlist_node_t来表示，节点内部有三个成员：指向前一个节点的指针，指向下一个节点的指针，节点保存的数据指针。

向链表增加或删除节点时，都需要对指针是否为NULL进行判断，包括：判断dlist_t的头指针、尾指针是否为NULL，判断dlist_node_t的前向、后向指针是否为NULL，从而进行对应的处理，这样排列组合起来的场景是比较多的，因此代码实现逻辑比较繁琐。

 

为了避免判断NULL，简化代码，一些新的实现思路被提出。

有人提议，把dlist_t的头尾指针，都改成dlist_node_t结构体，形成2个固定的哨兵，如下：

typedef struct dlist_t {    dlist_node_t head;    dlist_node_t tail;} dlist_t;

这样dlist_t就没有NULL指针了，并且链表中的节点，前向和后向指针都一定不是NULL。这样代码实现就大大简化了。

这样的设计，只有head的前向指针、tail的后向指针为NULL，并且由于他们是哨兵，这两个NULL指针不需要修改，也不需要判断。

 

这种改进方案，唯一的不足，是dlist_t 数据结构占用的内存变大了，多消耗了4个指针的内存空间，即32个byte。

对于追求完美的开发者而言，这不应该是终极方案！

 

我找到一种双向链表的实现方式，不需要增加任何额外的空间，并且能彻底消除对NULL的判断。其核心设计思路为：

把 dlist_t 也看作是一个dlist_node_t，和链表内的dlist_node_t一起构成一个首尾相接的环形结构，从而消除NULL指针。

具体如下图所示：

代码核心实现要点，如下：

1）数据结构dlist_t中的phead和ptail的位置需要对调。

2）dlist_t 初始化时，前向和后向指针都指向自己。

3）向dlist_t中增加、删除成员时，把双向链表看作是一个环状的双向链表，这个环上，每个节点的前向和后向指针都不是NULL，都可以访问和修改。

代码示例如下： dlist.h 的内容如下：

// dlist.h#ifndef DLIST_H#define DLIST_Htypedef struct dlist_node_t {    struct dlist_node_t* pprev;    struct dlist_node_t* pnext;    void* pdata;} dlist_node_t;typedef struct dlist_t {    dlist_node_t* ptail;    dlist_node_t* phead;} dlist_t;int dlist_init(dlist_t* plist);int dlist_push_tail(dlist_t* plist, void* pdata);int dlist_push_head(dlist_t* plist, void* pdata);void* dlist_pop_tail(dlist_t* plist);void* dlist_pop_head(dlist_t* plist);// ...#endif

dlist.c 的内容如下：

// dlist.c#include "dlist.h"#include 
   
    int dlist_init(dlist_t* plist) {    plist->phead = (dlist_node_t*)plist;    plist->ptail = (dlist_node_t*)plist;    return 0;}int dlist_push_tail(dlist_t* plist, void* pdata) {    // new node    dlist_node_t* pnode = (dlist_node_t*)malloc(sizeof(*pnode));    pnode->pdata = pdata;    // tail node    dlist_node_t* ptail = plist->ptail;    // ring : insert as next node of the tail node    pnode->pnext = ptail->pnext;    ptail->pnext->pprev = pnode;    pnode->pprev = ptail;    ptail->pnext = pnode;    return 0;}int dlist_push_head(dlist_t* plist, void* pdata) {    // new node    dlist_node_t* pnode = (dlist_node_t*)malloc(sizeof(*pnode));    pnode->pdata = pdata;    // head node    dlist_node_t* phead = plist->phead;    // ring : insert as prev node of the head node    pnode->pprev = phead->pprev;    phead->pprev->pnext = pnode;    pnode->pnext = phead;    phead->pprev = pnode;    return 0;}void* dlist_pop_tail(dlist_t* plist) {    if (plist->ptail == (dlist_node_t*)plist) {     // empty            return NULL;    }    // remove tail node from dlist    dlist_node_t* pnode = plist->ptail;    pnode->pprev->pnext = pnode->pnext;    pnode->pnext->pprev = pnode->pprev;    // free node    void* pdata = pnode->pdata;    free(pnode);    return pdata;}void* dlist_pop_head(dlist_t* plist) {    if (plist->phead == (dlist_node_t*)plist) {     // empty            return NULL;    }    // remove head node from dlist    dlist_node_t* pnode = plist->phead;    pnode->pprev->pnext = pnode->pnext;    pnode->pnext->pprev = pnode->pprev;    // free node    void* pdata = pnode->pdata;    free(pnode);    return pdata;}
   

测试程序 test_dlist.c 的内容如下：

#include "dlist.h"#include 
   
    #include 
    
     int main() {    dlist_t list, *plist = &list;    int iret = dlist_init(plist);    dlist_push_tail(plist, (void*)1);    dlist_push_tail(plist, (void*)2);    dlist_push_tail(plist, (void*)3);    dlist_push_head(plist, (void*)4);    dlist_push_head(plist, (void*)5);    printf("%lu\n", (uint64_t)dlist_pop_head(plist));    printf("%lu\n", (uint64_t)dlist_pop_head(plist));    printf("%lu\n", (uint64_t)dlist_pop_head(plist));    printf("%lu\n", (uint64_t)dlist_pop_head(plist));    printf("%lu\n", (uint64_t)dlist_pop_head(plist));    return 0;}
    
   

运行 ./test_dlist, 输出结果如下：

$ ./test_dlist54123

 

我的微信号 "实力程序员"，欢迎大家关注我。

转载地址：http://ztlsi.baihongyu.com/