本篇核心知识STL 容器基础list 双向链表、范围 for 循环、迭代器、手写双向循环链表、双向链表常用接口、链表经典算法反转 / 排序 / 去重 / 合并、友元在链表中的使用一、STL list 容器基础概念list 是 C 标准模板库 ST 提供的双向链表容器底层由双向节点构成封装了链表增删改查全部接口无需手动管理节点与堆内存。特性物理内存不连续依靠前后指针关联节点任意位置插入 / 删除效率 O (1)随机访问不支持只能迭代遍历自动管理内存容器销毁自动释放全部节点支持泛型可存放任意合法数据类型内置 / 自定义类。代码示例#include list #include iostream using namespace std; ​ int main() { listint lst; // 尾插 lst.push_back(10); lst.push_back(20); // 头插 lst.push_front(5); return 0; }拓展list 与 vector 区别vector顺序连续内存随机访问快、中间增删慢list链式离散随机访问慢、任意位置增删快。二、list 遍历两种写法迭代器、范围 for1. 迭代器遍历概念迭代器是容器通用指针封装用来指向容器元素begin()首元素迭代器、end()末尾无效迭代器尾后。特性语法容器类型::iterator 迭代器名it向后移动*it取元素值end 不作为有效元素循环终止条件it ! lst.end()。listint::iterator it lst.begin(); while(it ! lst.end()) { cout *it ; it; }2. 范围 for (C11 新特性)概念自动推导容器元素类型自动遍历全部元素底层由迭代器实现。特性auto自动推导变量类型auto 可修改元素const auto只读不修改。//只读遍历 for(auto x : lst) cout x; //可修改 for(auto x : lst) x *2;相似对比迭代器灵活支持中途增删、定点遍历范围 for代码简洁适合全容器遍历中途删除易失效。三、手写双向链表设计思路概念自行用 C 类封装双向链表节点包含数据域 前驱 prev 后继 next整体链表类统一管理头尾。特性节点结构prev上节点地址、data、next下节点地址链表增设哨兵头结点头傀儡不存有效数据统一空链表 / 首节点操作逻辑链表类将节点私有化通过成员函数访问需要时声明友元list 类 / 迭代器访问私有节点。代码示例节点与链表基础框架templatetypename T struct Node { T data; NodeT* prev; NodeT* next; Node(const T val):data(val),prev(nullptr),next(nullptr){} }; ​ templatetypename T class MyList { private: NodeT* head; //哨兵头 public: MyList(){ head new NodeT(T()); } ~MyList(){/*析构释放全部节点*/} };拓展友元使用场景节点成员私有化迭代器 / 链表需要访问节点私有成员将对应类声明为节点友元。四、双向链表核心接口增、删1. 指定位置插入概念在 pos 迭代对应节点前插入新节点特性插入固定三步新节点前驱 原前驱节点新节点后继 原目标节点原前驱 next 指向新节点、原目标 prev 指向新节点。顺序不能乱防止断链。//伪代码示意 NodeT* newNode new Node(val); newNode-prev pos-prev; newNode-next pos; pos-prev-next newNode; pos-prev newNode;2. 指定位置删除概念摘除目标节点前后节点互相链接delete 释放内存特性先让被删节点的前驱 -next 被删后继被删后继 -prev 被删前驱delete 释放当前节点杜绝内存泄漏。NodeT* del pos; del-prev-next del-next; del-next-prev del-prev; delete del;五、双向链表经典算法5.1 链表反转概念改变双向链表所有节点的prev前驱、next后继指针指向颠倒节点顺序原首节点变为尾节点原尾节点变为首节点仅修改指针不改动节点内部数据。特性核心逻辑遍历链表逐个交换当前节点的前驱、后继指针哨兵头结点保持不变仅反转有效数据节点时间复杂度 (O(n))仅需一次完整遍历相比单链表双向链表反转逻辑更直观可借助前驱指针回溯。代码示例基于模板双向链表templatetypename T void MyListT::reverse() { if (head-next nullptr) // 空链表无需反转 return; ​ NodeT* cur head-next; NodeT* temp nullptr; // 遍历所有有效节点交换prev和next while (cur ! nullptr) { // 暂存原后继节点 temp cur-next; // 交换前驱、后继指针 cur-next cur-prev; cur-prev temp; cur temp; } // 交换哨兵头与原首尾节点的指向 temp head-next; head-next head-prev; head-prev temp; }拓展单链表反转需要额外临时节点记录后继双向链表利用prev天然支持双向遍历实现复杂度更低。5.2 链表排序概念对双向链表的有效节点进行排序优先交换节点指针指向而非交换节点内部数据区别于数组直接交换元素值的实现方式。特性核心原因若节点存储大型自定义对象拷贝 / 交换数据开销极大修改指针仅操作地址效率更高常用算法冒泡排序适配链表结构实现简单排序过程中需同步维护每个节点的prev和next指针防止断链哨兵头结点位置始终固定不参与排序。代码示例双向链表冒泡排序templatetypename T void MyListT::sort() { if (head-next nullptr || head-next-next nullptr) return; // 空链表/单个节点无需排序 ​ NodeT* p; // 外层控制排序轮数 for (p head-next; p-next ! nullptr; p p-next) { NodeT* q head-next; // 内层相邻节点比较交换指针 while (q-next ! nullptr) { if (q-data q-next-data) { // 交换两个相邻节点仅修改指针不交换数据 NodeT* left q; NodeT* right q-next; left-next right-next; if (right-next ! nullptr) right-next-prev left; right-prev left-prev; left-prev-next right; right-next left; left-prev right; q right; } q q-next; } } }相似概念对比数组排序内存连续直接交换元素值实现简单链表排序内存离散优先交换指针大数据场景性能优势明显。5.3 删除重复节点概念遍历有序双向链表查找数值重复的节点摘除重复节点并释放堆内存最终保留唯一值节点保证链表无重复元素。特性前提一般针对有序链表无序链表去重效率极低操作步骤定位重复节点 → 修改前后节点指针完成摘除 →delete释放节点防止内存泄漏遍历过程中指针需谨慎移动避免节点丢失。代码示例templatetypename T void MyListT::eraseRepeat() { if (head-next nullptr) return; NodeT* cur head-next; while (cur-next ! nullptr) { // 当前节点与下一个节点值重复 if (cur-data cur-next-data) { NodeT* delNode cur-next; // 摘除重复节点 cur-next delNode-next; if (delNode-next ! nullptr) delNode-next-prev cur; // 释放内存 delete delNode; } else { cur cur-next; } } }拓展无序链表去重通常需要额外容器辅助记录已存在的值时间、空间开销会增加。5.4 两个有序链表合并概念将两条同排序规则的有序双向链表合并为一条新的有序双向链表全程仅修改节点指针指向不新建节点、不拷贝数据。特性要求两个原链表排序规则一致同为升序 / 同为降序核心逻辑依次比较两条链表当前节点值选取较小节点接入新链表合并完成后原链表失效所有节点归属新链表时间复杂度 (O(mn))m、n 为两条链表节点总数。代码示例合并两个升序双向链表templatetypename T // 传入两个有序链表返回合并后的新链表头 NodeT* mergeList(NodeT* h1, NodeT* h2) { NodeT* newHead new NodeT(); // 新哨兵头结点 NodeT* tail newHead; NodeT* p1 h1-next; NodeT* p2 h2-next; // 同时遍历两个链表择优接入 while (p1 ! nullptr p2 ! nullptr) { if (p1-data p2-data) { tail-next p1; p1-prev tail; p1 p1-next; } else { tail-next p2; p2-prev tail; p2 p2-next; } tail tail-next; } // 接入剩余节点 if (p1 ! nullptr) { tail-next p1; p1-prev tail; } if (p2 ! nullptr) { tail-next p2; p2-prev tail; } return newHead; }拓展合并后建议手动释放原链表的哨兵头结点避免内存冗余。六、构造函数与析构函数双向链表专属概念构造函数创建链表对象时自动执行完成哨兵头结点初始化析构函数链表对象生命周期结束时自动执行逐个释放所有节点内存彻底杜绝内存泄漏。特性构造函数链表初始化时仅创建哨兵头结点其prev、next默认置为nullptr无需创建有效数据节点保证空链表结构合法。析构函数遍历所有有效数据节点逐个delete释放最后释放哨兵头结点遵循「先释数据节点再释头结点」顺序析构函数无参数、无返回值不能重载。代码示例templatetypename T // 构造函数初始化哨兵头结点 MyListT::MyList() { head new NodeT(); head-prev nullptr; head-next nullptr; } templatetypename T // 析构函数释放全部节点 MyListT::~MyList() { NodeT* p head-next; // 释放所有有效节点 while (p ! nullptr) { NodeT* temp p; p p-next; delete temp; } // 最后释放哨兵头结点 delete head; head nullptr; }拓展若不自定义析构编译器默认析构不会释放堆上节点必然造成内存泄漏可结合拷贝构造、赋值重载实现链表深拷贝防止浅拷贝导致的重复释放问题。七、模板在链表中的应用概念使用 C类模板封装双向链表节点与链表整体脱离固定数据类型限制一套代码可适配整型、浮点型、字符串、自定义结构体 / 类等任意数据类型。特性语法规则以templateclass T或templatetypename T作为模板声明T为通用类型占位符作用域模板声明作用于后续整个类 / 成员函数类外实现成员函数时必须重复书写模板头实例化使用时显式指定具体类型如MyListint、MyListstring编译器自动生成对应类型代码兼容性模板代码建议写在同一头文件分离编译会导致链接报错。代码示例完整模板框架#include iostream using namespace std; // 模板声明 T通用数据类型 templateclass T // 模板节点类 struct Node { T data; NodeT* prev; NodeT* next; Node(const T val) : data(val), prev(nullptr), next(nullptr) {} }; // 模板链表类 templateclass T class MyList { private: NodeT* head; // 哨兵头结点 public: MyList(); // 构造 ~MyList(); // 析构 void pushBack(const T val); // 尾插 void reverse(); // 反转 void sort(); // 排序 void eraseRepeat();// 去重 };相似概念对比普通链表固定数据类型多类型需求需重复编写多套代码模板链表泛型设计代码复用性极强是 STL 容器的核心实现思想。拓展模板支持多类型参数templateclass T1, class T2可对特定类型做模板特化定制特殊逻辑模板不支持运行期类型推导必须在编译期确定具体类型。