目录1.list 的基本使用1.1 创建和初始化1.2. 插入元素1.3. 删除元素1.4. 访问元素1.5 遍历1.6 总结list是C标准库STL中的双向链表容器属于list头文件。它的特点是动态大小可以随时插入或删除元素不需要手动管理内存。双向链表每个节点都连接前后两个节点支持双向遍历。高效插入删除插入和删除的时间复杂度是O(1)比vector快vector可能会移动大量元素。随机访问慢不像vector可以直接访问vec[i]list只能顺序遍历O(n)。1.list的基本使用1.1创建和初始化std::listint lst1; // 创建空 list std::listint lst2 {1, 2, 3, 4, 5}; // 用初始化列表创建 std::listint lst3(5, 100); // 创建 5 个元素每个值都为 100 std::listint lst4(lst2); // 拷贝构造1.2. 插入元素lst.push_back(10); // 尾部插入 10 lst.push_front(5); // 头部插入 5 auto it lst.begin(); std::advance(it, 2); // 迭代器前进 2 步 lst.insert(it, 99); // 在第 3 个位置插入 991.3. 删除元素lst.pop_back(); // 删除最后一个元素 lst.pop_front(); // 删除第一个元素 auto it lst.begin(); std::advance(it, 1); lst.erase(it); // 删除第二个元素 lst.remove(3); // 删除所有值为 3 的元素 lst.clear(); // 清空 list1.4. 访问元素std::cout lst.front(); // 访问第一个元素 std::cout lst.back(); // 访问最后一个元素1.5 遍历// 方式 1使用范围 for for (int num : lst) { std::cout num ; } // 方式 2使用迭代器 for (std::listint::iterator it lst.begin(); it ! lst.end(); it) { std::cout *it ; }1.6 总结区别vector动态数组list双向链表底层结构动态数组连续内存双向链表分散存储访问速度随机访问快 (O(1))随机访问慢 (O(n))插入删除尾部操作快 (O(1))中间插入/删除慢 (O(n))任意位置插入/删除快 (O(1))内存使用连续存储节省空间但可能需要扩容每个节点有额外指针开销内存占用较大遍历方式支持 []可用 、- 运算符只能用迭代器 或 --pair这是 C 标准库里的“对组”或“二元组”。它里面可以装两个不同类型的数据。比如pairint, string就是“一个整数 一个字符串”捆绑在一起。list这就是我们刚才聊的链表容器双向链表。合在一起listpairA, B意思就是——这个链表里每一个节点存储的数据不再是一个普通的数字而是一个“小包裹”pair。
目录1.list 的基本使用1.1 创建和初始化1.2. 插入元素1.3. 删除元素1.4. 访问元素1.5 遍历1.6 总结list是C标准库STL中的双向链表容器属于list头文件。它的特点是动态大小可以随时插入或删除元素不需要手动管理内存。双向链表每个节点都连接前后两个节点支持双向遍历。高效插入删除插入和删除的时间复杂度是O(1)比vector快vector可能会移动大量元素。随机访问慢不像vector可以直接访问vec[i]list只能顺序遍历O(n)。1.list的基本使用1.1创建和初始化std::listint lst1; // 创建空 list std::listint lst2 {1, 2, 3, 4, 5}; // 用初始化列表创建 std::listint lst3(5, 100); // 创建 5 个元素每个值都为 100 std::listint lst4(lst2); // 拷贝构造1.2. 插入元素lst.push_back(10); // 尾部插入 10 lst.push_front(5); // 头部插入 5 auto it lst.begin(); std::advance(it, 2); // 迭代器前进 2 步 lst.insert(it, 99); // 在第 3 个位置插入 991.3. 删除元素lst.pop_back(); // 删除最后一个元素 lst.pop_front(); // 删除第一个元素 auto it lst.begin(); std::advance(it, 1); lst.erase(it); // 删除第二个元素 lst.remove(3); // 删除所有值为 3 的元素 lst.clear(); // 清空 list1.4. 访问元素std::cout lst.front(); // 访问第一个元素 std::cout lst.back(); // 访问最后一个元素1.5 遍历// 方式 1使用范围 for for (int num : lst) { std::cout num ; } // 方式 2使用迭代器 for (std::listint::iterator it lst.begin(); it ! lst.end(); it) { std::cout *it ; }1.6 总结区别vector动态数组list双向链表底层结构动态数组连续内存双向链表分散存储访问速度随机访问快 (O(1))随机访问慢 (O(n))插入删除尾部操作快 (O(1))中间插入/删除慢 (O(n))任意位置插入/删除快 (O(1))内存使用连续存储节省空间但可能需要扩容每个节点有额外指针开销内存占用较大遍历方式支持 []可用 、- 运算符只能用迭代器 或 --pair这是 C 标准库里的“对组”或“二元组”。它里面可以装两个不同类型的数据。比如pairint, string就是“一个整数 一个字符串”捆绑在一起。list这就是我们刚才聊的链表容器双向链表。合在一起listpairA, B意思就是——这个链表里每一个节点存储的数据不再是一个普通的数字而是一个“小包裹”pair。
