Python链表详细笔记
目录
链表（链接列表）简介
代码实现
以class类创建节点
以class类创建链表
生成简单链表
输出简单链表
通过函数生成链表
输出函数生成链表
通过函数输出链表
通过函数插入节点（在给定节点之后添加节点）
通过函数删除节点
搜索链表中的元素
对于按位置查值
对于按位置查找
实战练习
反转链表
交换链接列表中的节点而不只交换值
链表（链接列表）简介
与数组一样，Linked List链表是一种线性数据结构。与数组不同，链表元素不存储在连续的位置; 元素使用指针链接。
为何链接列表？ 数组可用于存储类似类型的线性数据，但数组具有以下限制。 1）数组的大小是固定的：所以我们必须事先知道元素数量的上限。而且，通常，分配的存储器等于上限而与使用无关。 2）在元素数组中插入新元素是昂贵的，因为必须为新元素创建空间并创建空间必须移动现有元素。
相对于阵列的优点 1）动态大小 2）易于插入/删除
相对于阵列的缺点： 1）不允许随机访问。我们必须从第一个节点开始按顺序访问元素。因此，我们不能使用其默认实现有效地使用链表进行二进制搜索。 2）列表的每个元素都需要指针的额外内存空间。 3）不缓存友好。由于数组元素是连续的位置，因此存在引用的位置，在链接列表的情况下不存在。
表示： 链表由指向链表的第一个节点的指针表示。第一个节点称为头部。如果链接列表为空，则head的值为NULL。 列表中的每个节点至少由两部分组成： 1）数据 2）指向下一个节点的指针（或参考）
代码实现
以class类创建节点
每个节点包含当前节点所要存的数据data，和指向下一节点的pnxet指针。pnext指针默认给空值。
class Node:
def __init__(self, data, pnext=None):
self.data = data
self.pnext = pnext以class类创建链表
链表初始时候有一个空的phead头指针，和表示链表长度的length。
class Link:
def __init__(self):
self.phead = None
self.length = 0生成简单链表
先实例化链表Link，然后实例化节点Node，最后把节点链接起来
if __name__ == '__main__':
link = Link() # 实例化链表Link
first = Node(1) # 实例化节点Node1
second = Node(2) # 实例化节点Node2
third = Node(3) # 实例化节点Node3
link.phead = Node(None) # 实例化空节点Node
link.phead.pnext = first # 链接节点head-1
first.pnext = second # 链接节点1-2
second.pnext = third # 链接节点2-3
third.pnext = None # 链接节点3-end
'''
list.head first second third
| | | |
| | | |
+----+------+ +----+------+ +----+------+ +----+------+
|None| None |---->| 1 | None |---->| 2 | None |---->| 3 | None |
+----+------+ +----+------+ +----+------+ +----+------+
'''输出简单链表
输出当前节点的data，再将pnext指针指向下一个链表，循环直至末尾
temp = link.phead.pnext
while temp:
print(temp.data)
temp = temp.pnext
# Output：
# 1 2 3通过函数生成链表
先创建一个phead头结点，注意该节点内不放数据。然后依次从所给的入参循环创建节点，并将节点链接，再将长度length+1。最后记得将末尾节点的pnext指针指向空None，并返回所生成链表的phead头指针。
class Link:
def __init__(self):
self.phead = None
self.length = 0
def creat(self, datas):
self.phead = Node(None) # 创建空的头部，不存数据
pend = self.phead # 借用临时量，方便后续操作
for i in datas: # 依次从所给入参中拿数据
node = Node(i) # 创建节点
pend.pnext = node # 上一节点的pnext指针，指向这个新创建的节点
pend = node # 这个节点赋值给临时量，方便进行下一轮循环
self.length += 1 # 链表长度+1
pend.pnext = None # 末尾节点的pnxet指针为空，表示后面无数据
return self.phead # 返回生成的链表的头指针输出函数生成链表
输出当前节点的data，再将pnext指针指向下一个链表，循环直至末尾
if __name__ == '__main__':
link = Link() # 实例化链表Link
new = link.creat([1,2,3,4,5,6])
new = new.pnext
while new:
print(new.data)
new = new.pnext
# Output：
# 1 2 3 4 5 6通过函数输出链表
可以通过节点是否为None来判断是否到末尾，也可通过之前的self.length来判断
class Link:
def __init__(self):
self.phead = None
self.length = 0
def display(self):
cursor = self.phead.pnext # 定位到第一个节点
for i in range(self.length): # 根据长度判断是否到末尾
print(cursor.data) # 输出节点数据
cursor = cursor.pnext # 指向下一节点
if __name__ == '__main__':
link = Link() # 实例化链表Link
new = link.creat([1,2,3,4,5,6])
link.display()
# Output：
# 1 2 3 4 5 6通过函数插入节点（在给定节点之后添加节点）
该函数需要指定插入的位置index，和要插入的数据val。先从头结点开始循环遍历，直到到达了位置index，再创建val对应的节点，以上图为例，先将新建节点E的pnext指针指向下一节点C，再将上一节点B的pnext指针指向节点E。最后记得将length+1。
class Link:
def insert(self, index, val):
cursor = self.phead # 定位到头节点
for i in range(index): # 跳过index个节点
cursor = cursor.pnext
node = Node(val) # 创建新节点
node.pnext = cursor.pnext # 新建节点的pnext = 上一节点的pnext
cursor.pnext = node # 上一节点的pnext = 新建节点
self.length += 1 # 链表长度+1
if __name__ == '__main__':
link = Link() # 实例化链表Link
new = link.creat([1,2,3])
link.display()
link.insert(3,0)
link.display()
# Output：
# 1 2 3
# 1 2 3 0 通过函数删除节点
该函数需要指定待删除节点所在位置index。先找到要删除的节点的上一个节点，更改上一个节点到下一个节点，释放要删除的节点的内存。在C语言中为malloc()和free()对应使用，python中可使用del。
如果要删除的节点是root，只需将其删除即可。要删除中间节点，我们必须有指向要删除的节点之前的节点的指针。因此，如果位置不为零，我们运行循环位置-1次并获得指向前一节点的指针。
class Link:
def delete(self, index):
if index > self.length or index <= 0:
print('Out of index')
return
cursor = self.phead # 定位到头节点
for i in range(index-1): # 跳过index-1个节点
cursor = cursor.pnext
nextnode = cursor.pnext.pnext # 存储需要删除的节点的下一个节点
del cursor.pnext # 删除节点
cursor.pnext = nextnode # 连接上一节点与下一节点
self.length -= 1 # 链表长度-1
if __name__ == '__main__':
link = Link() # 实例化链表Link
new = link.creat([1,2,3,4,5,6])
link.display()
link.delete(4)
link.display()
link.delete(10)
# Output：
# 1 2 3 4 5 6
# 1 2 3 5 6
# Out of index搜索链表中的元素
搜索元素分为按位置index查找值data，和按值data查找位置index。
对于按位置查值
循环链表，直至找到值，并返回位置index，否则提示输出。
class Link:
def searchByval(self, val):
cursor = self.phead.pnext
index = 0
while cursor:
index += 1
if val == cursor.data:
print(index) # 输出值
return index # 返回值
cursor = cursor.pnext # 指向下一个节点
print("No available value") # 输出提示
return None # 返回值
if __name__ == '__main__':
link = Link() # 实例化链表Link
new = link.creat([9,5,7,4,2,6])
link.display()
link.searchByval(3)
link.searchByval(4)
# Output：
# 9 5 7 4 2 6
# No available value
# 4对于按位置查找
先判断index是否在链表长度length内，然后循环值index，输出值data，否则输出提示。
class Link:
def searchByindex(self, index):
if index > self.length or index <= 0:
print('Out of index') # 输出提示
return None
cursor = self.phead # 定位到头节点
for i in range(index):
cursor = cursor.pnext
print(cursor.data) # 输出值
return cursor.data # 返回值
if __name__ == '__main__':
link = Link() # 实例化链表Link
new = link.creat([9,5,7,4,2,6])
link.display()
link.searchByindex(3)
link.searchByindex(10)
# Output：
# 9 5 7 4 2 6
# 7
# Out of index实战练习
反转链表
示例：
输入：以下链表的头部 1-> 2-> 3-> 4-> NULL 输出：链接列表应更改为， 4-> 3-> 2-> 1-> NULL 输入：以下链表的头部 1-> 2-> 3-> 4-> 5-> NULL 输出：链接列表应更改为， 5-> 4-> 3-> 2-> 1-> NULL 输入：NULL 输出：NULL 输入：1-> NULL 输出：1-> NULL
迭代法
- 初始化三个指针prev为NULL，curr为head，next为NULL。
- 通过链表迭代。在循环中，执行以下操作。 //在更改当前节点的下一个节点之前， //存储下一个节点 next = curr-> next //现在改变当前节点的下一节点 //这是实际逆转发生的地方 curr-> next = prev //将prev和curr向前移动一步 prev = curr curr = next
总结为：先存储当前节点的下一节点，再反转当前节点的pnext指针，最后重置head头部。 注意：若head指向Null而不放数据，则prev、curr、next应相应改变
class Link:
def reverse(self):
prev = self.phead # 上一指针
curr = self.phead.pnext # 当前指针
next = self.phead # 下一指针
while curr:
next = curr.pnext # 先存储下一节点
curr.pnext = prev # 反转pnext指针指向
prev = curr # 反转完成后，上一节点后移
curr = next # 反转完成后，当前节点后移
self.phead.pnext = prev # 重置节点
if __name__ == '__main__':
link = Link() # 实例化链表Link
new = link.creat([1,2,3,4,5,6])
link.display()
link.reverse()
link.display()
# Output：
# 1 2 3 4 5 6
# 6 5 4 3 2 1 交换链接列表中的节点而不只交换值
给定一个链表和两个键，交换两个给定键的节点。应通过更改链接来交换节点。在数据包含许多字段的许多情况下，交换节点数据可能是昂贵的。
可以假设链表中的所有键都是不同的。
例子：
输入：10-> 15-> 12-> 13-> 20-> 14，x = 3，y = 5 输出：10-> 15-> 20-> 13-> 12-> 14 输入：10-> 15-> 12-> 13-> 20-> 14，x = 1，y = 5 输出：20-> 15-> 12-> 13-> 10-> 14 输入：10-> 15-> 12-> 13-> 20-> 14，x = 3，y = 4 输出：10-> 15-> 13-> 12-> 20-> 14
这可能看起来很简单，但这是一个有趣的问题，因为它有以下案例需要处理。
- x和y可以相邻也可以不相邻。
- x或y可以是头节点。
- x或y可以是最后一个节点。
- 链接列表中可能不存在x和/或y。
它首先在给定的链表中搜索x和y。如果其中任何一个不存在，那么返回。在搜索x和y时，跟踪当前和之前的指针。首先更改前一个指针的下一个，然后更改当前指针的下一个。
class Link:
def swapNodes(self, x, y):
if x > self.length or y > self.length: # 判断是否在内
print("invalid")
return None
ma = max(x, y) # 较大者
mi = min(x, y) # 较小者
cursor = self.phead # 指向头部
curr_x = self.phead.pnext # 指向第一个节点
pre_x = self.phead # 指向头部
for i in range(ma-1): # 遍历较大者
cursor = cursor.pnext
if i == mi - 2: # 遍历较小者
pre_x = cursor # x节点的上一节点
curr_x = cursor.pnext # x节点
pre_y = cursor # y节点的上一节点
curr_y = cursor.pnext # y节点
pre_x.pnext, pre_y.pnext = pre_y.pnext, pre_x.pnext # 交换指针
curr_x.pnext, curr_y.pnext = curr_y.pnext, curr_x.pnext # 交换指针
if __name__ == '__main__':
link = Link() # 实例化链表Link
new = link.creat([1,2,3,4,5,6])
link.display()
link.swapNodes(1, 4)
link.display()
# Output:
# 1 2 3 4 5 6
# 4 2 3 1 5 6 未完待续...
欢迎关注↓↓↓
- 微信公众号：xfxuezhang
腾讯云开发者
