本篇核心知识：自定义双向链表迭代器、链表删除 / 插入 / 拼接 / 反转操作、链表冒泡排序、STL 容器嵌套、容器底层与面试要点
一、双向链表迭代器详解
概念
迭代是对原生指针的封装类，自定义双向链表的迭代器本质就是封装节点指针，重载++、--、*、->等运算符，模拟指针行为，实现统一遍历接口。迭代器隶属于对应容器，不同容器迭代器底层实现不同。
特性
双向链表迭代器支持前置 ++/ 后置 ++、前置 --/ 后置 --，可双向遍历；
前置自增 / 自减：先移动指针，再返回自身，可返回引用；
后置自增 / 自减：先保留当前状态，再移动指针，需生成临时对象，不能返回引用；
begin()：指向链表第一个有效数据节点；end()：指向尾结点（尾后位置），遵循 ST 标准前闭后开遍历区间；迭代器仅操作节点指针，不修改节点数据本身。
代码示例（双向链表迭代器完整实现）
#include <iostream> using namespace std; // 链表节点模板 template<typename T> struct Node { T data; Node<T>* prev; Node<T>* next; Node(const T& val) : data(val), prev(nullptr), next(nullptr) {} }; // 双向链表类（内嵌迭代器） template<typename T> class DoubleList { public: // 自定义迭代器类（内嵌类） class Iterator{ private: Node<T>* cur; // 封装节点指针 public: Iterator(Node<T>* p = nullptr) : cur(p) {} // 解引用 T& operator*() { return cur->data; } // 成员访问 Node<T>* operator->() { return cur; } // 前置++ Iterator& operator++(){ cur = cur->next; return *this; } // 后置++（int占位符标识后置） Iterator operator++(int){ Iterator temp = *this; cur = cur->next; return temp; // 临时对象，不能返回引用 } // 前置-- Iterator& operator--(){ cur = cur->prev; return *this; } // 后置-- Iterator operator--(int){ Iterator temp = *this; cur = cur->prev; return temp; } // 判等、判不等 bool operator==(const Iterator& it) const{ return cur == it.cur; } bool operator!=(const Iterator& it) const{ return cur != it.cur; } }; // 链表对外接口 Iterator begin() { return Iterator(head->next); } Iterator end() { return Iterator(tail); } private: Node<T>* head; // 头结点（无数据） Node<T>* tail; // 尾结点（无数据） public: DoubleList(){ head = new Node<T>(T()); tail = new Node<T>(T()); head->next = tail; tail->prev = head; } ~DoubleList(){ Node<T>* p = head->next; while (p != tail){ Node<T>* del = p; p = p->next; delete del; } delete head; delete tail; } // 尾插 void push_back(const T& val); };拓展
vector迭代器底层就是普通指针，无需重载过多运算符；链表、树等容器必须自定义迭代器，这是不同容器迭代器的核心区别。
二、链表删除操作（按迭代器删除）
概念
接收迭代器参数，删除该迭代器指向的节点，修改前后节点的指针指向，释放内存并返回下一个有效迭代器（解决迭代器失效问题）。
特性
操作核心：先保存待删节点的后继节点，再修改前驱与后继的指针连接；
步骤：保存后继 → 重定向指针 → 释放节点内存 → 返回后继迭代器；
带头尾结点链表无需判断边界，代码统一；
删除后原迭代器失效，必须使用返回值继续遍历。
代码示例
template<typename T> typename DoubleList<T>::Iterator DoubleList<T>::erase(Iterator pos) { Node<T>* delNode = pos.operator->(); // 获取待删节点 Node<T>* nextNode = delNode->next; // 保存后继节点 // 重定向指针，完成断链 delNode->prev->next = nextNode; nextNode->prev = delNode->prev; delete delNode; // 释放内存 return Iterator(nextNode); // 返回下一个迭代器 }易错点
不可先释放节点再修改指针，会导致前驱节点失去后继地址，造成断链、内存泄漏。
三、区间删除
概念
删除[start, end)区间内所有节点（遵循前闭后开规则），仅修改首尾指针，批量摘除中间节点并释放内存。
特性
区间为左闭右开，
end指向的节点不删除；先记录区间首尾的前驱、后继节点，再批量释放中间节点；
操作完成后将两端节点重新连接。
代码示例
template<typename T> void DoubleList<T>::erase(Iterator start, Iterator end) { Node<T>* s = start.operator->(); Node<T>* e = end.operator->(); Node<T>* pre = s->prev; Node<T>* next = e; // 批量释放区间内节点 Node<T>* cur = s; while (cur != e) { Node<T>* temp = cur; cur = cur->next; delete temp; } // 重连两端 pre->next = next; next->prev = pre; }四、链表拼接操作
概念
将一个完整链表整体插入到当前链表指定迭代器位置，合并两条链表，原链表置空（不释放内存）。
特性
仅修改指针指向，不拷贝节点数据，效率极高；
拼接完成后，原链表必须重置为空链表（头结点 next 指向尾结点），防止野指针；
区分：插入到迭代器之前/之后，指针修改逻辑不同。
代码示例
// 将链表lst插入到pos迭代器之前 template<typename T> void DoubleList<T>::splice(Iterator pos, DoubleList<T>& lst) { if (lst.begin() == lst.end()) return; // 原链表为空，直接返回 Node<T>* cur = pos.operator->(); Node<T>* lstHead = lst.head->next; Node<T>* lstTail = lst.tail->prev; // 完成拼接 cur->prev->next = lstHead; lstHead->prev = cur->prev; lstTail->next = cur; cur->prev = lstTail; // 原链表置空，不释放头尾结点 lst.head->next = lst.tail; lst.tail->prev = lst.head; }拓展
链表拼接相比数组拼接优势极大，数组需要批量拷贝数据，链表仅修改指针。
五、链表冒泡排序
概念
基于冒泡思想对双向链表排序，优先交换节点指针，不交换数据（大数据 / 自定义对象场景性能更优）。
特性
排序前提：元素个数 ≥ 2，空链表 / 单个节点无需排序；
冒泡规则：多层循环，外层控制排序趟数，内层相邻节点比较；
双向链表优势：可通过
prev直接获取前驱节点，单链表无法做到；每一趟排序都会将当前最大值 “冒泡” 到末尾，下一趟比较次数递减。
代码示例
template<typename T> void DoubleList<T>::sort() { int len = 0; // 统计链表有效节点个数 for (auto it = begin(); it != end(); ++it) len++; if (len < 2) return; // 外层：排序趟数 for (int i = 0; i < len - 1; ++i) { Node<T>* p = head->next; // 内层：相邻节点比较 for (int j = 0; j < len - 1 - i; ++j) { if (p->data > p->next->data) { // 交换两个相邻节点（修改指针，不交换数据） Node<T>* p1 = p; Node<T>* p2 = p->next; Node<T>* p3 = p2->next; p1->next = p3; p2->prev = p1->prev; p1->prev->next = p2; p2->next = p1; p1->prev = p3->prev; p3->prev = p1; } p = p->next; } } }对比
数组冒泡：直接交换元素值，内存连续操作简单；
链表冒泡：交换节点指针，逻辑复杂，但海量数据下开销更小。
六、链表反转（头插法实现）
概念
利用头插法遍历原链表，逐个将节点插入新链表头部，实现整体反转。
特性
不新建节点，仅修改指针指向；
时间复杂度 (O(n))，一次遍历即可完成；
双向链表也可直接交换每个节点
prev与next指针实现反转。
代码示例（头插法反转）
template<typename T> void DoubleList<T>::reverse() { Node<T>* newHead = head; Node<T>* cur = head->next; head->next = tail; tail->prev = head; while (cur != tail) { Node<T>* temp = cur->next; // 头插 cur->next = newHead->next; newHead->next->prev = cur; newHead->next = cur; cur->prev = newHead; cur = temp; } }七、容器嵌套与拓展应用
概念
STL / 自定义容器的模板参数可以是另一个容器，实现二维、多层数据结构。
特性
基础用法：
vector<vector<int>>模拟二维数组；进阶用法：
vector<list<int>>模拟哈希表拉链法（解决哈希冲突经典方案）；模板类型约束：嵌套容器内的类型，必须支持拷贝、对应运算符重载。
代码示例
#include <vector> #include <list> using namespace std; // 1. vector嵌套 = 二维动态数组 vector<vector<int>> vec2d; // 2. vector + list 模拟哈希拉链法 vector<list<int>> hashTable;拓展
C++ 标准库未直接提供哈希表容器（早期），开发中常使用vector+list组合自行实现，是底层开发常用技巧。
八、容器核心对比 & 选型总结
1. vector（顺序表）
底层：连续内存数组；
优点：下标随机访问 (O(1))，尾部操作效率高；
缺点：中间增删会挪动元素，频繁扩容影响性能；
适用：查询多、尾部操作多，尽量提前预留容量减少扩容。
2. list（双向链表）
底层：离散节点，前驱 + 后继双指针；
优点：任意位置增删仅改指针 (O(1))，无内存挪动；
缺点：不支持随机访问，遍历效率低；
适用：频繁随机增删、数据动态变化的场景。
通用编码规范
等值判断：
nullptr == p（常量放左侧），避免漏写等号引发 bug；指针操作：优先画图分析指针走向，杜绝断链、野指针；
内存管理：堆节点使用后必须
delete，防止泄漏。
九、补充知识点：容器类型要求
概念
STL 容器 / 模板类对存储类型存在隐性约束。
特性
自定义类型必须支持拷贝构造（容器添加元素会拷贝对象）；
排序、比较场景，需要重载
==、<、>等运算符；类中包含指针成员时，必须实现深拷贝，防止内存错误。
