当前位置： 首页 > ops >正文

C++ : list

ops 2025/7/27 11:28:03

💬 ：如果你在阅读过程中有任何疑问或想要进一步探讨的内容，欢迎在评论区畅所欲言！我们一起学习、共同成长~！

👍 ：如果你觉得这篇文章还不错，不妨顺手点个赞、加入收藏，并分享给更多的朋友噢~！

1. 基本概念

数据结构本质：std::list 是 C++ 标准库中的双向链表容器，元素存储在独立节点中，每个节点通过指针连接，内存非连续分配。

使用时包含头文件 <list> ；部分/全部展开命名空间。

核心特性：

  • 作为序列式容器，支持双向迭代（可前后遍历）；
  • 任意位置插入 / 删除操作时间复杂度为常数级（O (1)），相比 array、vector、deque，此类操作效率更高。
     

与 forward_list 的区别：
forward_list 是单链表（仅支持单向迭代），结构更简单、空间更高效；list 为双向链表（支持双向迭代）。

主要缺陷：

  • 不支持通过索引（operator[] 或 迭代器+/-n）随机访问，访问第 n 个元素需从头部 / 尾部逐个移动；
     
  • 额外空间开销（每个节点需存储前驱 / 后继指针，对存储小元素的大 list 影响较明显）。

2. list 的常见重要接口

2.1 构造

list()默认构造：创建空链表
list (size_type n, const value_type& val)创建包含 n 个值为 val 的元素的链表
list (InputIterator first, InputIterator last)用迭代器 [first, last) 范围内的元素构造链表
list (const list& other)拷贝构造：复制 other 的所有元素
#include <iostream>
#include <list>
using namespace std;int main()
{// 默认构造list<int> mylist1;// 创建包含 n 个值为 val 的元素的链表list<int> mylist2(5, 10);// 用迭代器 [first, last) 范围内的元素构造链表int arr[] = { 1, 2, 3, 4, 5 };list<int> mylist3(arr, arr + 5);// 拷贝构造list<int> mylist4(mylist2);cout << "mylist1: ";for (auto it = mylist1.begin(); it != mylist1.end(); ++it)cout << *it << " ";cout << endl;cout << "mylist3: ";for (auto it = mylist3.begin(); it != mylist3.end(); ++it)cout << *it << " ";cout << endl;return 0;
}

2.2 迭代器

begin()返回指向第一个元素的正向迭代器
end()返回指向最后一个元素后一位置的正向迭代器
rbegin()返回指向最后一个元素的反向迭代器
rend()返回指向第一个元素前一位置的反向迭代器

正向遍历：

​for (auto it = mylist.begin(); it != mylist.end(); ++it){cout << *it << " ";}
cout << endl;

反向遍历：

for (auto it = mylist.rbegin(); it != mylist.rend(); ++it){cout << *it << " ";}
cout << endl;

2.3 容量

empty()检测list是否为空，空则返回true，否则返回false
size()返回list中有效节点的个数

2.4 元素访问

front()返回第一个元素的引用（未定义行为：链表为空时调用）
back()返回最后一个元素的引用（未定义行为：链表为空时调用）
cout << "第一个元素: " << mylist.front() << endl;
cout << "最后一个元素: " << mylist.back() << endl;

2.5 修改

push_front(val)在头部插入元素 val
pop_front()删除头部元素
push_back(val)在尾部插入元素 val
pop_back()删除尾部元素
insert(it, val)在迭代器 it 指向的位置处插入 val，返回新元素的迭代器
erase(it)删除迭代器 it 指向的元素，返回下一个元素的迭代器
clear()清空链表
swap(other)交换两个链表的内容，仅交换内部指针

使用 insert() 或 erase() 时要定位元素，list 中可以使用 std::advance(it, n) 。

it ：一个迭代器的引用，表示待移动的迭代器

n ：移动的步数（整数类型）

  • n > 0：后移；
  • n < 0：前移（仅当迭代器支持反向操作时有效，如双向迭代器）

使用时要包含头文件 <iterator>

#include <iostream>
#include <list>
#include  <iterator>
using namespace std;int main()
{list<int> mylist;mylist.push_front(1);mylist.push_front(2);mylist.push_front(3);cout << "使用 push_front 头插元素后：";for (int val : mylist)cout << val << " ";cout << endl;mylist.push_back(4);mylist.push_back(5);cout << "使用 push_back 尾插元素后：";for (int val : mylist)cout << val << " ";cout << endl;mylist.pop_front();cout << "使用 pop_front 删除头部元素后：";for (int val : mylist)cout << val << " ";cout << endl;mylist.pop_back();cout << "使用 pop_back 删除尾部元素后：";for (int val : mylist)cout << val << " ";cout << endl;auto it = mylist.begin();advance(it, 1); // 头部迭代器后移1位auto new_it = mylist.insert(it, 99); // 第2个位置处插入cout << "使用 insert 在指定位置插入 99 后：";for (int val : mylist)cout << val << " ";cout << endl;it = mylist.begin();advance(it, 2); // 头部迭代器后移2位auto next_it = mylist.erase(it); // 第三个位置处删除cout << "使用 erase 删除指定位置元素后：";for (int val : mylist)cout << val << " ";cout << endl;mylist.clear();cout << "使用 clear 清空链表后，链表是否为空："<< (mylist.empty() ? "是" : "否") << endl;return 0;
}

2.6 迭代器失效问题

  • 插入操作：插入元素不会使任何迭代器 / 引用失效（新节点独立分配内存）。
  • 交换操作：交换两个链表的内容不会使迭代器失效（迭代器仍指向原链表的元素，但原链表已与另一个链表交换内容）。
  • 删除操作：仅使指向被删除元素的迭代器 / 引用失效，其他迭代器不受影响。

易错点1：循环中直接删除元素后继续使用原迭代器

for (auto it = list.begin(); it != list.end(); ++it) 
{if (*it == target) {list.erase(it);  // 删除后it已失效，继续++it会导致崩溃}
}

改正：用 erase 的返回值更新迭代器

for (auto it = list.begin(); it != list.end(); ) 
{if (*it == target) {it = list.erase(it);  // 返回下一个有效迭代器} else {++it;  // 不删除时递增}
}

易错点2：删除元素后访问已失效的迭代器

auto it = list.begin();
list.erase(it);
std::cout << *it;  // 访问已失效的迭代器

改正：删除后立即通过 erase 返回值获取新迭代器

auto it = list.begin();
it = list.erase(it);  // it 现在指向下一个元素或 end()

3. list 的模拟实现

3.1 反向迭代器

template<class Iterator>
class ReverseListIterator
{
public:// 明确告诉编译器 Ref/Ptr 是 Iterator 的嵌套类型（而非静态成员）typedef typename Iterator::Ref Ref;typedef typename Iterator::Ptr Ptr;typedef ReverseListIterator<Iterator> Self;public:// 构造函数：用原迭代器初始化反向迭代器ReverseListIterator(Iterator it) : _it(it) {}// 解引用操作：返回原迭代器前一个位置的元素Ref operator*() {Iterator temp(_it);  // 创建临时迭代器副本--temp;              // 临时迭代器左移（对应反向迭代器的“当前位置”）return *temp;        // 返回临时迭代器指向的元素}// 箭头操作符：通过解引用获取元素地址Ptr operator->() {return &(operator*());  // 依赖 operator*() 返回左值引用}// 前置递增：反向迭代器右移（原迭代器左移）Self& operator++() {--_it;  // 原迭代器左移，对应反向迭代器右移return *this;}// 后置递增：返回旧值后递增Self operator++(int) {Self temp(*this);  // 保存旧状态--_it;             // 原迭代器左移return temp;       // 返回旧状态}// 前置递减：反向迭代器左移（原迭代器右移）Self& operator--() {++_it;  // 原迭代器右移，对应反向迭代器左移return *this;}// 后置递减：返回旧值后递减Self operator--(int) {Self temp(*this);  // 保存旧状态++_it;             // 原迭代器右移return temp;       // 返回旧状态}// 不等比较：基于原迭代器的不等关系bool operator!=(const Self& other) const {return _it != other._it;  // 直接比较原迭代器}// 相等比较：修正原代码的逻辑错误bool operator==(const Self& other) const {return _it == other._it;  }private:Iterator _it;  // 反向迭代器的核心：持有原迭代器
};
面/笔试高频考点具体内容
typename的作用明确Iterator::Ref/Ptr是迭代器的嵌套类型（非静态成员），解决模板依赖类型歧义问题
与原迭代器的操作映射

反向迭代器++对应原迭代器--，--对应原迭代器++；

operator*需取原迭代器前一位置元素

操作符重载细节

前置++/--返回引用（修改自身），后置++/--返回旧值（先保存再修改）；

operator->依赖operator*返回左值引用

相等 / 不等比较逻辑operator==需直接比较原迭代器，与operator!=互斥

3.2 双向链表节点与迭代器实现

template <typename T>
struct ListNode {T data;ListNode* prev;ListNode* next;explicit ListNode(const T& val = T()) : data(val), prev(nullptr), next(nullptr) {}
};template <typename T>
class ListIterator {
public:using iterator_category = std::bidirectional_iterator_tag;using value_type = T;using pointer = T*;using reference = T&;ListIterator(ListNode<T>* node) : m_node(node) {}reference operator*() const { return m_node->data; }pointer operator->() const { return &m_node->data; }// 前置++ListIterator& operator++() {m_node = m_node->next;return *this;}// 后置++ListIterator operator++(int) {ListIterator tmp = *this;m_node = m_node->next;return tmp;}// 前置--ListIterator& operator--() {m_node = m_node->prev;return *this;}// 后置--ListIterator operator--(int) {ListIterator tmp = *this;m_node = m_node->prev;return tmp;}bool operator==(const ListIterator& other) const { return m_node == other.m_node; }bool operator!=(const ListIterator& other) const { return m_node != other.m_node; }private:ListNode<T>* m_node;
};

3.3 链表核心类实现

template <typename T>
class MyList {
public:// 类型别名（面试常考）using value_type = T;using iterator = ListIterator<T>;using const_iterator = ListIterator<const T>;// 默认构造：初始化哨兵头节点MyList() {m_head = new ListNode<T>();m_head->prev = m_head;m_head->next = m_head;}// 拷贝构造（深拷贝）MyList(const MyList& other) {m_head = new ListNode<T>();m_head->prev = m_head;m_head->next = m_head;for (auto it = other.begin(); it != other.end(); ++it) {push_back(*it);}}// 赋值运算符（深拷贝 + 自赋值安全）MyList& operator=(const MyList& other) {if (this != &other) {clear();for (auto it = other.begin(); it != other.end(); ++it) {push_back(*it);}}return *this;}// 析构函数（释放所有节点）~MyList() {clear();delete m_head;}// 迭代器接口iterator begin() { return iterator(m_head->next); }iterator end() { return iterator(m_head); }// 核心操作：头插 & 尾插void push_front(const T& val) {insert(begin(), val);}void push_back(const T& val) {insert(end(), val);}// 核心操作：头删 & 尾删void pop_front() {erase(begin());}void pop_back() {erase(--end()); // 尾迭代器需先递减}// 插入操作（面试高频）iterator insert(iterator pos, const T& val) {ListNode<T>* curr = pos.m_node;ListNode<T>* newNode = new ListNode<T>(val);// 调整指针顺序：prev -> newNode -> currnewNode->prev = curr->prev;newNode->next = curr;curr->prev->next = newNode;curr->prev = newNode;return iterator(newNode); // 返回新节点迭代器}// 删除操作（面试高频）iterator erase(iterator pos) {if (pos == end()) return pos; // 不能删除end()ListNode<T>* delNode = pos.m_node;ListNode<T>* nextNode = delNode->next;// 断开指针连接delNode->prev->next = nextNode;nextNode->prev = delNode->prev;delete delNode; // 释放内存return iterator(nextNode); // 返回下一个元素迭代器}// 清空链表void clear() {auto curr = m_head->next;while (curr != m_head) {auto next = curr->next;delete curr;curr = next;}// 恢复哨兵头节点自环m_head->prev = m_head;m_head->next = m_head;}// 辅助功能bool empty() const { return m_head->next == m_head; }size_t size() const {size_t cnt = 0;for (auto it = begin(); it != end(); ++it) cnt++;return cnt;}T& front() { return *begin(); }T& back() { return *(--end()); }private:ListNode<T>* m_head; // 哨兵头节点（不存储数据）
};

4. 对比 list 与 vector

对比维度vectorlist
底层结构动态顺序表，一段连续内存空间带头结点的双向循环链表
随机访问支持随机访问，时间复杂度 O (1)不支持随机访问，时间复杂度 O (N)
插入和删除

任意位置插入 / 删除效率低（需搬移元素，时间复杂度 O (N)）；

可能触发增容（开辟新空间→拷贝→释放旧空间）

任意位置插入 / 删除效率高（无需搬移元素，时间复杂度 O (1)）
空间利用率

连续内存，不易产生内存碎片；

缓存利用率高

节点动态开辟，小节点易产生内存碎片；

缓存利用率低

迭代器原生态指针（如 T*）对节点指针（如 ListNode*）的封装类
迭代器失效

插入可能因扩容导致所有迭代器失效；

删除需重新赋值当前迭代器否则失效

插入不会导致迭代器失效；

删除仅当前迭代器失效，其他迭代器不受影响

使用场景需要高效存储、支持随机访问，不关心插入 / 删除效率的场景大量插入 / 删除操作，不关心随机访问效率的场景

http://www.xdnf.cn/news/8934.html

相关文章：

  • TDengine 中集群维护
  • 基于开源链动2+1模式AI智能名片S2B2C商城小程序的产品驱动型增长策略研究
  • 猿大师办公助手网页编辑Office/wps支持服务器文件多线程下载吗？
  • 技术文档写作方法——以MATLAB滤波为例
  • 仓储物流场景下国标GB28181视频平台EasyGBS视频实时监控系统应用解决方案
  • Webtrees 手册/程序概述
  • 组态王KingSCADA3.53连接S7-1200PLC实战教程
  • Nginx 基本概念深度解析：从服务器特性到代理模式应用​
  • 亚当·斯密思想精髓的数学建模与形式化表征
  • 《软件工程》第 15 章 - 软件度量与估算：从概念到实践​
  • 离线安装Microsoft 照片【笔记】
  • Language Model
  • Vue-01（Vue CLI创建项目以及文件配置说明）
  • 爬虫学习-Scrape Center spa2 超简单 JS 逆向
  • 【WEB3】区块链、隐私计算、AI和Web3.0——可信数字身份体系构建（3）
  • Science Robotics 具身智能驱动的空中物理交互新范式：结合形态和传感，与非结构化环境进行稳健交互
  • 2025.05.22-得物春招机考真题解析-第二题
  • 【算法深练】双序列双指针：用“双轨并行”思维，高效破解算法难题
  • RabbitMQ 集群与高可用方案设计（三）
  • 基于多模态提示融合的交互式图像标注系统设计与实现
  • Java 访问者模式深度重构：从静态类型到动态行为的响应式设计实践
  • FastDFS集群部署与性能优化实战
  • 【后端高阶面经：MongoDB篇】41、MongoDB 是怎么做到高可用的？
  • 【自然语言处理与大模型】大模型Agent四大的组件
  • AI时代新词-大模型（Large Language Model）
  • 网络编程——UDP网络编程
  • flash_attn 安装慢的解决方法
  • 《软件工程》第 14 章 - 持续集成
  • 软考 系统架构设计师系列知识点之杂项集萃（75）
  • 【自然语言处理与大模型】大模型（LLM）基础知识⑤