目录

链表向链表中插入数据从链表中删除数据listlist的构造list迭代器使用list容量操作list增删查改其他操作迭代器失效list实现forward_list

链表

• 链表因其链状的结构，能方便地删除、插入数据，操作次数是。但也因为这样，寻找、读取数据的效率不如数组高，在随机访问数据中的操作次数是。

• 数组可以方便地寻找并读取数据，在随机访问中操作次数是。但删除、插入的操作次数是次。

向链表中插入数据

1. 初始化待插入的数据 node

2. 将 node 的 next 指针指向 p 的下一个结点

3. 将 p 的 next 指针指向 node

1. 初始化待插入的数据 node，判断给定链表 p 是否为空：

2. 若为空，则将 node 的 next 指针和 p 都指向自己；否则，将 node 的 next 指针指向 p 的下一个结点；

3. 将 p的next指针指向 node

1. 初始化待插入的数据 node；判断给定链表 p 是否为空；

2. 若为空，则将 node 的 left 和 right 指针，以及 p 都指向自己；否则，将 node 的 left 指针指向 p;

3. 将 node 的 right 指针指向 p 的右结点；

4. 将 p 右结点的 left 指针指向 node；

5. 将 p 的 right 指针指向 node。

从链表中删除数据

1. 将 p 下一个结点的值赋给 p，以抹掉 p->value；

2. 新建一个临时结点 t 存放 p->next 的地址；

3. 将 p 的 next 指针指向 p 的下下个结点，以抹掉 p->next；

4. 删除 t。此时虽然原结点 p 的地址还在使用，删除的是原结点 p->next 的地址，但 p 的数据被 p->next 覆盖，p 名存实亡。

1. 将 p 左结点的右指针指向 p 的右节点；

2. 将 p 右结点的左指针指向 p 的左节点；

3. 新建一个临时结点 t 存放 p 的地址；

4. 将 p 的右节点地址赋给 p，以避免 p 变成悬垂指针；

5. 删除 t。

list

std::list

Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions. List containers are implemented as doubly-linked lists; Doubly linked lists can store each of the elements they contain in different and unrelated storage locations.

https://cplusplus.com/reference/list/list/

1. 不适用连续的内存空间，这样可以随意地进行动态操作

2. 可以在内部任意位置快速地插入或删除，

3. 不能进行内部的随机访问，即不支持 []操作符。如果要访问list中的第 6 个元素，必须从已知的位置（比如头部或者尾部）迭代到该位置，在这段位置上迭代需要线性的时间开销。不仅如此，list还需要一些额外的空间，以保存每个结点的 "相关联信息"。

list的构造

• list()：创建一个空list

• list(int nSize)：创建一个vector，元素个数为nSize

• list(int nSize,const t& t)：创建一个list，元素个数为nSize，且值均为t

• list(const vector&)：复制构造函数

• list(begin,end)：复制[begin,end)区间内元素到list中

list迭代器使用

• iterator ：正向迭代器

• reverse_iterator：反向迭代器

• const_iterator：常量迭代器

• const_reverse_iterator：常量反向迭代器

• begin()返回指向容器中第一个元素的迭代器
end()返回指向容器最后一个元素所在位置后一个位置的迭代器

• cbegin()：在begin()基础上，增加了const属性，不能用于修改元素
cend()：在end()基础上，增加const属性，不能用于修改元素

• rbegin()：反向，返回指向最后一个元素的迭代器
rend() ：反向，返回指向第一个元素所在位置前一个位置的迭代器

• crbegin() ：在rbegin()基础上，增加了const属性，不能用于修改元素
crend() ：在rend()基础上，增加了const属性，不能用于修改元素

list容量操作

list增删查改

其他操作

迭代器失效

list实现

forward_list

std::forward_list

template > class forward_list; Forward lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence. Forward lists are implemented as singly-linked lists; Singly linked lists can store each of the elements they contain in different and unrelated storage locations.

https://cplusplus.com/reference/forward_list/forward_list/