【C++】深入理解List：双向链表的应用

风中的云彩

发布于 2025-03-07 10:58:58

5400

代码可运行

文章被收录于专栏：C/C++的自学之路C/C++的自学之路

运行总次数：0

代码可运行

凭时间赢来的东西，时间肯定会为之作证。

前言

这是我自己学习C++的第七篇博客总结。后期我会继续把C++学习笔记开源至博客上。 上一期笔记是关于C++的vector类知识，没看的同学可以过去看看：【C++】探索Vector：灵活的数据存储解决方案-CSDN博客

https://cloud.tencent.com/developer/article/2495371

list类的介绍

在使用list类时，必须包含 #include <list> 这一行。 string类的底层其实是一个储存字符的顺序表结构，而vector类的底层是一个顺序表模板，使用时需要显示实例化，而list类的底层是一个双向链表模板，使用时也需要显示实例化，后面的笔记中以整形为例。下面是list类的官方文本介绍，里面有详细的用法讲解。 cplusplus.com/reference/list/list/?kw=list

https://cplusplus.com/reference/list/list/?kw=list

list类对象的常见构造

list<int> l1，什么也不需要传入，构造一个空的list类对象。 list<int> l2(n,num)，构造一个list类对象，里面包含n个num整形。 list<int> l3(l2.begin(),l2.end())，使用另一个list类对象进行迭代器构造。 list<int> l4(l3)，使用另一个list类对象进行构造。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <list>
using namespace std;
int main()
{
	list<int> l1;
	list<int> l2(5, 1);
	list<int> l3(l2.begin(), l2.end());
	list<int> l4(l3);
	for (auto a : l1)
	{
		cout << a << " ";
	}
	cout << endl;
	for (auto a : l2)
	{
		cout << a << " ";
	}
	cout << endl;
	for (auto a : l3)
	{
		cout << a << " ";
	}
	cout << endl;
	for (auto a : l4)
	{
		cout << a << " ";
	}
	cout << endl;
	return 0;
}
//
//1 1 1 1 1
//1 1 1 1 1
//1 1 1 1 1

list类对象的初始化分为两种。如果使用＝号，则为拷贝初始化；如果不使用＝号，则为直接初始化。 list类对象的初始化时，需要使用大括号包裹初始化值。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <list>
using namespace std;
int main()
{
	list<int> l1 = { 1,2,3,4,5 };
	list<int> l2({ 5,6,7,8,9 });
	for (auto a : l1)
	{
		cout << a << " ";
	}
	cout << endl;
	for (auto a : l2)
	{
		cout << a << " ";
	}
	cout << endl;
	return 0;
}

list类对象的容量操作

list.size()，返回list类对象中有效节点的个数。 list.empty()，检测list类对象的有效大小是否为0，为0返回true，不为0返回flase。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <list>
using namespace std;
int main()
{
	list<int> l1 = { 1,2,3,4,5 };
	list<int> l2({ 5,6,7,8,9 });
	cout << l1.size() << endl;//5
	cout << l2.empty() << endl;//0
	return 0;
}

list类对象的修改操作

list.push_back(num)，在list类对象中尾插整数num。 list.pop_back()，在list类对象中尾删。 list.push_front(num)，在list类对象的首元素之前插入一个元素num。 list.pop front()，删除list类对象的首元素。 list.insert(pos_iterator,n,num)，在下标为pos位置的元素的前面插入n个数字num。 list.erase(pos_iterator)，删除下标为pos位置的元素的上的数字，如果需要删除一串数字，则再给一个截至迭代器。 list.swap(v2)，交换两个list类对象的值。

list类对象的返回值操作

list.front()，返回list类对象的第一个节点的值引用。 list.back()，返回list类对象的最后一个节点的值引用。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <list>
using namespace std;
int main()
{
	list<int> l1 = { 1,2,3,4,5 };
	cout << l1.front() << endl;
	cout << l1.back() << endl;
	return 0;
}

list类对象的遍历操作

由于vector类对象和string类对象的底层都是顺序表，所以都可以进行重构；而list类对象的底层是链表，所以不能进行重构，即无法使用。 list.begin()、list.end()，vector.begin()获取第一个节点的迭代器，string.end()获取最后一个节点的下一个位置的迭代器。 list.rbegin()、list.rend()，list.rbegin()获取头节点的迭代器，vector.rend()获取第一个节点的迭代器。注意反向迭代器进行迭代的步骤也是++，反向迭代器是用来反向遍历链表的。 范围for循环，用于有范围的集合进行遍历，C++11中引入了基于范围的for循环。for循环中的括号由冒号" : "分为两部分：第一部分是用于迭代的变量 （可以使用auto让编译器自动判断变量类型），第二部分则表示被迭代的范围。（自动迭代，自动取数据，自动判断结束。） 范围for循环，如果需要对范围对象进行修改，则使用auto&来修饰迭代的变量；如果需要对较大的目标对象进行遍历，也可以使用auto&来修饰迭代的变量。 范围for循环，是用于遍历容器的，它的底层也是迭代器。（数组也可以用范围for循环。）

//迭代器
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <list>
using namespace std;
int main()
{
	list<int> l1 = { 1,2,3,4,5 };
	auto lt = l1.begin();
	while (lt != l1.end())
	{
		cout << *lt << " ";
		lt++;
	}
	return 0;
}

//反向迭代器
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <list>
using namespace std;
int main()
{
	list<int> l1 = { 1,2,3,4,5 };
	auto lt = l1.rbegin();
	while (lt != l1.rend())
	{
		cout << *lt << " ";
		lt++;
	}
	return 0;
}

//for循环
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <list>
using namespace std;
int main()
{
	list<int> l1 = { 1,2,3,4,5 };
	list<int> l2({ 5,6,7,8,9 });
	for (auto a : l1)
	{
		cout << a << " ";
	}
	cout << endl;
	for (auto& a : l2)
	{
		cout << a << " ";
	}
	cout << endl;
	return 0;
}