企业官网建设流程全解析

本篇核心知识：STL 容器基础（list 双向链表）、范围 for 循环、迭代器、手写双向循环链表、双向链表常用接口、链表经典算法（反转 / 排序 / 去重 / 合并）、友元在链表中的使用

一、STL list 容器基础

概念

list 是 C++ 标准模板库 ST 提供的双向链表容器，底层由双向节点构成，封装了链表增删改查全部接口，无需手动管理节点与堆内存。

特性

1. 物理内存不连续，依靠前后指针关联节点；

2. 任意位置插入 / 删除效率 O (1)，随机访问不支持（只能迭代遍历）；

3. 自动管理内存，容器销毁自动释放全部节点；

4. 支持泛型，可存放任意合法数据类型（内置 / 自定义类）。

代码示例

#include <list> #include <iostream> using namespace std; ​ int main() { list<int> lst; // 尾插 lst.push_back(10); lst.push_back(20); // 头插 lst.push_front(5); return 0; }

拓展：list 与 vector 区别

vector：顺序连续内存，随机访问快、中间增删慢；

list：链式离散，随机访问慢、任意位置增删快。

二、list 遍历两种写法（迭代器、范围 for）

1. 迭代器遍历

概念

迭代器是容器通用指针封装，用来指向容器元素，begin()首元素迭代器、end()末尾无效迭代器（尾后）。

特性

语法：容器类型::iterator 迭代器名；

++it向后移动，*it取元素值；

end 不作为有效元素，循环终止条件it != lst.end()。

list<int>::iterator it = lst.begin(); while(it != lst.end()) { cout << *it << " "; ++it; }

2. 范围 for (C++11 新特性)

概念

自动推导容器元素类型，自动遍历全部元素，底层由迭代器实现。

特性

auto自动推导变量类型；

auto &可修改元素，const auto&只读不修改。

//只读遍历 for(auto x : lst) cout << x; //可修改 for(auto &x : lst) x *=2;

相似对比

迭代器：灵活支持中途增删、定点遍历；

范围 for：代码简洁，适合全容器遍历，中途删除易失效。

三、手写双向链表设计思路

概念

自行用 C++ 类封装双向链表，节点包含数据域 + 前驱 prev + 后继 next，整体链表类统一管理头尾。

特性

1. 节点结构：prev（上节点地址）、data、next（下节点地址）；

2. 链表增设哨兵头结点（头傀儡）：不存有效数据，统一空链表 / 首节点操作逻辑；

3. 链表类将节点私有化，通过成员函数访问，需要时声明友元（list 类 / 迭代器访问私有节点）。

代码示例：节点与链表基础框架

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 MyList { private: Node<T>* head; //哨兵头 public: MyList(){ head = new Node<T>(T()); } ~MyList(){/*析构释放全部节点*/} };

拓展：友元使用场景

节点成员私有化，迭代器 / 链表需要访问节点私有成员，将对应类声明为节点友元。

四、双向链表核心接口（增、删）

1. 指定位置插入

概念：在 pos 迭代对应节点前插入新节点

特性

插入固定三步：

1. 新节点前驱 = 原前驱节点；

2. 新节点后继 = 原目标节点；

3. 原前驱 next 指向新节点、原目标 prev 指向新节点。

顺序不能乱，防止断链。

//伪代码示意 Node<T>* newNode = new Node(val); newNode->prev = pos->prev; newNode->next = pos; pos->prev->next = newNode; pos->prev = newNode;

2. 指定位置删除

概念：摘除目标节点，前后节点互相链接，delete 释放内存

特性

1. 先让被删节点的前驱 ->next = 被删后继；

2. 被删后继 ->prev = 被删前驱；

3. delete 释放当前节点，杜绝内存泄漏。

Node<T>* del = pos; del->prev->next = del->next; del->next->prev = del->prev; delete del;

五、双向链表经典算法

5.1 链表反转

概念

改变双向链表所有节点的prev（前驱）、next（后继）指针指向，颠倒节点顺序，原首节点变为尾节点，原尾节点变为首节点；仅修改指针，不改动节点内部数据。

特性

1. 核心逻辑：遍历链表，逐个交换当前节点的前驱、后继指针；

2. 哨兵头结点保持不变，仅反转有效数据节点；

3. 时间复杂度 (O(n))，仅需一次完整遍历；

4. 相比单链表，双向链表反转逻辑更直观，可借助前驱指针回溯。

代码示例（基于模板双向链表）

template<typename T> void MyList<T>::reverse() { if (head->next == nullptr) // 空链表，无需反转 return; ​ Node<T>* cur = head->next; Node<T>* 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 链表排序

概念

对双向链表的有效节点进行排序，优先交换节点指针指向，而非交换节点内部数据；区别于数组直接交换元素值的实现方式。

特性

1. 核心原因：若节点存储大型自定义对象，拷贝 / 交换数据开销极大，修改指针仅操作地址，效率更高；

2. 常用算法：冒泡排序（适配链表结构，实现简单）；

3. 排序过程中需同步维护每个节点的prev和next指针，防止断链；

4. 哨兵头结点位置始终固定，不参与排序。

代码示例（双向链表冒泡排序）

template<typename T> void MyList<T>::sort() { if (head->next == nullptr || head->next->next == nullptr) return; // 空链表/单个节点，无需排序 ​ Node<T>* p; // 外层控制排序轮数 for (p = head->next; p->next != nullptr; p = p->next) { Node<T>* q = head->next; // 内层相邻节点比较，交换指针 while (q->next != nullptr) { if (q->data > q->next->data) { // 交换两个相邻节点（仅修改指针，不交换数据） Node<T>* left = q; Node<T>* 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 删除重复节点

概念

遍历有序双向链表，查找数值重复的节点，摘除重复节点并释放堆内存，最终保留唯一值节点，保证链表无重复元素。

特性

1. 前提：一般针对有序链表（无序链表去重效率极低）；

2. 操作步骤：定位重复节点 → 修改前后节点指针完成摘除 →delete释放节点，防止内存泄漏；

3. 遍历过程中指针需谨慎移动，避免节点丢失。

代码示例

template<typename T> void MyList<T>::eraseRepeat() { if (head->next == nullptr) return; Node<T>* cur = head->next; while (cur->next != nullptr) { // 当前节点与下一个节点值重复 if (cur->data == cur->next->data) { Node<T>* delNode = cur->next; // 摘除重复节点 cur->next = delNode->next; if (delNode->next != nullptr) delNode->next->prev = cur; // 释放内存 delete delNode; } else { cur = cur->next; } } }

拓展

无序链表去重通常需要额外容器辅助记录已存在的值，时间、空间开销会增加。

5.4 两个有序链表合并

概念

将两条同排序规则的有序双向链表，合并为一条新的有序双向链表；全程仅修改节点指针指向，不新建节点、不拷贝数据。

特性

1. 要求：两个原链表排序规则一致（同为升序 / 同为降序）；

2. 核心逻辑：依次比较两条链表当前节点值，选取较小节点接入新链表；

3. 合并完成后，原链表失效，所有节点归属新链表；

4. 时间复杂度 (O(m+n))（m、n 为两条链表节点总数）。

代码示例（合并两个升序双向链表）

template<typename T> // 传入两个有序链表，返回合并后的新链表头 Node<T>* mergeList(Node<T>* h1, Node<T>* h2) { Node<T>* newHead = new Node<T>(); // 新哨兵头结点 Node<T>* tail = newHead; Node<T>* p1 = h1->next; Node<T>* 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; }

拓展

合并后建议手动释放原链表的哨兵头结点，避免内存冗余。

六、构造函数与析构函数（双向链表专属）

概念

构造函数：创建链表对象时自动执行，完成哨兵头结点初始化；

析构函数：链表对象生命周期结束时自动执行，逐个释放所有节点内存，彻底杜绝内存泄漏。

特性

1. 构造函数

   链表初始化时，仅创建哨兵头结点，其prev、next默认置为nullptr；

   无需创建有效数据节点，保证空链表结构合法。

2. 析构函数

   遍历所有有效数据节点，逐个delete释放；

   最后释放哨兵头结点，遵循「先释数据节点，再释头结点」顺序；

   析构函数无参数、无返回值，不能重载。

代码示例

template<typename T> // 构造函数：初始化哨兵头结点 MyList<T>::MyList() { head = new Node<T>(); head->prev = nullptr; head->next = nullptr; } template<typename T> // 析构函数：释放全部节点 MyList<T>::~MyList() { Node<T>* p = head->next; // 释放所有有效节点 while (p != nullptr) { Node<T>* temp = p; p = p->next; delete temp; } // 最后释放哨兵头结点 delete head; head = nullptr; }

拓展

1. 若不自定义析构，编译器默认析构不会释放堆上节点，必然造成内存泄漏；

2. 可结合拷贝构造、赋值重载，实现链表深拷贝，防止浅拷贝导致的重复释放问题。

七、模板在链表中的应用

概念

使用 C++类模板封装双向链表节点与链表整体，脱离固定数据类型限制，一套代码可适配整型、浮点型、字符串、自定义结构体 / 类等任意数据类型。

特性

1. 语法规则：以template<class T>或template<typename T>作为模板声明，T为通用类型占位符；

2. 作用域：模板声明作用于后续整个类 / 成员函数，类外实现成员函数时，必须重复书写模板头；

3. 实例化：使用时显式指定具体类型（如MyList<int>、MyList<string>），编译器自动生成对应类型代码；

4. 兼容性：模板代码建议写在同一头文件（分离编译会导致链接报错）。

代码示例（完整模板框架）

#include <iostream> using namespace std; // 模板声明 T：通用数据类型 template<class T> // 模板节点类 struct Node { T data; Node<T>* prev; Node<T>* next; Node(const T& val) : data(val), prev(nullptr), next(nullptr) {} }; // 模板链表类 template<class T> class MyList { private: Node<T>* head; // 哨兵头结点 public: MyList(); // 构造 ~MyList(); // 析构 void pushBack(const T& val); // 尾插 void reverse(); // 反转 void sort(); // 排序 void eraseRepeat();// 去重 };

相似概念对比

普通链表：固定数据类型，多类型需求需重复编写多套代码；

模板链表：泛型设计，代码复用性极强，是 STL 容器的核心实现思想。

拓展

1. 模板支持多类型参数template<class T1, class T2>；

2. 可对特定类型做模板特化，定制特殊逻辑；

3. 模板不支持运行期类型推导，必须在编译期确定具体类型。