目录

链表（链接列表）简介代码实现以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.pnextwhile 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 # 链表长度+1if __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 # 链表长度-1if __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 = currcurr = 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 

​