list是个双向带头循环链表。
带头双向循环链表我们在数据结构与算法专栏中有过详细的讲解，并且还带大家实现过：
数据结构与算法⑦(第二章收尾)带头双向循环链表的实现_GR C的博客-CSDN博客
我们知道，带头双向循环链表是非常合适任意位置的插入和删除的，时间复杂度都是O（1）.
list 在实际的运用中用的没有 vector 多，包括大家在刷题的时候 list 也出现的很少，
因为 list 不支持随机访问，有很多数据堆在那里你可能还需要排序一下，list 要排序，
效率就慢一点，所以用 vector 的情况较多。
但 list 在一些场景也需用到，比如需要频繁的插入和删除，特别是需要在头尾部插入和删除。
1. list 介绍和简单使用
1.1 list介绍
像前面一样查查文档：https://cplusplus.com/reference/list/list/?kw=list
① list 是一个顺序容器：
是允许你在任意位置进行 插入删除的顺序容器，并提供双向迭代器。
② list的底层是双向链表结构：
双向链表中每个元素存储在互不相关的独立结点中，在结点中通过两个指针指向其前后元素。
③ list 与 forward_list 非常相似：
它们很相似，最大的不同 forward_list 是单链表，只能向前迭代（也让其因此更简单高效）。
④ 与其他的序列式容器相比（array，vector，deque）：
list 通常在任意位置进行插入、移除元素的执行效率更好。
list 和 forward_list 最大的缺陷是不支持任意位置的随机访问。举个例子：
如果要访问 list 中的第 6 个元素，必须从已知的位置（比如头部或者尾部）迭代到该位置，
在这段位置上迭代需要线性的时间开销。不仅如此，list 还需要一些额外的空间，
以保存每个结点的 "相关联信息"（对于存储类型较小元素的大 list 来说这 可能是一个重要的因素）
1.2 list简单接口函数
看看构造：
和vector差不多，看看其它接口函数：
看不懂英文又不想查的朋友看这里：
还是和vector差不多，还有一些特有的接口没截，等下着重讲讲。简单用下上面吧：
1.3 push_back 和遍历
首先思考一个问题：我们还能用 "下标 + 方框号" 的方式遍历吗？
不行的，因为 list 是链表，是通过指针连接的， 所以 list 不支持随机访问！
而 string 和 vector 可以，是因为它底层的结构是连续的数组，它的物理结构是连续的。
void Test_push_back() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); list<int>::iterator it = lt.begin();// 迭代器遍历1到5 while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; for (auto& e : lt)// 范围for 把1到5乘2 { e *= 2; cout << e << " "; } cout << endl; list<int>::reverse_iterator rit = lt.rbegin();//反向迭代器倒着遍历 while (rit != lt.rend()) { cout << *rit << " "; rit++; } cout << endl; }
1.4 list常规接口函数使用
void Test_other() { list<int> lt; lt.push_front(10);//头插四个 lt.push_front(20); lt.push_front(30); lt.push_front(40); list<int>::iterator it = find(lt.begin(), lt.end(), 20);//在20前面插入50 if (it != lt.end()) { lt.insert(it, 50); } for (const auto& e : lt) { cout << e << " "; } cout << "size = " << lt.size() << endl; lt.pop_back();//尾删 lt.pop_front();//头删 it = find(lt.begin(), lt.end(), 20);//删除20 if (it != lt.end()) { lt.erase(it); } for (const auto& e : lt) { cout << e << " "; } cout << "size = " << lt.size() << endl; }
2. list 的其它接口函数
因为list的存储不是连续的，库里的一些函数用不了（比如sort和reverse），
所以list提供了一些接口函数：
2.1 splice 接合
简单来说就是把一个链表转移到另一个链表里去：
void Test_splice() { list<int> lt1; lt1.push_back(1); lt1.push_back(2); lt1.push_back(3); lt1.push_back(4); lt1.push_back(5); list<int> lt2; lt2.push_back(10); lt2.push_back(20); lt2.push_back(30); lt2.push_back(40); lt2.push_back(50); lt1.splice(lt1.end(), lt2);//把lt2接合到lt1后面 for (const auto& e : lt1)// 范围for遍历 { cout << e << " "; } cout << endl; }
2.2 remove 删完一个值
remove 只需要给一个元素的值，它就可以自己找自己删！
erase 还需要搞个搞个迭代器，然后还要 if 判断一下，但 remove 就不一样了：
void Test_remove() { list<int> lt; lt.push_back(10); lt.push_back(20); lt.push_back(30); lt.push_back(40); lt.push_back(10); lt.push_back(20); lt.push_back(30); lt.push_back(40); for (const auto& e : lt) { cout << e << " "; } cout << endl; // 如果存在元素，删完 lt.remove(10); for (const auto& e : lt) { cout << e << " "; } cout << endl; // 如果待删元素不存在,则无事发生 lt.remove(50); for (const auto& e : lt) { cout << e << " "; } cout << endl; }
2.3 sort和reverse
unique是去重，但是再后面点学的set天生带去重，所以其它接口后面有机会再讲行了。
前面说到：因为list的存储不是连续的，库里的一些函数用不了（比如sort和reverse）。
但是list提供的作用和其差不多，值得注意的是库里的sort底层是快排，快排，链表是用不了的，
那list用上面排序呢？冒泡等是可以的，就是效率太低，这时归并排序就派上用场了，
而且不会多开空间。但是排序大量数据时list的排序就比快排慢了，甚至你拷贝list的数据到vector
用库里的快排，排完再拷回list的时间还要比list自己排得快，但是数据量小的话也差不多：
void Test_sort_reverse() { list<int> lt; lt.push_back(1); lt.push_back(20); lt.push_back(2); lt.push_back(40); lt.push_back(5); lt.push_back(10); lt.push_back(30); lt.push_back(4); lt.push_back(4); lt.push_back(50); for (const auto& e : lt) { cout << e << " "; } cout << endl; lt.sort(); for (const auto& e : lt) { cout << e << " "; } cout << endl; lt.reverse();// 懂我意思把 for (const auto& e : lt) { cout << e << " "; } cout << endl; }
本章完。
list没有很好的OJ题，且一些选择题打算放在下一篇了，模拟实现之后再写好一点。
