双向链表，是一种常用的数据结构。在 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_H
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* 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 <stdlib.h>
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 <stdio.h>#include <stdint.h>
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, 输出结果如下：
我的微信号 "实力程序员"，欢迎大家关注我。
评论