我去年整理代码时翻到一个老项目——手写的 C++ 模板双向链表。当时我在做一个需要频繁在中间位置插入删除任务的小模块，本来可以直接用std::list，但我想弄清楚 list 内部到底怎么管理节点、迭代器是怎么工作的，干脆按标准库的接口自己实现了一个。这一写，反而把模板、指针、内存管理、迭代器这几块 C++ 里最难啃的骨头全串起来了。
这份代码对老手来说属于基本功，但对刚学完语法、正准备往数据结构实战走的同学，价值比干看 STL 源码大得多。它支持任意数据类型，List<int>、List<std::string>、List<自定义结构体>都能存；插入删除是 O(1) 复杂度；还带了一个能和范围内 for 无缝配合的迭代器。读完这篇文章，你可以直接拿到一份可编译的源码，更重要的是搞清楚每一步为什么要这么写。
1. 双向链表模板的设计思路：为什么值得自己写一遍
1.1 项目背景：从“会用 list”到“能写出 list”
当时项目的需求大概是这样的：有一批任务对象，需要按优先级在任意位置插入，删除某个中间任务时也不能拉着后面的数据一起动。std::list本身可以胜任，但我还有一个额外的诉求——希望给每个节点加上一个“状态标记”，同时随时统计链表中处于特殊状态的节点数量。如果把任务对象包一层再塞进std::list，每次插入都要复制；如果用裸指针数组，插入删除又很别扭。于是“自定义链表”这个方案就成了最顺手的选择。
顺着这个需求你会发现，自己写链表不是为了造轮子，而是为了能在节点结构上做文章。比如侵入式链表（节点内部直接内置 prev 和 next 指针）、带自定义内存池的链表，都必须先理解双向链表的基本实现逻辑才改得动。另外，很多公司的面试手撕代码环节都爱考链表，把自己完整实现过一遍，遇到变体题心里就有底，至少不会被“反转链表”“判断环”这类题目问住。
1.2 为什么用模板而不是 void*
C 语言时代，要写一个“通用链表”，无非用void*存数据，或者用宏展开。void*的最大问题是类型不安全：往链表里塞一个int，取出来的时候当成double用，编译器根本不会拦你，运行时直接乱套。宏展开相当于给每种类型复制一份代码，可维护性极差，改一个逻辑要同步改多处。
模板解决的是“代码生成”问题：List<int>和List<std::string>用同一份模板，编译器会在编译期分别生成类型安全的代码。类型检查发生在编译期，存错类型就直接编译报错，而不是等程序跑起来才爆炸。这一点和 Java 泛型的“类型擦除”不一样，C++ 模板是真正在编译期为每个实例化类型生成对应代码，理论上运行效率也更高。
这里插一句，模板不是没有代价。编译期实例化会让编译时间变长、代码膨胀，而且模板的声明和定义不能像普通函数那样分藏在.cpp文件里。这个坑我会在第 4 章单独讲，因为它太经典了。
1.3 双向链表 vs 单链表：一个 prev 指针换来什么
单向链表结构简单，每个节点只有一个 next 指针，遍历只能向前。删除某个节点时，你必须先找到它的前驱节点，因为要改前驱的 next 指向。这就意味着，“删除已知节点”的时间复杂度最坏是 O(n)——哪怕你已经定位到要删的节点了，却拿不到它的前驱，只能从头部重新走一遍。
双向链表给每个节点多存一个 prev 指针，删除当前节点时直接通过 prev 找到前驱，改两条指针就够了，时间复杂度从 O(n) 降到了 O(1)。代价是每个节点多出 8 字节（64 位系统下一个指针）内存，以及插入删除时多维护一次指针操作。在节点本身存了大量数据时，这点内存开销可以忽略；但如果节点很小、数量很大，就要认真算算这笔账了。
我项目里选了双向，是因为任务对象本身不小，8 字节的开销无所谓，而删除操作是高频动作，必须做到 O(1)。这就是双向和单链表取舍的核心：用空间换时间。
2. 核心结构拆解：节点、迭代器与哨兵节点
2.1 节点 Node 的设计细节
链表的基础就是节点。节点里至少要有三样东西：数据本身、指向前一个节点的指针、指向后一个节点的指针。我的定义是这样的：
template<typename T> struct Node { T data; Node* prev; Node* next; Node() : data{}, prev(nullptr), next(nullptr) {} explicit Node(const T& value) : data(value), prev(nullptr), next(nullptr) {} };用 struct 而不是 class，是因为节点内部的数据成员需要被链表直接访问，而 struct 的默认访问级别是 public，省去手动写一堆public:的啰嗦。这不是风格问题，而是实际编码效率问题。
data{}是 C++
