list基本概念
**功能：**将数据进行链式存储
链表 (list) 是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针连接实现的
链表的组成：链表由一系列结点组成
结点的组成：一个是存储数据的数据域，另一个是存储下一个结点地址的指针域
STL中的链表是一个双向循环链表
NOTE每一个结点既记录了下一个结点又记录上一个结点 — 双向链表
只记录下一个 — 单向链表
第一个结点的prev记录最后一个结点的地址，最后一个的next记录第一个结点的地址 — 循环
优点：
- 可以对任意位置快速插入或删除元素
- 采用动态存储分配，不会造成内存浪费和溢出
缺点
-
容器遍历速度，没有数组（vector,std::array等）快
-
占用空间比数组大
-
链表灵活，但是空间（指针域）和时间（遍历）额外耗费较大
CAUTION本图未体现出循环，循环需将本图的null去掉，并将左侧第一个prev指向右侧第一个，右侧next同理
由于链表的存储方式不是连续的空间，因此链表迭代器只支持前移和后移，称为双向迭代器
List有一个重要性质，插入和删除操作都不会造成原有迭代器失效，这在vector上不成立（因为vector每次修改数组大小都是开辟新的区域，迭代器得重新生成指向新区域）
总结
STL中list和vector是2个最常用容器，各有优缺点
list构造函数
功能描述：
创建list容器
函数原型
list<T> l; //list采用模板类实现，默认构造list(beg,end); //将区间[beg,end)的元素拷贝赋值给本身list(n,elem); //构造函数将n个elem拷贝给本身list(const list &l); //拷贝构造list赋值与交换
功能描述：
- 给list赋值，以及交换list容器
函数原型：
assign(beg,end); //将[beg,end)区间的数据拷贝赋值给本身assign(n,elem);//将n个elem拷贝赋值给本身list& operator=(const list &lst); //重载=swap(lst); //将lst与本身元素交换list大小操作
功能描述：
- 对list容器的大小进行操作
函数原型：
size(); //返回个数resize(num); //重新指定容器长度为num，若容器变长，则用默认值填充新元素； //若变短，删除超出元素resize(num,elem); //与上类似，但默认值换为elemempty();//判断是否为空list插入和删除
功能描述：
- 对list容器进行数据的插入和删除
函数原型：
push_back(elem); //尾插一个元素pop_back(); //尾删push_front(elem); //前插pop_front(); //前删
insert(pos,elem); //在pos插入一个elem，返回新数据位置insert(pos,n,elem); //在pos插入n个eleminsert(pos,beg,end); //在pos插入[beg,end)区间的元素
clear();//清除所有元素
erase(pos); //清除pos位置的元素，返回下一个元素的位置erase(beg,end); //清除[beg,end)区间的数据，返回下一个元素的位置
remove(elem); //清除容器中所有与elem匹配的元素CAUTION由于list是链表不是数组，不可用index访问，得用迭代器当作pos
list数据存取
功能描述：
- 对list容器中数据进行存取
函数原型：
front(); //返回第一个元素back(); //返回最后一个元素CAUTIONlist不支持at,[idx]的方式返回元素 链表存储方式不是连续空间，迭代器不支持随机访问，只能++ —（前移后移）
list的反转和排序
功能描述
- 将容器中的元素反转，以及将元素排序
函数原型
reverse(); //反转链表sort(); //排序链表sort(function()); //function可以在外面自定义一个，也可以用lambda，可以实现自定义排序规则NOTE此处的sort()是list成员方法，不是algorithm内的sort()，algorithm的sort不支持双向迭代器的排序
Video
If this article helped you, please share it with others!
Some information may be outdated