文章目录
注意：本文供有一定编程基础的小伙伴阅读，因为这边不会刻意去介绍太多语法层面的内容
1. 链表
1.1 概念
学过 c 语言或者 java 语言的我们应该知道：数组具有连续的储存空间，查找可以通过指定下标进行查找，时间复杂度为 O(1)。但是，数组有个比较麻烦的点就是：移动不便。如图：当第一个元素删除的时候，后续所有元素都需要移动，如果我们从中插入一个元素，插入位置后续的元素也都需要移动。
所以，我们就会思考，有没有什么数据结构可以让插入和删除的操作更加便利呢？链表这时候就显示出他的优势。链表的结点的结构分为两个部分：数据域和指针域。其中，数据域用来存放该结点的数据，指针域用来存放指向下一个结点的指针。
并且，链表的存储空间是不连续的，结点们犹如冰糖葫芦一样，一个个串在一起，这就形成了一个链表。我只要知道一个链表的头结点，那么其他结点我就一定可以得到。
1.2 链表结点的定义
我们通过 python 中的类来定义链表结点
class Node:
def __init__(self,value,next=None):
self.value = value
self.next = next
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 简单分析
每次将想要的玩具提前，其他玩具势必向后移动。这题其实用数组和链表都可以做，但这里由于移动较为频繁且我们需要了解链表这个数据结构，所以我们使用链表来做。
1.5 链表初始化
由于已知玩具的数量，我们先对链表进行初始化。一般为了找到这个链表我们通常都会定义一个无意义的头，如题目中的 Node(0) 作为头结点，这里相当于我做了个标记，这个标记不能动，因为它象征着我的链表。（知道一个链表的头结点 = 知道整条链表），但我们需要进行连接操作的话，必须需要有一个结点来连接，这里我们使用p结点，一开始它等于头结点，然后连接，移动，连接，移动，直至结束。
def createLink(): # 创建链表
head = Node(0) # 头结点
p = head
for i in range(1,11):
p.next = Node(i) # 连接
p = p.next # 移动
return head
具体步骤如下：
1.6 链表插入
把想要的玩具放到放到最前面，我们可以直接插入一个新的想要的玩具，之后再删除想要的玩具。比如我想要玩具2，我新建一个玩具2放到最前面，然后再删除之前的玩具2。（其实也不用那么麻烦，但是还是那句话，为了让我们更了解链表的使用）插入的过程虽然较为简单，但这里存在断连接的操作，需要好好讲讲。
欲在头结点和结点1之间插入结点5
头结点和结点5先建立联系
如果头结点先连接结点5，就会导致头结点和结点1断连接，从而导致无法找到结点1。如果说一定要这样的话，也请先记录结点1。
结点5和结点1先建立联系
如果结点5和结点1先进行连接，就不会导致断连接的操作，即可以从头结点到结点1，也可以从头结点到结点5。然后，头结点再和结点5进行连接，这时候头结点和结点1的连接断掉，从而真正将结点5插入进来。
插入的代码
def insertLink(x,head): # 插入x元素 p = Node(x) p.next = head.next # 连接 head.next = p # 连接 return head
1.7 链表删除
如图，如果我要删除结点2的话，我直接可以用结点1指向结点3（断了结点1和结点2的连接，但结点2和结点3的连接没有断），但我发现一个问题：当设置一个遍历的变量时，如果我查询到结点2的话，我无法知道结点1，因为是单向链表，从结点2到结点3可以很容易得到，但结点2到结点1就很困难了。所以，我们这里采用两个遍历的变量，一个在前一个在后，在后的变量负责记录我要的值的位置，在前的变量负责记录后的变量记录的前一个位置。
def deleteLink(x,head): # 删除x元素
p1 = p2 = head # p1:后指针 p2: 前指针
while p1 != None:
if p1.value == x:
p2.next = p1.next
p2 = p1
p1 = p1.next
return head
1.8 链表打印
最后，最简单的就是打印链表了。只需要一个循环，就可以打印出来。不过，这里要注意的一点是：打印要从头结点的下一个位置开始，因为头结点没有意义。
def showLink(head):
p = head.next
while p!= None:
print(p.value,end=" ")
p = p.next
print("")
1.9 主函数
这里一定要先删除后插入，因为先插入再删除，会把插入的那个给删了，这和我们的目的不符。
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. 实例的完整代码
可在 我的仓库免费查看，如果无法使用可以及时私信我或在评论区指出，谢谢。
本文主要参考蓝桥杯省赛14天夺奖冲刺营，有兴趣的可以自己在蓝桥杯官网搜索
如有错误，敬请指正，欢迎交流🤝，谢谢♪(･ω･)ﾉ