介绍

链表是一种用于存储数据的数据结构，通过如链条一般的指针来连接元素。它的特点是插入与删除数据十分方便，但寻找与读取数据的表现欠佳。

优点

链表的优点还是非常明显的：

  1. 它可以迅速地在任何节点进行插入和删除操作，因为 list 的每个节点保存着它在链表中的位置，插入或删除个元素仅对最多三个元素有所影响。

缺点

  1. list 随机检索的性能非常的不好，因为它不像vector那样直接找到元素的地址，而是要从头一个一个的顺序查找。
  2. list 支持双向迭代器，没有下标，必须使用迭代器遍历list。（由于不支持随机迭代器，不能写迭代器 +x，迭代器 -x，不能用 sort 函数，但 list 拥有 sort 成员函数）。

STL 链表

个人认为 STL链表 非常适合使用，就比如你喜欢使用 string 而不是 char[] 。但是它一部分功能实际上并没有手写链表好用，比如需要 STL迭代器 遍历等等。

成员函数描述

常用成员函数
函数名 函数说明
push_back(元素) 往链表尾部添加元素
push_front(元素) 往链表头部添加元素
pop_back(元素) 链表尾部移除元素
pop_front(元素) 链表头部移除元素
insert() 在指定位置插入一个或多个元素
begin() 获取链表的起始地址
end() 获取链表的结束地址
size() 返回链表的结束地址
erase(开始地址,结束地址) 删除链表中置顶范围之间的元素
remove(值val) 删除和 val 相等的元素
sort(链表对象) 链表元素排序
clear() 清空链表
empty() 判断链表是否为空
reverse(开始地址,结束地址) 翻转链表所有值
swap() 交换两个 list
max_size() 获取链表支持的最大容量
全部成员函数
由 必应AI 为我们整理的全部成员函数以及其解释

根据网络搜索结果¹²³⁴，C++ stl list的所有成员函数及其解释如下表所示：

成员函数 解释
构造函数 用于创建list对象，可以指定元素个数、值、迭代器范围或初始化列表
begin() 返回指向list第一个元素的迭代器
end() 返回指向list最后一个元素之后的迭代器
rbegin() 返回指向list最后一个元素的反向迭代器
rend() 返回指向list第一个元素之前的反向迭代器
cbegin() 返回指向list第一个元素的常量迭代器
cend() 返回指向list最后一个元素之后的常量迭代器
crbegin() 返回指向list最后一个元素的常量反向迭代器
crend() 返回指向list第一个元素之前的常量反向迭代器
size() 返回list中的元素个数
max_size() 返回list能容纳的最大元素个数
resize() 改变list的大小，如果需要，添加或删除元素
empty() 判断list是否为空
front() 返回list第一个元素的引用
back() 返回list最后一个元素的引用
assign() 用指定的值、迭代器范围或初始化列表替换list中的元素
push_front() 在list的开头插入一个元素
pop_front() 删除list的第一个元素
push_back() 在list的末尾插入一个元素
pop_back() 删除list的最后一个元素
insert() 在list的指定位置插入一个或多个元素
erase() 删除list的指定位置或范围的元素
swap() 交换两个list的内容
clear() 删除list中的所有元素
emplace() 在list的指定位置构造一个元素
emplace_front() 在list的开头构造一个元素
emplace_back() 在list的末尾构造一个元素
splice() 将另一个list或其子序列移动到list的指定位置
remove() 删除list中等于指定值的所有元素
remove_if() 删除list中满足指定条件的所有元素
unique() 删除list中相邻的重复元素
merge() 将另一个list合并到list中，保持元素的排序
sort() 对list中的元素进行排序
reverse() 反转list中的元素的顺序

源: 与必应的对话， 2023/2/16(1) C++ List | Top 6 Functions of List in C++ You Should Learn - EDUCBA. https://www.educba.com/c-plus-plus-list/#:~:text=Functions of the List in C%2B%2B 1 1.,5 5. Modifiers ... 6 6. Operations 访问时间 2023/2/16.
(2) std::list - cppreference.com. https://en.cppreference.com/w/cpp/container/list 访问时间 2023/2/16.
(3) list - C++ Reference - cplusplus.com. https://cplusplus.com/reference/list/list/ 访问时间 2023/2/16.
(4) List in C++ Standard Template Library (STL) - GeeksforGeeks. https://www.geeksforgeeks.org/list-cpp-stl/ 访问时间 2023/2/16.

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 引入头文件
#include <iostream>
#include <list>
using namespace std;

int main()
{
	// 创建一个链表对象
	list<int> myList;

	// 在链表尾部插入元素
	myList.push_back(10);
	myList.push_back(20);
	myList.push_back(30);

	// 在链表头部插入元素
	myList.push_front(5);
	myList.push_front(4);
	myList.push_front(3);

	// 输出链表的大小
	cout << "链表的大小是: " << myList.size() << endl;

	// 遍历链表并输出元素
	cout << "链表的元素是: " << endl;
	for (auto it = myList.begin(); it != myList.end(); it++)
		cout << *it << " ";
	cout << endl;

	// 删除链表中的某个元素
	myList.remove(20);

	// 输出删除后的链表元素
	cout << "删除20后的链表元素是: " << endl;
	for (auto it = myList.begin(); it != myList.end(); it++)
		cout << *it << " ";
	cout << endl;

	// 清空链表
	myList.clear();

	// 输出清空后的链表大小
	cout << "清空后的链表大小是: " << myList.size() << endl;

	return 0;
}

编译结果：

1
2
3
4
5
6
链表的大小是: 6
链表的元素是:
3 4 5 10 20 30
删除20后的链表元素是:
3 4 5 10 30
清空后的链表大小是: 0

不错，其实 STL 链表非常容易运用，只需使用成员函数即可。接下来就让我详细地讲解一下手写函数把~