数据结构里最容易被低估的，就是双向链表。单链表写起来顺手，但一到"删除当前节点"或者"从后往前遍历"这种场景，就得从头再扫一遍，时间复杂度直接退化。双向链表多存一个前驱指针，换来的是 O(1) 的删除和双向游走能力，这笔账在很多场景下非常划算。我最早系统性地啃双向链表，是在翻《Mastering Algorithms with C》这本书的时候，书里用dlist这个模块把双向链表的增删改查、遍历、销毁封装成了一套可复用的接口。这套接口设计得很克制，没有花哨的东西，但每一处细节都值得琢磨——比如dlist_remove为什么要传一个data出参、dlist_destroy为什么要单独接收一个释放函数。这些设计背后都是实打实的工程考量。
这篇内容我想把dlist这个模块从里到外拆一遍。不是照本宣科地翻译书上的代码，而是站在"我要在自己的项目里用起来"的角度，讲清楚它的数据结构长什么样、每个接口为什么这么设计、插入删除时指针到底怎么改、边界情况怎么处理，以及我在实际使用中踩过的坑。适合已经会写单链表、想进一步掌握双向链表工程实现的读者，也适合手头正好有一份dlist源码、想搞明白每一行在干什么的人。读完你应该能自己从零写出一个稳定的双向链表模块，并且知道哪些地方最容易出 bug。
1. dlist 的骨架：两个结构体撑起整个模块
dlist这个模块的代码量不大，核心就是两个结构体：一个描述"节点"，一个描述"链表本身"。很多人写链表喜欢只定义一个节点结构体，然后用一个指向头节点的指针代表整个链表。这种写法在单链表里勉强能用，但在双向链表里会很难受，因为你需要频繁地区分"空链表"和"只有一个节点的链表"，还要在头尾操作时做特殊判断。dlist把链表本身也抽象成一个结构体，这个决定直接决定了后面所有接口的写法。
1.1 节点结构体：data 与前后指针的三元组
节点结构体DListElmt的定义大致是这样的：
typedef struct DListElmt_ { void *data; struct DListElmt_ *prev; struct DListElmt_ *next; } DListElmt;三个字段，data存数据，prev指向前驱，next指向后继。这里第一个值得说的点是data用了void *。这意味着链表本身不关心你存的是什么——整数、字符串、结构体指针都行，链表只负责把这些指针串起来。这种"数据与结构分离"的做法是 C 语言里实现通用容器的标准套路，好处是同一个dlist可以复用到任何数据类型上，代价是使用者要自己管理data指向的内存的生死。
第二个值得说的是prev和next的类型都是struct DListElmt_ *，而不是void *。这一点很关键。如果用void *，每次访问前后节点都要强制转换，代码会变得很脏，而且编译器帮不上忙。用具体的结构体指针类型，编译器能做类型检查，你写node->next->data这种链式访问时也不会报错。这是 C 语言里"自引用结构体"的典型用法，定义的时候结构体还没定义完，所以必须用struct DListElmt_这种带标签的写法。
提示：
data用void *而指针字段用具体类型，这个组合不是随意的。数据要通用所以用void *，结构关系要类型安全所以用具体指针。理解这个区分，你就理解了 C 通用容器的基本设计哲学。
1.2 链表结构体：size、head、tail 与 destroy
链表结构体DList的定义：
typedef struct DList_ { int size; int (*destroy)(void *data); DListElmt *head; DListElmt *tail; } DList;四个字段各司其职。size记录当前节点数量，这样取链表长度就是 O(1)，不用每次遍历去数。head和tail分别指向头节点和尾节点，这是双向链表相比单链表的一大优势——有了tail，在尾部插入就是 O(1)，不用从头遍历到尾。destroy是一个函数指针，指向一个用户提供的释放函数，链表在销毁节点或者删除节点时会调用它来释放data指向的内存。
为什么destroy要放在链表结构体里，而不是每次调用删除接口时传进去？这是个很实际的设计问题。如果每次删除都传destroy，接口会变得冗长，而且容易忘记传或者传错。把它固化在链表结构体里，相当于在创建链表时就"约定"好了这个链表的数据该怎么释放，后续所有操作都自动遵守这个约定。这个思路在 C 的容器库里很常见，本质上是把"策略"和"结构"绑定在一起。
size用int而不是size_t，这一点书里没多解释，但我个人觉得是个小瑕疵。size_t是无符号的，语义上更贴合"数量"这个概念，而且能表示更大的范围。不过用int在实际项目里问题不大，除非你的链表节点数真的会超过二十亿。这里提一句，是让你知道这个选择的存在，自己写的时候可以斟酌。
1.3 宏定义：把"取长度"和"判空"变成零成本操作
dlist模块还提供了几个宏：
#define dlist_size(list) ((list)->size) #define dlist_head(list) ((list)->head) #define dlist_tail(list) ((list)->tail) #define dlist_is_head(node) ((node)->prev == NULL ? 1 : 0) #define dlist_is_tail(node) ((node)->next == NULL ? 1 : 0) #define dlist_data(node) ((node)->data) #define dlist_next(node) ((node)->next) #define dlist_prev(node) ((node)->prev)这些宏看起来琐碎，但作用不小。用宏而不是函数，是因为这些操作都是"取一个字段"或者"做一次比较"，函数调用的开销（压栈、跳转、返回）反而比操作本身还大。宏在预处理阶段就展开成内联代码，零开销。dlist_is_head和dlist_is_tail通过判断prev或next是否为NULL来识别头尾，这个判断依赖一个约定：头节点的prev是NULL，尾节点的next是NULL。这个约定贯穿整个模块，后面所有插入删除逻辑都要维护它。
注意：宏参数一定要用括号包起来，比如
((list)->size)而不是(list->size)。因为宏是文本替换，如果调用时传的是dlist_size(a + b)，没有外层括号就会展开成a + b->size，直接编译错误或者算出错误结果。这是 C 宏的经典坑，dlist的宏定义在这一点上做得很规范。
2. 初始化与销毁：内存管理的起点和终点
链表的生命周期从dlist_init开始，到dlist_destroy结束。这两个函数看起来简单，但里面藏着几个容易忽略的细节，尤其是销毁时的遍历顺序和destroy回调的调用时机。
2.1 dlist_init：四行代码里的初始化顺序
dlist_init的实现：
void dlist_init(DList *list, void (*destroy)(void *data)) { list->size = 0; list->destroy = destroy; list->head = NULL; list->tail = NULL; }四行代码，把四个字段都初始化了。size置 0，destroy存下用户传进来的释放函数（可以是NULL，表示不需要释放数据），head和tail都置NULL表示空链表。这里没什么玄机，但有一个使用上的约定：调用dlist_init之前，list指向的内存必须已经分配好。dlist_init不负责分配DList结构体本身，它只初始化字段。这意味着你可以把DList放在栈上、堆上、或者作为另一个结构体的成员，灵活性很高。
destroy传NULL是合法的，表示链表不负责释放data。什么场景下会这样用？比如你的data指向的是栈上的变量，或者指向的是别处已经管理好的内存，链表只是临时把它们串起来用一下。这种情况下传NULL，销毁链表时就只释放节点本身，不碰data。这个设计给了使用者选择权，很务实。
2.2 dlist_destroy：为什么必须先存 next 再释放当前节点
dlist_destroy的实现：
void dlist_destroy(DList *list) { void *data; while (dlist_size(list) > 0) { if (dlist_remove(list, dlist_tail(list), (void **)&data) == 0 && list->destroy != NULL) { list->destroy(data); } } memset(list, 0, sizeof(DList)); }这个函数从尾部开始，一个一个地删除节点，直到链表为空。每删除一个节点，如果destroy不为NULL，就调用它释放data。最后用memset把整个DList结构体清零，防止残留的野指针被误用。
这里最值得讲的是"从尾部删"这个选择。你可能会想，从头删不是一样吗？从结果上看确实一样，但从实现细节上看，dlist_remove在删除尾节点时不需要更新后继节点的prev（因为尾节点没有后继），逻辑稍微简单一点。不过这不是关键，关键是这个循环的写法——它没有直接操作head和next指针去遍历，而是反复调用dlist_remove。这样做的好处是把"删除节点"的逻辑完全交给dlist_remove处理，dlist_destroy不用重复实现一遍指针操作，减少了出错的可能。代价是每次删除都要走一遍dlist_remove的完整逻辑，效率略低，但销毁操作本来就不频繁，这点开销可以接受。
提示：
memset(list, 0, sizeof(DList))这一步很多人会省略，觉得链表都空了还清什么。但清零是有意义的——它把head、tail置NULL，size置 0，destroy置NULL。如果之后有人误用了这个已经销毁的链表，至少size是 0，遍历不会进入循环，不会立刻崩溃。这是一种防御性编程，成本极低，收益是排查问题时少一类诡异 bug。
2.3 destroy 回调的调用时机：删除节点和销毁链表都要管
destroy回调在两个地方被调用：dlist_remove删除单个节点时，以及dlist_destroy销毁整个链表时。这两个地方都要记得调用，漏掉任何一个都会造成内存泄漏。dlist_remove里的调用逻辑是：先把要删除节点的data通过出参传出去，然后如果list->destroy不为NULL，就调用它释放。注意这里dlist_remove本身不调用destroy，而是把data传出去让调用者决定——不对，仔细看代码，dlist_remove内部是调用了list->destroy的。让我重新理一下。
实际上dlist_remove的标准实现是这样的：
int dlist_remove(DList *list, DListElmt *element, void **data) { if (element == NULL || dlist_size(list) == 0) return -1; *data = element->data; if (element == dlist_head(list)) { list->head = element->next; if (list->head == NULL) list->tail = NULL; else element->next->prev = NULL; } else { element->prev->next = element->next; if (element->next == NULL) list->tail = element->prev; else element->next->prev = element->prev; } free(element); list->size--; return 0; }注意，这个实现里dlist_remove并没有调用list->destroy，它只是把element->data通过*data传出去，然后free(element)释放节点本身。data指向的内存由调用者负责释放。这和dlist_destroy里的写法是一致的——dlist_destroy拿到data后自己调用list->destroy(data)。所以destroy回调的调用责任在调用方，不在dlist_remove内部。这个分工很清晰：dlist_remove只管节点结构体的释放，data的释放交给上层。这样设计的好处是灵活性——有时候你删除一个节点只是想把它从链表里摘出来，data还要继续用，这时候就不该释放data。
3. 插入操作：四种位置，四套指针改法
双向链表的插入有四种位置：头部、尾部、某个元素之前、某个元素之后。dlist提供了dlist_ins_next和dlist_ins_prev两个接口，分别在某元素之后和之前插入。头部插入和尾部插入可以通过这两个接口配合NULL或者头尾指针来实现，但书里通常也会单独提供dlist_ins_next在头部插入的用法。这一节我把四种情况的指针改法逐一拆开，因为这是双向链表最容易写错的地方。
3.1 在元素之后插入：dlist_ins_next 的完整逻辑
dlist_ins_next的签名是int dlist_ins_next(DList *list, DListElmt *element, const void *data)，意思是把data包装成新节点，插到element后面。如果element是NULL，表示插到链表头部。实现逻辑分几步：
int dlist_ins_next(DList *list, DListElmt *element, const void *data) { DListElmt *new_element; if (element == NULL && dlist_size(list) != 0) return -1; if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL) return -1; new_element->data = (void *)data; if (dlist_size(list) == 0) { list->head = new_element; list->head->prev = NULL; list->head->next = NULL; list->tail = new_element; } else { new_element->next = element->next; new_element->prev = element; if (element->next == NULL) list->tail = new_element; else element->next->prev = new_element; element->next = new_element; } list->size++; return 0; }第一个判断element == NULL && dlist_size(list) != 0是防御性的：如果链表非空，却让你在NULL后面插入，这是矛盾的，直接返回错误。如果链表为空，element必须是NULL，此时新节点既是头也是尾，prev和next都置NULL。
非空链表的情况下，指针改法要按顺序来，顺序错了会丢节点。正确的顺序是：先设新节点的next和prev，再处理element->next的prev（如果存在），再处理element->next，最后处理tail。为什么这个顺序？因为new_element->next = element->next这一步必须在element->next = new_element之前，否则你就拿不到原来的后继了。而element->next->prev = new_element必须在element->next = new_element之前，因为改完之后element->next就指向新节点了，原来的后继就找不到了。这种"先保存、后修改"的顺序是链表指针操作的通则。
注意：
new_element->data = (void *)data;这里把const void *强转成void *赋给data字段。这个强转去掉了const限定，意味着链表内部可以修改data指向的内容。如果你传进来的是真正的常量，后续通过链表修改它会导致未定义行为。实际使用中一般不会去改data指向的内容，但知道这个强转的存在有好处。
3.2 在元素之前插入：dlist_ins_prev 与 ins_next 的对称性
dlist_ins_prev的逻辑和dlist_ins_next完全对称，只是方向反过来：
int dlist_ins_prev(DList *list, DListElmt *element, const void *data) { DListElmt *new_element; if (element == NULL && dlist_size(list) != 0) return -1; if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL) return -1; new_element->data = (void *)data; if (dlist_size(list) == 0) { list->head = new_element; list->head->prev = NULL; list->head->next = NULL; list->tail = new_element; } else { new_element->next = element; new_element->prev = element->prev; if (element->prev == NULL) list->head = new_element; else element->prev->next = new_element; element->prev = new_element; } list->size++; return 0; }空链表的情况和ins_next一模一样，因为空链表插入第一个节点，无论说"在之前"还是"在之后"，结果都是同一个。非空链表时，新节点的next指向element，prev指向element->prev。如果element是头节点（prev == NULL），新节点成为新的头，所以要更新list->head；否则更新element->prev->next。最后更新element->prev指向新节点。
这里有个容易混淆的点：dlist_ins_prev(list, element, data)是把新节点插到element前面，所以新节点成为element的前驱。而dlist_ins_next(list, element, data)是把新节点插到element后面，新节点成为element的后继。两个函数的element参数含义不同——一个是"参照物在前"，一个是"参照物在后"。写代码时如果搞反了，链表结构不会崩，但数据顺序会错，这种 bug 特别隐蔽，因为程序不报错，只是结果不对。
3.3 头部和尾部插入：用 ins_next 配合 NULL 和 tail 实现
dlist没有单独的dlist_ins_head和dlist_ins_tail，但用dlist_ins_next可以轻松实现。头部插入就是dlist_ins_next(list, NULL, data)——在NULL后面插入，也就是插到最前面。尾部插入就是dlist_ins_next(list, dlist_tail(list), data)——在尾节点后面插入。这两种用法在书里的示例代码中很常见。
为什么不在接口层面单独提供头尾插入？因为ins_next配合NULL和tail已经能覆盖这两种情况，再单独提供接口会增加 API 表面积，而且实现逻辑和ins_next高度重复。这是"最小接口"的设计思路——用最少的函数覆盖最多的场景。代价是使用者要记住"传NULL表示头部插入"这个约定，稍微有点隐晦。我个人在实际项目里会额外封装一层dlist_push_front和dlist_push_back的宏或者内联函数，让调用处的意图更清晰，但底层还是走ins_next。
提示：尾部插入用
dlist_ins_next(list, dlist_tail(list), data)是 O(1) 的，因为dlist_tail直接取list->tail，不需要遍历。这正是双向链表维护tail指针的价值所在。如果只有head没有tail，尾部插入就得从头遍历到尾，变成 O(n)。
4. 删除操作：dlist_remove 的边界处理是重头戏
删除是双向链表里边界情况最多的操作。要删除的节点可能在头部、尾部、中间，也可能是链表里唯一的节点。每种情况的指针改法都不同，漏掉任何一种都会导致链表断裂或者野指针。dlist_remove把这些情况都处理了，但代码读起来需要一点耐心。
4.1 删除头节点：更新 head 和新的头节点的 prev
删除头节点时，list->head要指向原头节点的后继。如果原头节点是链表里唯一的节点，那么它的后继是NULL，此时list->tail也要置NULL，表示链表空了。如果还有后继，新头节点的prev要置NULL，因为它现在是最前面的节点了。这三步缺一不可：
if (element == dlist_head(list)) { list->head = element->next; if (list->head == NULL) list->tail = NULL; else element->next->prev = NULL; }注意element->next->prev = NULL这一步用的是element->next而不是list->head，虽然此时两者相等。用element->next更直观地表达"原头节点的后继"，逻辑上更清晰。这种细节不影响正确性，但影响代码可读性。
4.2 删除非头节点：prev 和 next 的双向缝合
删除非头节点时，要把它的前驱和后继直接连起来：
else { element->prev->next = element->next; if (element->next == NULL) list->tail = element->prev; else element->next->prev = element->prev; }element->prev->next = element->next让前驱跳过当前节点指向后继。如果当前节点是尾节点（next == NULL），那么list->tail要更新为前驱；否则后继的prev要指向前驱。这两步完成了双向链表的"缝合"，当前节点就被从链表中摘出来了。最后free(element)释放节点内存，size减一。
这里有个隐含的前提：element->prev不为NULL。因为进入else分支意味着element不是头节点，所以prev一定存在。这个前提由前面的if保证，不需要额外判断。这种"分支互斥"的写法在链表操作里很常见，读代码时要能识别出每个分支的前置条件。
4.3 删除时的 data 出参：为什么用 void ** 而不是返回值
dlist_remove的第三个参数是void **data，用来把被删除节点的data传出去。为什么不用返回值？因为返回值已经被用来表示成功或失败了（0 成功，-1 失败）。C 语言没有异常机制，一个函数只能有一个返回值，所以"传出数据"和"报告状态"必须分开，一个走返回值，一个走出参。这是 C 接口设计的经典模式，你在标准库和各类开源库里会反复看到。
出参的用法是*data = element->data;，把节点里的data指针赋给调用者提供的变量。调用者拿到这个指针后，可以选择释放它、继续使用它、或者传给别的函数。这个设计把"节点结构体的释放"和"数据内存的释放"解耦了，前面已经讲过，这里再强调一次：dlist_remove只free(element)，不碰*data指向的内存。如果你需要释放数据，得自己调用list->destroy(*data)或者直接free(*data)。
注意：调用
dlist_remove时传的data出参不能是NULL，否则*data = element->data会解引用空指针导致崩溃。虽然标准实现里没有检查这个，但作为使用者必须保证传一个有效的地址。这是使用出参接口时的通用注意事项。
5. 遍历与查找：宏配合循环的惯用法
dlist没有提供专门的遍历函数，因为遍历的逻辑太简单了，用宏配合for循环就够了。书里给出的惯用法是用dlist_head取头节点，然后沿着dlist_next一路走。查找则是遍历加比较，找到就返回节点指针。
5.1 正向遍历的标准写法
正向遍历的典型代码：
DListElmt *element; for (element = dlist_head(list); element != NULL; element = dlist_next(element)) { /* 处理 dlist_data(element) */ }这个循环从head开始，每次取next，直到NULL结束。dlist_head和dlist_next都是宏，展开后就是字段访问，没有函数调用开销。循环体里用dlist_data(element)取数据。这个写法简洁、高效，是 C 链表遍历的标准范式。
有一个细节：循环条件用element != NULL而不是dlist_size(list)计数。用NULL判断更直接，也不依赖size字段的正确性。如果size因为某种 bug 算错了，用NULL判断的遍历仍然能正确走完，而用计数判断的遍历可能提前结束或者越界。这是一种"用结构本身保证正确性"的思路，比依赖外部计数器更可靠。
5.2 反向遍历：双向链表独有的能力
反向遍历是双向链表相比单链表的独有能力：
DListElmt *element; for (element = dlist_tail(list); element != NULL; element = dlist_prev(element)) { /* 处理 dlist_data(element) */ }从tail开始，每次取prev，直到NULL。这个能力在某些场景下非常有用，比如你要从后往前处理日志、从尾部开始回滚操作、或者实现一个支持双向迭代的容器。单链表要做到这一点，要么先反转链表（破坏结构），要么用递归（栈溢出风险），都不如双向链表直接走prev来得干净。
5.3 查找：遍历加比较，返回节点指针
查找没有专门的接口，自己写一个循环就行：
DListElmt *dlist_find(DList *list, const void *data, int (*match)(const void *, const void *)) { DListElmt *element; for (element = dlist_head(list); element != NULL; element = dlist_next(element)) { if (match(dlist_data(element), data)) return element; } return NULL; }这里用了一个match回调来做比较，而不是直接==。因为data是void *，直接比较指针只能判断是不是同一个对象，不能判断内容是否相等。用回调把比较逻辑交给使用者，链表本身不关心数据的具体类型。这个模式和destroy回调是同一个思路——把类型相关的操作外置，保持链表本身的通用性。
提示：查找的时间复杂度是 O(n)，如果频繁查找，考虑在链表之外再维护一个哈希表或者索引结构。链表适合频繁插入删除、少量查找的场景，不适合反过来。选数据结构时要看清访问模式，别拿链表当数组用。
6. 实战中踩过的坑与经验
纸上谈兵和实际写代码是两回事。dlist的接口看起来简单，但真正用起来，有几个坑我踩过不止一次，这里分享出来，希望能帮你少走弯路。
6.1 删除节点后继续用 element 指针
最常见的错误是在dlist_remove之后还继续用element指针。dlist_remove内部free(element)了，之后element就是野指针，再访问element->next或者element->data都是未定义行为，可能崩溃，也可能读到垃圾数据。正确的做法是在删除之前先把需要的信息存下来，比如：
DListElmt *next = dlist_next(element); dlist_remove(list, element, &data); element = next; /* 用存好的 next 继续遍历 */这个坑在遍历中删除节点时特别容易踩。如果你写for (element = head; element; element = dlist_next(element))然后在循环体里删除element，下一次迭代的dlist_next(element)就是在访问已释放的内存。解决办法就是上面这样，先存next再删。
6.2 destroy 回调里不要访问链表
destroy回调是在dlist_destroy的循环里被调用的，此时链表正在被拆解，head和tail的状态在变化。在destroy回调里访问链表结构（比如试图删除别的节点）会导致不可预期的结果。destroy回调应该只做一件事：释放传进来的data指向的内存。不要在里面做任何和链表结构相关的操作。
6.3 空链表和单节点链表的特殊处理
空链表插入第一个节点时，新节点的prev和next都必须是NULL，head和tail都指向它。单节点链表删除唯一节点时，head和tail都要置NULL。这两个边界情况在代码里都有专门的分支处理，但如果你自己手写链表操作而不用dlist的接口，很容易漏掉其中一个，导致head或tail变成悬空指针。我的建议是尽量用封装好的接口，不要自己手动改指针，除非你非常清楚每一个字段的状态。
6.4 size 字段的维护要贯穿所有操作
size字段在每次插入时加一，每次删除时减一。这个维护必须严格，漏掉任何一次都会导致size和实际节点数不一致。size不一致的后果是：dlist_size返回错误的值，依赖size做循环次数的代码会出错，dlist_destroy的while (dlist_size(list) > 0)可能死循环或者提前结束。所以每次改链表结构，都要检查size有没有同步更新。这是个体力活，但没有捷径，只能靠仔细。
6.5 多线程环境下 dlist 不是线程安全的
dlist的所有操作都没有加锁，多线程同时操作同一个链表会导致数据竞争，指针可能被改乱，链表结构被破坏。如果需要在多线程环境使用，要么在外部加锁（比如用一个互斥锁保护整个链表），要么用线程安全的数据结构。不要指望dlist自己能处理并发，它从设计上就不是干这个的。
注意：外部加锁时，锁的粒度要覆盖整个操作序列，不能只锁单次
dlist_ins_next调用。比如"先查找再插入"这个组合操作，如果查找和插入之间释放了锁，另一个线程可能在这期间修改链表，导致插入位置失效。正确的做法是把查找和插入放在同一个锁的保护范围内。
7. 从 dlist 延伸出去的设计思考
把dlist吃透之后，你会发现它的很多设计决策可以迁移到别的场景。这一节聊几个我觉得最有价值的延伸点，不是教你写新代码，而是帮你建立一种"看数据结构看设计意图"的眼光。
7.1 为什么用 void * 而不是泛型
C 没有泛型，void *是最接近泛型的机制。它的代价是类型安全——编译器不知道data实际指向什么类型，你传错了类型它也不报错，运行时才可能崩溃。但它的好处是极致的通用性，同一个dlist可以存任何东西。C++ 的模板在编译期做类型检查，更安全，但会为每种类型生成一份代码，二进制体积更大。两种方案各有取舍，C 的选择是"运行时灵活、编译期不管"，这符合 C 语言"信任程序员"的哲学。
7.2 回调函数：把变化的部分外置
dlist用了两个回调：destroy和查找时的match。这两个回调的共同点是"操作依赖于数据类型，但链表本身不想知道具体类型"。把这类操作做成回调，链表就能保持通用。这个模式叫"策略模式"的 C 语言实现——把算法策略作为参数传入，而不是硬编码在结构里。你在写其他通用模块时也可以套用这个思路：凡是"因数据类型而异"的操作，都考虑做成回调。
7.3 双向链表的空间换时间账本
双向链表每个节点比单链表多一个prev指针。在 64 位系统上，一个指针 8 字节，所以每个节点多 8 字节开销。假设你存的是int（4 字节），加上data指针（8 字节）和两个指针（16 字节），一个节点总共 28 字节左右，其中有效数据只占 4 字节，开销是数据的 6 倍。这个账要算清楚：如果你的数据本身很小、节点数量很大，双向链表的内存开销会很明显。这时候可以考虑用数组或者更紧凑的结构。但如果你的数据本身就不小（比如每个节点存一个结构体），那多一个指针的开销就微不足道了。选不选双向链表，要看数据大小和操作模式的综合权衡。
7.4 迭代器失效问题
dlist没有显式的迭代器概念，但DListElmt *指针实际上就充当了迭代器的角色。这里有一个和 C++ 容器类似的问题：删除一个节点后，指向它的指针就失效了。更隐蔽的是，某些操作可能导致其他节点的指针也失效——不过在dlist里，插入和删除只影响相邻节点的指针，不会导致整个链表的所有指针失效（不像vector扩容那样）。理解这一点，你就能判断什么时候可以安全地持有节点指针，什么时候必须重新获取。
8. 自己动手实现时的检查清单
如果你打算不看现成代码，自己从零写一个dlist，下面这份清单可以帮你自查。每一条都是我在实际编码中验证过的关键点，漏掉任何一条都可能导致 bug。
| 检查项 | 具体要求 | 常见错误 |
|---|---|---|
| 空链表插入 | 新节点 prev 和 next 都置 NULL，head 和 tail 都指向它 | 只更新 head 忘了 tail |
| 头部插入 | 新节点 prev 置 NULL，原头节点 prev 指向新节点 | 忘了更新原头节点的 prev |
| 尾部插入 | 新节点 next 置 NULL，原尾节点 next 指向新节点 | 忘了更新 tail 指针 |
| 删除头节点 | head 指向后继，后继 prev 置 NULL | 后继为 NULL 时忘了置 tail |
| 删除尾节点 | tail 指向前驱，前驱 next 置 NULL | 前驱为 NULL 时忘了置 head |
| 删除中间节点 | 前驱 next 指向后继，后继 prev 指向前驱 | 只改了一个方向 |
| size 维护 | 每次插入加一，每次删除减一 | 某个分支漏了更新 |
| 内存释放 | 删除节点时 free 节点，data 由调用者决定 | 重复释放或漏释放 |
这份清单的核心逻辑是：双向链表的每个指针改动都要"双向对称"——改了next就要考虑对应的prev，改了head就要考虑tail。任何单边的改动都是 bug 的温床。写的时候可以对着清单逐条过，写完再用几个边界用例测一下：空链表插入、单节点删除、头尾操作、中间操作，这四类用例覆盖了绝大多数指针逻辑。
最后分享一个我调试链表问题的小技巧：在插入和删除操作前后，写一个dlist_dump函数把整个链表的结构打印出来——每个节点的地址、data值、prev和next指向的地址。链表出问题时，肉眼对比操作前后的结构变化，比单步调试快得多。尤其是指针改错方向这种 bug，打印出来一眼就能看出来哪个节点的prev或next指错了地方。这个函数不用写得多漂亮，能打印就行，调试完删掉或者用宏关掉，不影响正式代码。
