C++模板双向链表实战：手写STL list-北京尧图网络

我去年整理代码时翻到一个老项目——手写的 C 模板双向链表。当时我在做一个需要频繁在中间位置插入删除任务的小模块本来可以直接用std::list但我想弄清楚 list 内部到底怎么管理节点、迭代器是怎么工作的干脆按标准库的接口自己实现了一个。这一写反而把模板、指针、内存管理、迭代器这几块 C 里最难啃的骨头全串起来了。这份代码对老手来说属于基本功但对刚学完语法、正准备往数据结构实战走的同学价值比干看 STL 源码大得多。它支持任意数据类型Listint、Liststd::string、List自定义结构体都能存插入删除是 O(1) 复杂度还带了一个能和范围内 for 无缝配合的迭代器。读完这篇文章你可以直接拿到一份可编译的源码更重要的是搞清楚每一步为什么要这么写。1. 双向链表模板的设计思路为什么值得自己写一遍1.1 项目背景从“会用 list”到“能写出 list”当时项目的需求大概是这样的有一批任务对象需要按优先级在任意位置插入删除某个中间任务时也不能拉着后面的数据一起动。std::list本身可以胜任但我还有一个额外的诉求——希望给每个节点加上一个“状态标记”同时随时统计链表中处于特殊状态的节点数量。如果把任务对象包一层再塞进std::list每次插入都要复制如果用裸指针数组插入删除又很别扭。于是“自定义链表”这个方案就成了最顺手的选择。顺着这个需求你会发现自己写链表不是为了造轮子而是为了能在节点结构上做文章。比如侵入式链表节点内部直接内置 prev 和 next 指针、带自定义内存池的链表都必须先理解双向链表的基本实现逻辑才改得动。另外很多公司的面试手撕代码环节都爱考链表把自己完整实现过一遍遇到变体题心里就有底至少不会被“反转链表”“判断环”这类题目问住。1.2 为什么用模板而不是 void*C 语言时代要写一个“通用链表”无非用void*存数据或者用宏展开。void*的最大问题是类型不安全往链表里塞一个int取出来的时候当成double用编译器根本不会拦你运行时直接乱套。宏展开相当于给每种类型复制一份代码可维护性极差改一个逻辑要同步改多处。模板解决的是“代码生成”问题Listint和Liststd::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 的设计细节链表的基础就是节点。节点里至少要有三样东西数据本身、指向前一个节点的指针、指向后一个节点的指针。我的定义是这样的templatetypename 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

C++模板双向链表实战：手写STL list

相关推荐

ShareX 免费截屏指南：一次按键出图，打码、长截图、自动上传都省时间

STM32Cube_FW_F1 V1.8.0固件包详解：下载安装与工程配置指南

OpenCore Legacy Patcher 手把手:3 步在老 Mac 上装最新 macOS

更多资讯

移动端导航五种模式：空间利用与用户体验的成本决策

彻底搞懂Vue nextTick：异步更新、DOM更新与事件循环原理

烽火光猫厂家调试软件实战：Telnet、TTL、EV2400全解析

如何用 FIPS 140 快照校验 Go crypto 标准库？GOFIPS140 测试流程与 fips140.sum 校验

shadcn/ui 新建项目时 Base UI 与 Radix 基础组件库怎么选？

一串9引发的生产事故：边界值治理与系统稳定性实践

今日更新

在S3C2410上移植Nucleus RTOS：启动、驱动与实时性调优实战

2026年Turnitin降重降AI二合一红黑榜：能过和别碰

2026期刊投稿AI写作工具实测：6款打分谁更值得用

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？