一、什么是链表？
链表（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>
using namespace std;
< T>
{
:
T data;
SingleListNode<T>* next;
(T val) : (val), () {}
};
< T>
{
:
SingleListNode<T>* head;
length;
:
() : (), () {}
~() {
SingleListNode<T>* current = head;
(current != ) {
SingleListNode<T>* temp = current;
current = current->next;
temp;
}
head = ;
length = ;
}
{
length == ;
}
{
length;
}
{
SingleListNode<T>* newNode = <T>(val);
newNode->next = head;
head = newNode;
length++;
}
{
SingleListNode<T>* newNode = <T>(val);
(()) {
head = newNode;
} {
SingleListNode<T>* current = head;
(current->next != ) {
current = current->next;
}
current->next = newNode;
}
length++;
}
{
(pos < || pos > length) {
cout << << endl;
;
}
(pos == ) {
(val);
;
}
SingleListNode<T>* current = head;
( i = ; i < pos; i++) {
current = current->next;
}
SingleListNode<T>* newNode = <T>(val);
newNode->next = current->next;
current->next = newNode;
length++;
;
}
{
(()) {
cout << << endl;
;
}
SingleListNode<T>* temp = head;
head = head->next;
temp;
length--;
;
}
{
(()) {
cout << << endl;
;
}
(length == ) {
head;
head = ;
} {
SingleListNode<T>* current = head;
(current->next->next != ) {
current = current->next;
}
current->next;
current->next = ;
}
length--;
;
}
{
(()) {
cout << << endl;
;
}
(head->data == val) {
();
}
SingleListNode<T>* current = head;
(current->next != && current->next->data != val) {
current = current->next;
}
(current->next == ) {
cout << << val << << endl;
;
}
SingleListNode<T>* temp = current->next;
current->next = temp->next;
temp;
length--;
;
}
{
SingleListNode<T>* current = head;
(current != ) {
(current->data == val) {
;
}
current = current->next;
}
;
}
{
(()) {
cout << << endl;
;
}
cout << ;
SingleListNode<T>* current = head;
(current != ) {
cout << current->data << ;
current = current->next;
}
cout << endl;
}
};
