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

链表的‘跑酷’：C++ list 如何在数据中自由穿梭？

article 2025/2/13 6:14:17

前言

本篇博客将详细介绍C++的list

💖 个人主页：熬夜写代码的小蔡

本篇文章所涉及的代码在Gitte仓库

码云——List

🖥 文章专栏：C++

若有问题评论区见

🎉欢迎大家点赞👍收藏⭐文章

一.list的介绍及使用

1.list的介绍

list是一种数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点（以及前一个节点）的指针。在C++中，std::list是一个双向链表，这意味着每个节点既可以向前也可以向后查找。

list的文档介绍http://www.cplusplus.com/reference/list/list/?kw=listhttp://www.cplusplus.com/reference/list/list/?kw=listhttp://www.cplusplus.com/reference/list/list/?kw=listhttp://www.cplusplus.com/reference/list/list/?kw=list

2.list的使用

2.1为什么使用 list

与数组或std::vector相比，std::list在处理频繁插入和删除操作时更加高效。这是因为链表不需要在内存中连续存储数据，插入或删除操作只需要调整节点的指针。

list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已
达到可扩展的能力。以下为list中一些常见的重要接口。

默认构造函数：创建一个空的链表。
大小构造函数：创建一个指定大小的链表，元素默认初始化为默认值（如int初始化为0）。
值初始化构造函数：创建一个指定大小的链表，所有元素初始化为指定值。
范围初始化构造函数：通过另一个容器的迭代器范围初始化链表。
拷贝构造函数：通过另一个链表进行深拷贝初始化。
移动构造函数：通过另一个链表进行移动初始化（资源转移，原链表被置空）。
初始化列表构造函数：使用花括号{}的初始化列表直接初始化链表。
分类说明：
元素操作：这些接口用于添加、删除或修改链表中的元素。
容量和状态查询：这些接口用于获取链表的大小或判断链表是否为空。
访问元素：这些接口用于访问链表开头或末尾的元素。
迭代器操作：这些接口用于遍历链表或反向遍历链表。
链表操作：这些接口用于对链表进行整体操作，如清空、排序、合并或反转。

2.2 list的模拟实现

由于代码比较多，所以不在博客中直接展示，放在下面的码云中

码云——Listhttps://gitee.com/cai-bowei/text.c/blob/master/12.list/list/LIst.hhttps://gitee.com/cai-bowei/text.c/blob/master/12.list/list/LIst.hhttps://gitee.com/cai-bowei/text.c/blob/master/12.list/list/LIst.h

2.3list的迭代器失效

此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无
效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入
时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭
代器，其他迭代器不会受到影响。

int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array + sizeof(array) / sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
	// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给
	//其赋值
	//l.erase(it);
	//++it;
//更改
	it = l.erase(it++);
}