C++基础笔记（三）链表list
一、数据结构说明
- list
std::list是一种双向链表（doubly linked list），其底层数据结构是互不连续的节点。- 刷题要点：
- 在任何位置进行元素的插入和删除都非常高效，时间复杂度为 O(1)。
- 不支持随机访问（如
list[i]），只能通过迭代器顺序访问，访问第 N 个元素时间复杂度为 O(N)。 - 在需要频繁在序列中间进行增删操作，且不需要随机访问的场景下，
list比vector或deque更具优势。
- 刷题要点：
二、常见使用方法
std::list核心使用
#include <list> #include <algorithm> // 部分操作可能需要，但list有自带的sort // 常见构造 std::list<int> l; // 空 list std::list<int> l3 = {1,2,3,4}; // 列表初始化 // 查看属性 l.size(); // 元素个数，O(N) (可能，视具体实现) l.empty(); // 是否为空，O(1) // 注意：list 没有 capacity() 接口，因为是链表结构，按需分配。 // 改变大小 l.resize(n); // 改变 size：变大时填充默认值，变小时移除多余元素。 l.clear(); // 清空所有元素。 // 元素增删改查 l.push_back(x); // 尾部添加，O(1) l.pop_back(); // 删除尾部元素，O(1) l.push_front(x); // 头部添加，O(1) l.pop_front(); // 头部删除，O(1) l.insert(it, x); // 在迭代器 it 位置插入，O(1) l.erase(it); // 擦除 it（返回下一个元素迭代器），O(1) // 遍历 // list 不支持随机访问，只能用迭代器或范围for循环 for (const auto &x : l) { /* ... */ } for (auto it = l.begin(); it != l.end(); ++it) { /* ... */ }std::list特殊操作
// 排序 l.sort(); // 默认升序，list自带的排序方法，O(N log N) l.sort(std::greater<int>()); // 降序 // 合并与拼接 l.merge(other_list); // 将 other_list 合并到当前 list (要求两者都已排序)，other_list 变空。 l.splice(it, other_list); // 将 other_list 的所有元素移动到当前 list 的 it 位置，other_list 变空。 // 移除 l.remove(value); // 移除所有值为 value 的元素。 l.remove_if(predicate); // 移除所有满足 predicate 条件的元素。 l.unique(); // 移除连续重复的元素（list 必须已排序）。 l.reverse(); // 反转 list。三、底层实现
- list
std::list的底层是一个双向循环链表。每个节点包含数据、指向前一个节点的指针和指向后一个节点的指针。通常会有一个“哨兵节点”（伪头节点）来简化边界处理。- 插入和删除：仅需修改少量指针，时间复杂度为 O(1)。
- 随机访问：不支持 O(1)，需 O(N) 遍历。
- 内存开销：每个节点额外的指针存储导致内存占用高于
std::vector。 - 迭代器稳定性：插入和删除元素时，除了被删除元素的迭代器，其他迭代器保持有效。
四、注意事项
- 选择依据：
std::list最适用于需要频繁在序列中间进行插入和删除，但不要求随机访问的场景。如果涉及大量随机访问或内存连续性有要求，应优先考虑std::vector或std::deque。 - 排序：由于不支持随机访问迭代器，
std::list不能使用std::sort，而必须使用其自带的sort()成员函数。 - 内存和性能：尽管插入删除快，但由于内存不连续，
list的遍历可能比vector慢，且每个元素占用更多内存。 - 迭代器失效：
list的迭代器在插入和删除操作时相对稳定，但为了代码清晰和避免潜在问题，建议在操作后更新相关迭代器。 - 使用场景：需要频繁在数据结构中进行
插入，删除或者合并操作，同时不需要排序或者在插入的时候已经有序。又或者是不确定数据的大小或者内存碎片较多的场景（这种刷题的时候不考虑内存问题，大部分都是时间不够），例如基数排序中的每个桶中的元素（不过一般vector也能实现而且效果更好就是了）。