【数据结构】一文了解链表【思路+例题学习】

🏆今日学习目标：
🍀学习算法-数据结构-链表
✅创作者：贤鱼
⏰预计时间：30分钟
🎉个人主页：贤鱼的个人主页
🔥专栏系列：算法
🍁贤鱼的个人社区，欢迎你的加入 贤鱼摆烂团

🍁链表

🍀介绍🍀

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

🍀分类🍀

🍉单项链表🍉

每一个单元都指向下一位

🍉循环链表🍉

和单链表差不多，只不过第一位和最后一位相连，变成了循环链表

🍉双向链表🍉

🍁常见操作🍁

🍀链表🍀

头文件

#include

插入

前方插入push_front(数字)
在链表最前面插入一个数字
后方插入push_back(数字)
链表最后面插入一个数字
中间插入insert(迭代器，数字)
在迭代器指向的链表元素前面插入一个数字

删除

erase(迭代器)
删除迭代器指向的链表元素

查找

begin()
链表头
end()
链表末尾
需要迭代器储存

输出

需要迭代器，后文会讲

结构体模拟部分看例题解法2

🍀迭代器🍀

list::iterator 名字

迭代器是一种检查容器内元素并遍历元素的数据类型
可以理解为数组的下标
举个例子

list<int>::iterator pos[10005];
list<int> m;
pos[5]//迭代器代表的内容就是链表中元素为5的部分
list<int>::iterator iterbegin;
iterbegin=m.begin();
cout<<*iterbegin;//输出链表第一位数值
//循环
list<int>::iterator iterend;
iterend=m.end();
for(;iterbegin!=iterend;iterbegin++){
   
//内容
}
1
2
3
4
5
6
7
8
9
10
11
12
13

循环也很好理解

只有当begin=end的时候循环就会结束

🍁例题🍁

🍀队列安排🍀

🍎题目描述🍎

一个学校里老师要将班上 $N$ 个同学排成一列，同学被编号为 $1\sim N$，他采取如下的方法：

1. 先将 $1$ 号同学安排进队列，这时队列中只有他一个人；

2. $2-N$ 号同学依次入列，编号为 $i$ 的同学入列方式为：老师指定编号为 $i$ 的同学站在编号为 $1\sim (i-1)$ 中某位同学（即之前已经入列的同学）的左边或右边；

3. 从队列中去掉 $M(M<$