list 容器详解

list 是 STL 中的双向链表容器，底层由双向循环链表实现，支持在任意位置高效插入、删除元素，但不支持随机访问，是频繁进行中间操作的最优选择。

一、list 核心特性

1. 双向链表结构：每个节点保存前驱和后继指针，支持双向遍历
2. 高效插入 / 删除：在任意位置插入、删除元素效率均为 O (1)
3. 不支持随机访问：不能使用 [] 或 at() 访问元素，只能通过迭代器遍历
4. 迭代器稳定性：插入、删除元素不会导致原有迭代器失效（仅被删除节点的迭代器失效）
5. 自带头尾操作：支持 push_front、pop_front 等高效头尾操作

二、list 与其他容器核心区别

• vector：支持随机访问，尾部插入高效，中间插入效率低
• deque：支持随机访问，头尾插入高效，中间插入效率一般
• list：不支持随机访问，任意位置插入 / 删除都高效
• queue/stack：受限访问容器，仅支持头尾 / 栈顶操作

三、基础用法

#include <iostream>
#include <list>     // list 头文件
using namespace std;

int main() {
    // 1. 定义 int 类型链表
    list<int> lst;

    // 2. 头尾插入元素
    lst.push_back(10);    // 尾插
    lst.push_back(20);
    lst.push_front(5);    // 头插

    // 3. 遍历链表（只能用迭代器/范围for）
    cout << "遍历结果：";
    for (int num : lst) {
        cout << num << " ";   // 输出：5 10 20
    }
    cout << endl;

    // 4. 访问头尾元素
    cout << "头部元素：" << lst.front() << endl;
    cout << "尾部元素：" << lst.back() << endl;

    // 5. 指定位置插入（迭代器位置）
    auto it = lst.begin();
    it++;                   // 指向第二个元素（10）
    lst.insert(it, 15);     // 在 10 前插入 15

    // 6. 删除元素
    lst.pop_front();        // 删除头部
    lst.pop_back();         // 删除尾部
    lst.erase(lst.begin()); // 删除迭代器指向元素

    // 7. 常用操作
    cout << "链表大小：" << lst.size() << endl;
    cout << "是否为空：" << lst.empty() << endl;

    lst.clear(); // 清空链表
    return 0;
}

四、list 常用操作汇总

操作	语法	说明
头部插入	push_front(元素)	在链表头部插入元素，效率 O(1)
尾部插入	push_back(元素)	在链表尾部插入元素，效率 O(1)
头部删除	pop_front()	删除链表头部元素，效率 O(1)
尾部删除	pop_back()	删除链表尾部元素，效率 O(1)
访问头部	front()	返回链表头部元素（不删除），需确保非空
访问尾部	back()	返回链表尾部元素（不删除），需确保非空
指定位置插入	insert(迭代器, 元素)	在迭代器位置插入元素
指定位置删除	erase(迭代器)	删除迭代器指向的元素
清空链表	clear()	删除所有元素
判空	empty()	链表为空返回 true，否则返回 false
获取大小	size()	返回链表元素个数

五、适用场景总结（一句话选型）

1. 需要频繁在任意位置插入 / 删除元素 → 用 list
2. 对插入 / 删除效率要求极高，不在乎随机访问 → 用 list
3. 需要频繁头尾操作 + 中间操作 → 用 list
4. 需要随机访问元素 → 不要用 list

六、注意事项

1. 不支持随机访问：不能用 [] 访问元素，只能迭代器遍历
2. 迭代器使用：仅支持 ++、--，不支持 +n 跳跃操作
3. 内存不连续：元素内存地址分散，无法像 vector 一样连续存储
4. 空间开销大：每个节点需存储前后指针，内存占用高于 vector
5. 无容量概念：不需要预分配空间，按需动态申请