7. list 双向链表

双向链表（list） 是链式存储的一种数据结构，其内部由双向链表实现。它的特点是在任意位置插入/删除快（O(1)），但不支持随机访问。

双向链表适用于需要频繁在中间插入/删除，且不需要随机访问的场景。

缺点：遍历较慢。

list 模板的定义方法如下:

template<
    class T,
    class Allocator = std::allocator<T>
> class list;

说明:

list 创建的双向链表可以使用统一初始化列表 {...} 进行初始化。如：

std::list<int> vd = {1, 2, 3, 4};

常用的成员函数

成员函数
说明
list
构造函数。
~list
析构函数。
operator=
赋值。
assign
等同于 operator=。
元素访问相关成员函数
front
访问第一个元素
back
访问最后一个元素
容量相关成员函数
empty
判断是否为空
size
返回数据元素个数
max_size
返回可能存储的最大数据元素个数。
修改相关成员函数
clear
清空数据。
insert
插入数据
emplace(C++11)
使用构造对象替换
erase
删除数据
push_back
向后追加单个数据
pop_back
删除尾部单个数据
push_front
在开始位置插入单个数据
pop_front
删除第一个数据
resize
修改数据元素个数量
swap
交换两个容器内容
修改相关成员函数
merge
合并两个有序链表
splice
从另一个链表删除元素
remove/remove_if
删除指定的数据
reserve
反转数组顺序
unique
删除重复数据
sort
排序所有元素
迭代器相关成员函数
begin 或 cbegin(C++11)
返回容器数据开始位置的迭代器
end或cend(C++11)
返回容器数据结束位置的迭代器（最后一个元素的后面）
rbegin或crbegin(C++11)
返回反向迭代器的起始位置（最后一个元素）
rend或 crend(C++11)
返回反向迭代器的结束位置（第一个元素的前一位置）

以上函数只给出了函数名，以上函数大多数都有重载，具体请查看官方文档.

参考文档

https://en.cppreference.com/cpp/container/vector

非成员函数

操作
说明
operator==
比较两个容器是否相同。

示例

// filename: mylist.cpp
#include <iostream>
#include <list>

int main(int argc, char * argv[]) {
    // 创建一个存储整数的链表容器
    std::list<int> l = {7, 5, 16, 8};

    // 在前面插入一个整数。
    l.push_front(25);
    // 在末尾追加一个整数。
    l.push_back(13);

    // 打印链表信息：(C++98 的用法)
    for (std::list<int>::const_iterator it = l.cbegin(); it != l.cend(); it++)
        std::cout << *it << " ";
    std::cout << std::endl;

    l.remove(16);
    // 打印链表信息：(C++11 的用法)
    for (auto it = l.cbegin(); it != l.cend(); it++)
        std::cout << *it << " ";
    std::cout << std::endl;

    return 0;
}

编译和运行结果如下

weimz@mzstudio:~$ g++ -o mylist mylist.cpp
weimz@mzstudio:~$ ./mylist
25 7 5 16 8 13
25 7 5 8 13