文章目录
1. 双向链表
1.1 概念
单向链表我们只能从一个方向找我想要的结点，而双向链表可以双向找我想要的结点。就比如在只用一个变量遍历链表中的元素时，我们发现到了要删的元素的时候，无法得到他的上一个元素，而双向链表就可以在使用一个变量遍历链表时得到前面的元素。
事实上，单向链表也可以用一个变量遍历元素做到删减的功能，等下在循环链表有应用。
双向链表由数据域，左指针域和右指针域组成。
相互连接关系为：
前一个结点的右指针指向后一个结点，后一个结点的左指针指向前一个结点。
我们暂时先将结点简化为：
1.2 结点的定义
根据 python 类的定义双向链表的结点：
class Node:
def __init__(self,value,left=None,right=None):
self.value = value
self.left = left
self.right = right
1.3 实例
我们还是通过这个实例来了解一下，双向链表的定义和使用。
题目描述
小王子有一天迷上了排队的游戏，桌子上有标号为 1−10 的 10 个玩具，现在小王子将他们排成一列，可小王子还是太小了，他不确定他到底想把那个玩具摆在哪里，直到最后才能排成一条直线，求玩具的编号。已知他排了 M 次，每次都是选取标号为 X 个放到最前面，求每次排完后玩具的编号序列。
输入描述
第一行是一个整数 M，表示小王子排玩具的次数。
随后 M 行每行包含一个整数 X，表示小王子要把编号为 X 的玩具放在最前面。
输出描述
共 M 行，第 i 行输出小王子第 i 次排完序后玩具的编号序列。
输入输出样例
示例 1
输入
5
3
2
3
4
2
输出
3 1 2 4 5 6 7 8 9 10
2 3 1 4 5 6 7 8 9 10
3 2 1 4 5 6 7 8 9 10
4 3 2 1 5 6 7 8 9 10
2 4 3 1 5 6 7 8 9 10
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
1.4 链表初始化
先右连接下一个，再左连接上一个（左连接这里用的是需要用建立好的连接先从右连接到下一个结点，然后再用左连接连接到上一个结点）
def createLink(): # 创建链表
head = Node(0)
p = head
for i in range(1,11):
p.right = Node(i) # 右连接下一个
p.right.left = p # 左连接上一个
p = p.right # 移动
return head
1.5 链表插入
欲在头结点和结点1之间插入结点5，注意以下只是其中一种插入方法
结点5和结点1先建立连接
当结点1建立与结点5的左连接时，结点1到头结点的左连接中断
结点5和头结点再建立联系
当头结点建立与结点5的右连接时，头结点到结点1的右连接中断，至此头结点与结点1没有任何连接。
插入的代码
def insertLink(x,head): # 插入x元素 p = Node(x) p.right = head.right # 插入的结点建立右连接 p.right.left = p # 再建立其左连接 head.right = p # 头和插入结点建立右连接 p.left = head # 再建立其左连接 return head
1.6 链表删除
注意以下只是其中一种删除方法，代码采用的是先建立左连接，再建立右连接的方法
先建立右连接
若结点 i 与 i+2 建立右连接，则结点 i 与待删除结点的右连接中断
再建立左连接
若结点 i+2 与 i 建立左连接，则结点 i+2 与待删除结点的左连接中断
删除的代码
def deleteLink(x,head): # 删除x元素 p = head while p != None: if p.value == x: p.right.left = p.left # 建立左连接 p.left.right = p.right # 建立右连接 p = p.right return head
1.7 链表打印
和单向链表一样，不过使用 right 指向下一个
def showLink(head):
p = head.right
while p!= None:
print(p.value,end=" ")
p = p.right
print("")
1.8 主函数
这里一定要先删除后插入，因为先插入再删除，会把插入的那个给删了，这和我们的目的不符。
if __name__ == '__main__':
head = createLink()
n = int(input())
for i in range(n):
x = int(input())
deleteLink(x,head)
insertLink(x,head)
showLink(head)
2. 循环链表
2.1 概念
我们将单向链表的头结点和尾结点相连，就组成了新的一种链表，循环链表。（我们这里一般较少用双向链表去建立循环链表，因为他的删除和加入和结点结构都比单向链表复杂）。
循环链表的结构：
2.2 结点的定义
由于由单向链表组成，所以结点的定义并无区别。
class Node:
def __init__(self,value,next=None):
self.value = value
self.next = next
2.3 实例
我们通过这个实例来了解一下，循环链表的定义和使用。
题目描述
设有 n 个人围坐在圆桌周围，现从某个位置 k 上的人开始报数，报数到 m 的人就站出来。下一个人，即原来的第 m+1 个位置上的人，又从 1 开始报数，再报数到 m 的人站出来。依次重复下去，直到全部的人都站出来为止。试设计一个程序求出这 n 个人的出列顺序。
要求一：采用循环链表解决。
要求二：可以使用模拟法，模拟循环链表。
要求三：可以不使用循环链表类的定义使用方式。
输入描述
输入只有一行且为用空格隔开的三个正整数 n,k,m，其含义如上所述。
输出描述
共 n 行，表示这 n 个人的出列顺序。
输入输出样例
示例 1
输入
3 5 8
输出
3
2
1
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
2.4 简单分析
如果使用数组也能做，要不就是删除数组中的元素（需要进行多次移动），要不就是设置一个标记出列的为 0 ，未出列的为 1，但这可能需要频繁判断数组元素是否出列。所以这里还是采用循环链表来做。
2.5 链表初始化
和单向链表一致，只是尾结点连接的不再是 none，而是 head，注意这里：头结点并不再是无意义的数值，而是有数据元素的结点，也就是没有头结点这个说法了，而是首元结点： 单链表中第一个有数据元素的结点。
在初始化时我们也要注意 <1 个结点肯定构不成链表，而 1 个结点没必要用循环链表，再怎么循环都是它自己，所以我们先判断再连接。
def createLink(n):
# 先判断
if n <= 0:
return False
elif n == 1:
return Node(1)
else:
head = Node(1)
p = head
for i in range(2,n+1):
p.next = Node(i)
p = p.next
p.next = head # 首尾相接
return head
2.6 链表模拟过程（主函数）
2.6.1 输入数据
我们可以通过 map 函数输入 n,k,m，然后创建循环列表，并定义遍历变量 p
n,k,m = map(int,input().split())
head = createLink(n)
p = head
2.6.2 循环遍历 p 到第一次 k 的位置
从结点 1 到结点 k 需要移动 k-1 步
## 先到k的位置
for i in range(k-1):
p = p.next
2.6.3 模拟
我们移动后的步骤应该就是删除了，由于我们使用的是一个变量的遍历，他一定在待删除结点的上一个结点，所以约舍夫环出队的元素应该在该变量的下一个结点里。如果我们只剩一个结点（这里指的是待删除结点的上一个结点），当打印出队元素的时候因为空，所以应该正删除之前加上一个循环判定，如果结点不是链表中最后的结点，执行删除和打印操作。
while p.next != p: # p 不是最后的结点
我们从刚才的模拟过程应该知道：p 是待删除结点的上一个结点，所以应该报数到 m-1 ,而报数 m-1 需要移动 m-2次（如报数 3，1 到 3 只需移动 2 步）
for i in range(m-2): # 找到该删除指针的上一个指针
p = p.next
这时候我们指向要删除的上一个结点，所以我们先打印出来
print(p.next.value)
再进行删除操作：
p.next = p.next.next # 连接
p = p.next # 重新从1开始报数
由于之前我们的循环判断的是：p 不是最后的结点，所以跳出循环还有一个结点，我们也要打印出来。
print(p.value)
3. 完整代码
可在 我的仓库免费查看，如果无法使用可以及时私信我或在评论区指出，谢谢。
本文主要参考蓝桥杯省赛14天夺奖冲刺营，有兴趣的可以自己在蓝桥杯官网搜索
如有错误，敬请指正，欢迎交流🤝，谢谢♪(･ω･)ﾉ