链表详解及C++实现
一、什么是链表？
链表（Linked List）是一种线性数据结构，它通过指针将一组离散的内存节点串联起来，形成有序的序列。与数组的连续内存存储不同，链表的节点在内存中可以不连续，节点间的逻辑关系完全依靠指针维系。这种特性让链表在插入、删除操作上具有天然优势，无需像数组那样移动大量元素。
1.1 链表的核心组成
链表的基本单位是节点（Node），每个节点通常包含两部分：
- 数据域：存储节点的数据（如int、float、自定义类型等）；
- 指针域：存储下一个（或上一个）节点的内存地址，通过指针实现节点间的关联。
1.2 常见链表类型
- 单链表：每个节点仅包含一个指针域，指向下一个节点，尾节点指针域为nullptr（空指针），只能从表头遍历到表尾；
- 双向链表：每个节点包含两个指针域，分别指向前一个节点和后一个节点，可双向遍历，插入/删除时需维护两个指针；
- 循环链表：尾节点的指针域不指向nullptr，而是指向表头节点（单循环链表）或表头的前驱节点（双循环链表），可实现首尾相连的遍历。
1.3 链表与数组的对比
| 特性 | 链表（指针实现） | 数组 |
|---|---|---|
| 内存存储 | 离散存储，节点间通过指针关联 | 连续存储，元素地址连续 |
| 访问效率 | O(n)，需从表头遍历查找元素 | O(1)，支持随机访问（通过下标） |
| 插入/删除效率 | O(1)（已知插入/删除位置时），仅需修改指针 | O(n)，需移动插入/删除位置后的所有元素 |
| 空间灵活性 | 动态扩容，无需预先分配固定空间 | 静态扩容（或动态数组的拷贝扩容），空间利用率可能较低 |
二、指针链表的C++实现核心思路
C++中实现链表的核心是自定义节点结构体/类和指针操作。以最常用的单链表和双向链表为例，核心思路如下：
2.1 节点定义
使用模板类定义节点，确保链表可适配多种数据类型。单链表节点包含数据域和一个后继指针；双向链表节点额外增加一个前驱指针。
2.2 链表类设计
封装链表的核心操作，对外提供简洁的接口，隐藏指针操作的细节。核心操作包括：
- 初始化（创建空链表）；
- 节点插入（表头、表尾、指定位置）；
- 节点删除（表头、表尾、指定值/位置）；
- 链表遍历（正向、反向，双向链表支持）；
- 元素查找；
- 获取链表长度、判断是否为空；
- 销毁链表（释放内存，避免内存泄漏）。
三、完整C++实现代码
3.1 单链表实现
单链表是最基础的链表类型，仅支持正向遍历，插入/删除操作只需维护后继指针。
#include<iostream>usingnamespace std;// 单链表节点模板类template<typenameT>classSingleListNode{public: T data;// 数据域 SingleListNode<T>* next;// 后继指针（指向 next 节点）// 构造函数SingleListNode(T val):data(val),next(nullptr){}};// 单链表类（指针实现）template<typenameT>classSingleLinkedList{private: SingleListNode<T>* head;// 头指针（指向链表第一个节点）int length;// 链表长度（避免每次遍历统计）public:// 构造函数：初始化空链表SingleLinkedList():head(nullptr),length(0){}// 析构函数：销毁链表，释放所有节点内存~SingleLinkedList(){ SingleListNode<T>* current = head;while(current !=nullptr){ SingleListNode<T>* temp = current;// 保存当前节点 current = current->next;// 移动到下一个节点delete temp;// 释放当前节点内存} head =nullptr;// 头指针置空 length =0;}// 1. 判空：判断链表是否为空boolisEmpty()const{return length ==0;}// 2. 获取链表长度intgetLength()const{return length;}// 3. 表头插入节点voidinsertAtHead(T val){// 创建新节点 SingleListNode<T>* newNode =newSingleListNode<T>(val);// 新节点的 next 指向原头节点 newNode->next = head;// 头指针指向新节点（新节点成为新表头） head = newNode; length++;// 长度+1}// 4. 表尾插入节点voidinsertAtTail(T val){ SingleListNode<T>* newNode =newSingleListNode<T>(val);// 空链表特殊处理：新节点直接作为头节点if(isEmpty()){ head = newNode;}else{// 遍历到尾节点（next 为 nullptr 的节点） SingleListNode<T>* current = head;while(current->next !=nullptr){ current = current->next;}// 尾节点的 next 指向新节点 current->next = newNode;} length++;}// 5. 指定位置插入节点（pos：插入到第 pos 个节点之后，pos 从 1 开始）boolinsertAtPos(int pos, T val){// 位置合法性检查：pos 需在 0 ~ length 之间（pos=0 等价于表头插入）if(pos <0|| pos > length){ cout <<"插入位置非法！"<< endl;returnfalse;}// pos=0 直接调用表头插入if(pos ==0){insertAtHead(val);returntrue;}// 遍历到第 pos 个节点 SingleListNode<T>* current = head;for(int i =1; i < pos; i++){ current = current->next;}// 创建新节点，调整指针 SingleListNode<T>* newNode =newSingleListNode<T>(val); newNode->next = current->next;// 新节点 next 指向原 pos+1 节点 current->next = newNode;// pos 节点 next 指向新节点 length++;returntrue;}// 6. 删除表头节点booldeleteAtHead(){if(isEmpty()){ cout <<"链表为空，无法删除！"<< endl;returnfalse;} SingleListNode<T>* temp = head;// 保存原头节点 head = head->next;// 头指针指向原头节点的 nextdelete temp;// 释放原头节点内存 length--;returntrue;}// 7. 删除表尾节点booldeleteAtTail(){if(isEmpty()){ cout <<"链表为空，无法删除！"<< endl;returnfalse;}// 只有一个节点的情况：直接删除头节点if(length ==1){delete head; head =nullptr;}else{// 遍历到倒数第二个节点（尾节点的前驱） SingleListNode<T>* current = head;while(current->next->next !=nullptr){ current = current->next;}delete current->next;// 释放尾节点 current->next =nullptr;// 倒数第二个节点 next 置空} length--;returntrue;}// 8. 删除指定值的节点（删除第一个匹配值的节点）booldeleteByVal(T val){if(isEmpty()){ cout <<"链表为空，无法删除！"<< endl;returnfalse;}// 头节点就是目标节点的情况if(head->data == val){returndeleteAtHead();}// 遍历查找目标节点的前驱 SingleListNode<T>* current = head;while(current->next !=nullptr&& current->next->data != val){ current = current->next;}// 未找到目标节点if(current->next ==nullptr){ cout <<"未找到值为 "<< val <<" 的节点！"<< endl;returnfalse;}// 删除目标节点 SingleListNode<T>* temp = current->next; current->next = temp->next;// 前驱节点 next 指向目标节点的 nextdelete temp; length--;returntrue;}// 9. 查找指定值的节点（返回是否存在）boolsearch(T val)const{ SingleListNode<T>* current = head;while(current !=nullptr){if(current->data == val){returntrue;// 找到} current = current->next;}returnfalse;// 未找到}// 10. 正向遍历链表并打印voidtraverse()const{if(isEmpty()){ cout <<"链表为空！"<< endl;return;} cout <<"单链表遍历："; SingleListNode<T>* current = head;while(current !=nullptr){ cout << current->data <<" "; current = current->next;} cout << endl;}};3.2 双向链表实现
双向链表支持正向和反向遍历，插入/删除时需同时维护前驱指针和后继指针，灵活性更高。
#include<iostream>usingnamespace std;// 双向链表节点模板类template<typenameT>classDoubleListNode{public: T data;// 数据域 DoubleListNode<T>* prev;// 前驱指针（指向 previous 节点） DoubleListNode<T>* next;// 后继指针（指向 next 节点）// 构造函数DoubleListNode(T val):data(val),prev(nullptr),next(nullptr){}};// 双向链表类（指针实现）template<typenameT>classDoubleLinkedList{private: DoubleListNode<T>* head;// 头指针 DoubleListNode<T>* tail;// 尾指针（直接指向尾节点，优化表尾操作效率）int length;// 链表长度public:// 构造函数：初始化空链表DoubleLinkedList():head(nullptr),tail(nullptr),length(0){}// 析构函数：销毁链表~DoubleLinkedList(){ DoubleListNode<T>* current = head;while(current !=nullptr){ DoubleListNode<T>* temp = current; current = current->next;delete temp;} head = tail =nullptr; length =0;}// 1. 判空boolisEmpty()const{return length ==0;}// 2. 获取长度intgetLength()const{return length;}// 3. 表头插入voidinsertAtHead(T val){ DoubleListNode<T>* newNode =newDoubleListNode<T>(val);if(isEmpty()){// 空链表：头、尾指针都指向新节点 head = newNode; tail = newNode;}else{ newNode->next = head;// 新节点 next 指向原头节点 head->prev = newNode;// 原头节点 prev 指向新节点 head = newNode;// 头指针更新为新节点} length++;}// 4. 表尾插入（利用尾指针，O(1) 效率）voidinsertAtTail(T val){ DoubleListNode<T>* newNode =newDoubleListNode<T>(val);if(isEmpty()){ head = newNode; tail = newNode;}else{ newNode->prev = tail;// 新节点 prev 指向原尾节点 tail->next = newNode;// 原尾节点 next 指向新节点 tail = newNode;// 尾指针更新为新节点} length++;}// 5. 指定位置插入（pos：插入到第 pos 个节点之后，pos 从 1 开始）boolinsertAtPos(int pos, T val){if(pos <0|| pos > length){ cout <<"插入位置非法！"<< endl;returnfalse;}if(pos ==0){insertAtHead(val);returntrue;}if(pos == length){insertAtTail(val);returntrue;}// 遍历到第 pos 个节点（双向链表可优化为从表头或表尾遍历，此处简化为表头遍历） DoubleListNode<T>* current = head;for(int i =1; i < pos; i++){ current = current->next;}// 调整前驱和后继指针 DoubleListNode<T>* newNode =newDoubleListNode<T>(val); newNode->prev = current;// 新节点 prev 指向 pos 节点 newNode->next = current->next;// 新节点 next 指向 pos+1 节点 current->next->prev = newNode;// pos+1 节点 prev 指向新节点 current->next = newNode;// pos 节点 next 指向新节点 length++;returntrue;}// 6. 删除表头booldeleteAtHead(){if(isEmpty()){ cout <<"链表为空，无法删除！"<< endl;returnfalse;} DoubleListNode<T>* temp = head;if(length ==1){// 只有一个节点：头、尾指针都置空 head = tail =nullptr;}else{ head = head->next;// 头指针指向原头节点的 next head->prev =nullptr;// 新头节点 prev 置空}delete temp; length--;returntrue;}// 7. 删除表尾（O(1) 效率）booldeleteAtTail(){if(isEmpty()){ cout <<"链表为空，无法删除！"<< endl;returnfalse;} DoubleListNode<T>* temp = tail;if(length ==1){ head = tail =nullptr;}else{ tail = tail->prev;// 尾指针指向原尾节点的 prev tail->next =nullptr;// 新尾节点 next 置空}delete temp; length--;returntrue;}// 8. 删除指定值的节点booldeleteByVal(T val){if(isEmpty()){ cout <<"链表为空，无法删除！"<< endl;returnfalse;}// 头节点是目标节点if(head->data == val){returndeleteAtHead();}// 尾节点是目标节点if(tail->data == val){returndeleteAtTail();}// 遍历查找目标节点 DoubleListNode<T>* current = head->next;while(current != tail && current->data != val){ current = current->next;}// 未找到if(current == tail && current->data != val){ cout <<"未找到值为 "<< val <<" 的节点！"<< endl;returnfalse;}// 调整指针 current->prev->next = current->next;// 前驱节点 next 指向目标节点的 next current->next->prev = current->prev;// 后继节点 prev 指向目标节点的 prevdelete current; length--;returntrue;}// 9. 查找指定值boolsearch(T val)const{ DoubleListNode<T>* current = head;while(current !=nullptr){if(current->data == val){returntrue;} current = current->next;}returnfalse;}// 10. 正向遍历voidtraverseForward()const{if(isEmpty()){ cout <<"链表为空！"<< endl;return;} cout <<"双向链表正向遍历："; DoubleListNode<T>* current = head;while(current !=nullptr){ cout << current->data <<" "; current = current->next;} cout << endl;}// 11. 反向遍历（双向链表特有）voidtraverseBackward()const{if(isEmpty()){ cout <<"链表为空！"<< endl;return;} cout <<"双向链表反向遍历："; DoubleListNode<T>* current = tail;while(current !=nullptr){ cout << current->data <<" "; current = current->prev;} cout << endl;}};3.3 测试代码（主函数）
intmain(){// -------------------------- 单链表测试 -------------------------- cout <<"===== 单链表测试 ====="<< endl; SingleLinkedList<int> singleList;// 插入测试 singleList.insertAtHead(3); singleList.insertAtHead(1); singleList.insertAtTail(5); singleList.insertAtPos(2,4);// 在第2个节点（值为3）后插入4 singleList.traverse();// 预期：1 3 4 5// 长度和判空测试 cout <<"单链表长度："<< singleList.getLength()<< endl;// 预期：4 cout <<"单链表是否为空："<<(singleList.isEmpty()?"是":"否")<< endl;// 预期：否// 查找测试int searchVal =4; cout <<"是否存在值 "<< searchVal <<"："<<(singleList.search(searchVal)?"是":"否")<< endl;// 预期：是// 删除测试 singleList.deleteByVal(3); singleList.traverse();// 预期：1 4 5 singleList.deleteAtHead(); singleList.traverse();// 预期：4 5 singleList.deleteAtTail(); singleList.traverse();// 预期：4// -------------------------- 双向链表测试 -------------------------- cout <<"\n===== 双向链表测试 ====="<< endl; DoubleLinkedList<int> doubleList;// 插入测试 doubleList.insertAtHead(2); doubleList.insertAtTail(6); doubleList.insertAtPos(1,4);// 在第1个节点（值为2）后插入4 doubleList.traverseForward();// 预期：2 4 6 doubleList.traverseBackward();// 预期：6 4 2// 长度测试 cout <<"双向链表长度："<< doubleList.getLength()<< endl;// 预期：3// 删除测试 doubleList.deleteByVal(4); doubleList.traverseForward();// 预期：2 6 doubleList.deleteAtHead(); doubleList.traverseForward();// 预期：6 doubleList.deleteAtTail(); doubleList.traverseForward();// 预期：链表为空return0;}四、代码说明与核心要点
4.1 指针操作的核心细节
- 空指针处理：链表操作中必须避免对 nullptr 解引用（如访问 current->data 时需确保 current != nullptr），否则会导致程序崩溃；
- 指针指向更新顺序：插入/删除节点时，需先更新新节点或前驱节点的指针，再更新原节点的指针，避免链表“断裂”（如单链表表头插入需先让新节点 next 指向原头节点，再更新 head）；
- 内存释放：删除节点后必须手动释放内存（delete），否则会造成内存泄漏，析构函数中需遍历整个链表释放所有节点。
4.2 模板类的优势
使用模板类 template <typename T> 让链表可适配 int、float、string 等多种数据类型，无需为每种数据类型单独编写链表代码，极大提高了代码复用性。例如，创建存储字符串的链表只需 SingleLinkedList<string> strList;。
4.3 双向链表的优化点
双向链表通过增加尾指针（tail），将表尾插入、表尾删除操作的效率从 O(n) 提升到 O(1)；同时支持反向遍历，适合需要双向访问元素的场景（如LRU缓存淘汰算法）。但相比单链表，双向链表每个节点多一个指针域，占用更多内存，插入/删除操作需维护两个指针，逻辑更复杂。
五、编译与运行
5.1 编译命令
将代码保存为 linked_list.cpp，使用 g++ 编译：
g++ linked_list.cpp -o linked_list 5.2 运行结果
===== 单链表测试 ===== 单链表遍历：1 3 4 5 单链表长度：4 单链表是否为空：否 是否存在值 4：是 单链表遍历：1 4 5 单链表遍历：4 5 单链表遍历：4 ===== 双向链表测试 ===== 双向链表正向遍历：2 4 6 双向链表反向遍历：6 4 2 双向链表长度：3 双向链表正向遍历：2 6 双向链表正向遍历：6 双向链表为空！ 六、常见问题与注意事项
- 链表断裂：指针更新顺序错误会导致链表断裂（如单链表插入时先更新 head 再设置 newNode->next），需牢记“先关联新节点，再断开旧关联”；
- 内存泄漏：忘记 delete 删除的节点，或析构函数未遍历释放所有节点，会导致内存泄漏，长期运行可能导致程序崩溃；
- 边界条件处理：空链表、只有一个节点的链表、插入/删除位置为表头/表尾等边界情况，需单独处理，否则易出现逻辑错误；
- 遍历终止条件：单链表遍历终止条件为
current != nullptr，双向链表反向遍历终止条件为current != nullptr，避免越界访问； - 与STL容器对比：C++ STL 提供了
std::list（双向链表）和std::forward_list（单链表），封装了完整的链表操作，实际开发中可直接使用，但手动实现链表有助于理解指针和数据结构原理。
七、总结
指针链表是C++中指针应用的经典场景，核心在于通过指针串联离散节点，实现高效的插入/删除操作。本文详细讲解了单链表和双向链表的概念、设计思路，并用模板类实现了完整的链表操作，包括插入、删除、遍历、查找等核心功能，同时提供了测试代码和运行结果。
