---

前言

std::list 是 C++ 标准库中的双向链表容器。与 vector 不同，list 的元素在内存中不是连续存储的，而是通过指针链接。这种结构带来了独特的优缺点：

特性	vector	list
内存布局特性	连续	不连续，节点分散
下标访问	O(1)	不支持
中间插入/删除	O(n) 需移动元素	O(1) 只需改指针
迭代器类型	随机迭代器	双向迭代器

🐶 🐾 ✨ 🐾 🐶

---

1. list 的底层本质：双向循环链表

四大核心特性：

1. 双向：每个节点包含前驱指针（prev）和后继指针（next），支持向前、向后遍历
2. 循环：尾节点的 next 指向头节点，头节点的 prev 指向尾节点，形成闭环
3. 哨兵位头节点：不存储有效数据，避免插入、删除时判断“是否为空”或“是否为头节点”的麻烦
4. 迭代器语义：

• 正向迭代器
  • begin() -> 指向第一个有效元素
  • end() -> 指向哨兵位头节点（尾节点后一个位置）
• 反向迭代器
  • rbegin() -> 指向最后一个有效元素
  • rend() -> 指向哨兵位头节点

🐶 🐾 ✨ 🐾 🐶

---

2. 构造与遍历

2.1 三种构造方式

void test_list1()
{
    list<int> l1;           // 无参构造：空链表
    list<int> l2(5, 1);     // 构造 5 个值为 1 的节点：1 1 1 1 1
    list<int> l3(l2);       // 拷贝构造
}

---

2.2 遍历方式（不能用下标）

list 不支持 [ ] 下标访问，因为内存不连续。只能使用迭代器或范围 for：

// 方式1：迭代器遍历->遍历打印：(list不能再像vector用[]下标访问来打印，只能用迭代器)
list<int>::iterator it = l2.begin();
while (it != l2.end())
{
    cout << *it << " ";
    it++;
}
cout << endl;

// 方式2：范围 for（C++11）
for (auto e : l3)
{
    cout << e << " ";
}
cout << endl;

🐶 🐾 ✨ 🐾 🐶

---

3. 迭代器的特殊性：双向 vs 随机

3.1 为什么 list 不能用 std::sort？

std::sort 依赖随机访问迭代器 ，list里面的数据不是连续存储的，而是用指针指向

void test_list2()
{
    list<int> l1;
    l1.push_back(4);
    l1.push_back(3);
    l1.push_back(2);
    l1.push_back(1);

    // std::sort 要求随机迭代器
    // sort(l1.begin(), l1.end()); //error:list里面的数据不是连续存储的，而是用指针指向
    
	//随机迭代器
    // ✅ 正确：list 自己实现了 sort 算法
    l1.sort();

    for (auto e : l1)
    {
        cout << e << " ";   // 1 2 3 4
    }
}

迭代器分类：

迭代器类型	支持操作	代表容器
随机迭代器	+、-、+=、-=、[ ]	vector、deque
双向迭代器	++、--	list、set、map
单向迭代器	++	forward_list

核心区别 ：list 的迭代器是双向迭代器，只支持 ++ 和 --，不支持 +n 或 -n 的跳跃操作。

---

3.2 遍历时的注意事项

list<int>::iterator it1 = l1.begin();

// ❌ 错误：双向迭代器不支持 + 操作
// l1.insert(it1 + 2, 10);

// ✅ 正确：只能通过多次 ++ 移动
size_t k;
cin >> k;
while (k--)
{
    it1++;
}
l1.insert(it1, 10);  // 在下标为 k 的位置插入

🐾list 的 insert 和 erase 本身是 O(1)，但要找到插入位置需要 O(n) 的遍历时间。

🐶 🐾 ✨ 🐾 🐶

---

4. 增删操作：push、pop、insert、erase

4.1 头尾操作

void test_list3()
{
    list<int> l1({ 1, 2, 3 });

    // 头插
    l1.push_front(0);   // 0 1 2 3

    // 尾插
    l1.push_back(4);    // 0 1 2 3 4

    // 头删
    l1.pop_front();     // 1 2 3 4

    // 尾删
    l1.pop_back();      // 1 2 3
}

---

4.2 中间插入 insert

list<int>::iterator it1 = l1.begin();
size_t k;
cin >> k;               // 输入要插入的位置
while (k--)
{
    it1++;              // 移动到目标位置
}
l1.insert(it1, 10);     // 在 it1 位置前插入 10

---

4.3 中间删除 erase

list<int>::iterator it2 = l1.begin();
size_t t;
cin >> t;
while (t--)
{
    it2++;              // 移动到目标位置
}
l1.erase(it2);          // 删除 it2 位置的元素

注意 ：erase 会使被删除位置的迭代器失效，需要接收返回值或重新获取。

🐶 🐾 ✨ 🐾 🐶

---

5. list 专用算法：sort、unique、reverse、merge

list 提供了自己的算法版本，因为标准库算法（如 std::sort）要求随机迭代器，list 无法直接使用。

---

5.1 find：查找元素

void test_list4()
{
    list<int> l1({ 1, 2, 3, 4, 5 });
    size_t k;
    cin >> k;

    auto pos = find(l1.begin(), l1.end(), k);  // 标准库 find 使用 ++ 即可
}

---

5.2 sort：排序

list<int> l2({ 5, 3, 1, 2, 4 });
l2.sort();                      // 升序排序
// 输出：1 2 3 4 5

---

5.3 unique：去重

使用前必须先排序，因为 unique 只移除相邻的重复元素：

list<int> l3({ 5, 1, 4, 3, 5, 1, 2, 2, 4, 1 });

l3.sort();                      // 排序：1 1 1 2 2 3 4 4 5 5
l3.unique();                    // 去重：1 2 3 4 5

for (auto e : l3)
{
    cout << e << " ";            // 1 2 3 4 5
}

---

5.4 reverse：反转

list<int> l4({ 1, 2, 3, 4, 5 });
l4.reverse();                    // 5 4 3 2 1

---

5.5 merge：合并两个有序链表

list<int> l5({ 5, 3, 1, 2, 4 });
list<int> l6({ 7, 9, 6, 10, 8 });

l5.sort();                       // 1 2 3 4 5
l6.sort();                       // 6 7 8 9 10
l5.merge(l6);                    // 将 l6 合并到 l5，l6 变为空

// l5：1 2 3 4 5 6 7 8 9 10
// l6：（空）

注意 ：merge 要求两个链表都已排序，合并后目标链表仍保持有序。

🐶 🐾 ✨ 🐾 🐶

---

6. 迭代器失效问题与解决方案

6.1 erase 导致的失效

list<int> l1({ 1, 2, 3, 4, 5 });
auto pos = find(l1.begin(), l1.end(), 2);

// ❌ 错误写法：erase 后 pos 失效
// l1.erase(pos);
// cout << *pos << endl;  // 非法访问

// ✅ 正确写法：接收返回值
pos = l1.erase(pos);    // erase 返回被删除元素的下一个位置

for (auto e : l1)
{
    cout << e << " ";    // 1 3 4 5
}
cout << endl;
cout << *pos << endl;    // 3（被删除元素的下一个）

---

6.2 vector vs list 失效对比

操作	vector 迭代器是否失效	list 迭代器是否失效
insert	扩容时全部失效；插入点之后失效	不失效（只改指针）
erase	删除点之后全部失效	只有被删除的迭代器失效
push_back	扩容时全部失效	不失效

list 的优势 ：由于节点是独立分配的，插入和删除只会影响被操作节点的迭代器，其他迭代器依然有效。

🐶 🐾 ✨ 🐾 🐶

---

总结

std::list 的核心使用场景：

分类	核心接口
构造	list()、list(n, val)、拷贝构造
遍历	迭代器、范围 for（!不支持 []）
头尾操作	push_front()、pop_front()、push_back()、pop_back()
中间操作	insert()、erase()（! 需通过 ++ 移动迭代器）
查找	find()（标准库算法）
专用算法	sort()、unique()、reverse()、merge()

关键要点回顾：

• list 底层是双向循环链表 + 哨兵位头节点

• 迭代器是双向迭代器，不支持 +/- 操作

• list 不能用 std::sort，需用自己的 sort() 成员函数

• unique() 前必须先 sort()，因为只移除相邻重复元素

• erase 会使被删除位置的迭代器失效，需用返回值更新

🐶 🐾 ✨ 🐾 🐶

---

本文全部代码

🐾 Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<list>
#include<algorithm>
using namespace std;


//list的本质是双向链表
//双向：每个字节包含前驱指针（prev）和后继指针（next），支持向前，向后遍历
//循环：尾节点的next指向头节点，头节点的prev指向尾节点，形成一个闭环
//哨兵位头节点：避免车插入、删除时判断“是否为空”“是否为头节点的”的麻烦

//正向迭代器：begin（）指向list第一个有效元素，end（）指向头节点（尾节点后一个位置）
//反向迭代器：rbegin（）指向list最后一个有效元素，rend（）指向头节点（反向尾节点后一个位置）

void test_list1()
{
	//构造
	list<int> l1;			//无参构造
	list<int> l2(5, 1);		//构造五个1: 1 1 1 1 1
	list<int> l3(l2);		//拷贝构造

	//遍历打印：(list不能再像vector用[]下标访问来打印，只能用迭代器)
	list<int>::iterator it = l2.begin();
	while (it != l2.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

	for (auto e : l3)
	{
		cout << e << " ";
	}
	cout << endl;
}
//int main()
//{
//	test_list1();
//	return 0;
//}

////////////////////////////////////////////////////////////////////////////////////////////////////////////
void test_list2()
{
	//迭代器
	list<int> l1;
	l1.push_back(4);
	l1.push_back(3);
	l1.push_back(2);
	l1.push_back(1);

	//随机迭代器
	//sort(l1.begin(), l1.end()); //error:list里面的数据不是连续存储的，而是用指针指向
	//std::sort不支持，要求随机迭代器

	l1.sort();			 // list 有专门的 sort 算法
	for (auto e : l1)
	{
		cout << e << " ";
	}
	cout << endl;
}
//
//int main()
//{
//	test_list2();
//	return 0;
//}

////////////////////////////////////////////////////////////////////////////////////////////////////////////

void test_list3()
{
	////元素修改：插入，删除，清空

	list<int> l1({ 1, 2, 3 });

	//头插push_front
	l1.push_front(0);

	//尾插push_back
	l1.push_back(4);

	for (auto e : l1)
	{
		cout << e << " ";
	}
	cout << endl;			//0 1 2 3 4

	//头删pop_front
	l1.pop_front();

	//尾删pop_back
	l1.pop_back();

	for (auto e : l1)
	{
		cout << e << " ";
	}
	cout << endl;			//1 2 3

	//1 2 3
	//插入insert
	list<int>::iterator it1 = l1.begin();

		//l1.insert(it + 2, 10); //error
		//因为list的迭代器是双向迭代器，而双向迭代器是不支持 +/- 的操作，只支持 ++/--
		//所以不能是 it + 2 这种操作
	size_t k;
	cin >> k;
	while (k--)
	{
		it1++;
	}					//当循环结束时，it1=k

	l1.insert(it1, 10); //在下标为k的位置插入10，k的值只能是不能大于目前元素个数
	for (auto e : l1)
	{
		cout << e << " ";
	}
	cout << endl;

	//删除erase(和insert一样，删除中间某个位置数据只能通过循环++获取)
	list<int>::iterator it2 = l1.begin();
	size_t t;
	cin >> t;
	while (t--)
	{
		it2++;
	}					//当循环结束时，it2=t，t不能大于当前元素个数
	l1.erase(it2);
	for (auto e : l1)
	{
		cout << e << " ";
	}
	cout << endl;
}

//int main()
//{
//	test_list3();
//	return 0;
// }

/// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
//常用算法

void test_list4()
{
	//find
	list<int> l1({ 1, 2, 3, 4, 5 });
	size_t k;
	cin >> k;			//从输入读取k，用find查找
	auto pos = find(l1.begin(), l1.end(), k);//找k

	if (pos != l1.end())
	{
		//l1.erase(pos);//pos失效了,pos 就无法再次访问了，不要这样写
		//原来的pos被删掉了，那是不是就该指向一个新的位置了，也就是被删掉元素的下一个位置，因为是链表嘛
		//在list里，pos位置被删掉之后，他占的位置就被销毁了，迭代器必须往后走，而erase就是给他返回下一个元素的位置
		pos = l1.erase(pos); //给 pos 重新赋值，此时 pos 指向的是删除数据的下一个数据
	}
	else
	{
		cout << "没有找到" << endl;
	}

	for (auto e : l1)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << *pos << endl;
	//比如输入2
	//2
	//1 3 4 5
	//3
	//*pos原来是2，2被删除之后，新的*pos就变成了3

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//sort----对list元素进行升序排序

	list<int> l2({ 5, 3, 1, 2, 4 });
	l2.sort();
	for (auto e : l2)
	{
		cout << e << " ";		//1 2 3 4 5
	}
	cout << endl;


//unique()----移除重复的元素，只保留一个

	list<int> l3({ 5, 1, 4, 3, 5, 1, 2, 2, 4, 1 });

	l3.sort();			//1 1 1 2 2 3 4 4 5 5
	for (auto e : l3)
	{
		cout << e << " ";
	}
	cout << endl;

	l3.unique();		//1 2 3 4 5
	for (auto e : l3)
	{
		cout << e << " ";
	}
	cout << endl;

//reverse----反转list中所有元素的顺序

	list<int> l4({ 1, 2, 3, 4, 5 });

	l4.reverse();			//5 4 3 2 1
	for (auto e : l4)
	{
		cout << e << " ";
	}
	cout << endl;

	//merge----蒋两个链表合并在一起，并重新排序
	list<int> l5({ 5, 3, 1, 2, 4 });
	list<int> l6({ 7, 9, 6, 10, 8 });

	l5.sort();
	l6.sort();
	l5.merge(l6); //此时是把l6的数据合并到l5，l6变为空链表

	for (auto e : l5)
	{
		cout << e << " ";			//1 2 3 4 5 6 7 8 9 10
	}
	cout << endl;

	for (auto e : l6)
	{
		cout << e << " ";			//l6为空链表
	}
	cout << endl;
}

int main()
{
	test_list4();
	return 0;
}
//
//int main()
//{
//	//test_list1();
//	//test_list2();
//	//test_list3();
//	test_list4();
//	return 0;
//}

1. 欢迎留言交流
   ​
2. 期待你的评论与建议
   ​
3. 留下你的想法吧

---