基本概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。链表在逻辑上是连续的，但是在物理空间上可能是不连续的，因为链表的内存都是临时申请的，不一定会申请到连续的内存空间。

常用的链表有单向链表和双向链表。这里主要介绍单项链表。

单项链表的组成节点有两部分构成：数据和下一个列表的存储地址。

单节点结构图：

链表结构图：

可以看到每一个节点中的addr都指向下一个节点的地址，phead为整个链表的头节点，不能改变，否则就会找不到整个链表。

python中实现链表首先需要一个类来实现节点对象

"""class Node: 创建链表节点"""class Node:def __init__(self, value, next=None):self.value = valueself.next = next

这个节点类包含两个属性，value和next。value表示当前节点存储的值，nex表示当前节点指向的下一个节点的地址。

链表的操作

空链表的实现

空链表没有任何节点，只包含了一个head地址，因此可以实现如下：

class DataList:def __init__(self):self.head = Node(None)

这样一个链表类就写完了，这个类中目前只包含一个空的头指针，其他方法还没有加上去

链表功能

增

增加链表节点其实都可以用插入节点来统一实现，不管是在头部插入、尾部插入还是中间插入，其本质上都是按index位置来插入值。这里实现尾部插入和按index位置插入两种方法。

尾部插入
  1. 首先要找到链表的尾部在哪里，从上面链表的结构可以看出来最后一个节点的后面是没有节点的，所以最后一个节点的next一定是指向None的，因此可以根据这个特征来找到最后一个节点

p的初始位置为phead，从phead开始遍历

找到尾节点之后p的位置，

然后把新的节点连接在当前p.next上。代码中的while循环就是用来寻找尾节点的。

def append(self, value):"""在链表结尾增加节点"""p = self.headwhile p.next is not None:p = p.nextp.next = Node(value)
根据index插入

原理和尾部插入类似，先遍历链表，找到需要插入的节点位置,然后插入。

def insert(self, value, index=0):"""在index的位置插入value值:param index: 插入位置,默认为0，插入第一个位置:param value: 待插入的值:return:"""p = self.headnode = Node(value)for i in range(index):print("iteration:"+str(i))if p.next is not None:p = p.nextelse:print("index is out of range")returnnode.next = p.nextp.next = node

查找到index的位置的时候，p的位置如下图：

找到index的位置之后如何将新节点插入？

  1. 首先将新节点的next指向原列表的index所在的节点，也就是p.next
  2. 然后将p.next指向新节点

如果第一步和第二步颠倒过来，则会发生节点p之后的所有链表节点都无法寻找，因为唯一的查询依据p.next已经指向了新节点。

删除节点

原理类似，先查找到index的位置，然后将p.next更改为p.next.next，但是这里需要单独注意一下index=0的情况，因为range(0)不会执行循环，因此需要额外考虑

def delete(self, index):"""根据index来删除相应的节点:param index: 需要删除的节点:return:"""p = self.head# 当index ==0 时，range循环不会进行，会导致删除第一个元素失败if index == 0:p.next = p.next.nextreturnfor i in range(index):if p.next is not None:p = p.nextelse:print("index is out of range")returnp.next = p.next.next
修改节点

原理类似，直接上代码

def modify(self, index, value):"""根据index修改对应的value:param index: 需要修改的index:param value: 需要更新的值:return:"""p = self.headfor i in range(index):if p.next is not None:p = p.nextelse:print("index is out of range")returnp.next.value = value

最后附上完整的代码

"""class Node: 创建链表节点"""class Node:def __init__(self, value, next=None):self.value = valueself.next = next"""class DataList:实现链表的增、删、改、查等功能"""class DataList:def __init__(self):self.head = Node(None)def show_all(self):"""显示链表中所有的值"""p = self.headwhile p.next is not None:p = p.nextprint(p.value)def append(self, value):"""在链表结尾增加节点"""p = self.headwhile p.next is not None:p = p.nextp.next = Node(value)def insert(self, value, index=0):"""在index的位置插入value值:param index: 插入位置,默认为0，插入第一个位置:param value: 待插入的值:return:"""p = self.headnode = Node(value)for i in range(index):print("iteration:"+str(i))if p.next is not None:p = p.nextelse:print("index is out of range")returnnode.next = p.nextp.next = nodedef delete(self, index):"""根据index来删除相应的节点:param index: 需要删除的节点:return:"""p = self.head# 当index ==0 时，range循环不会进行，会导致删除第一个元素失败if index == 0:p.next = p.next.nextreturnfor i in range(index):if p.next is not None:p = p.nextelse:print("index is out of range")returnp.next = p.next.nextdef modify(self, index, value):"""根据index修改对应的value:param index: 需要修改的index:param value: 需要更新的值:return:"""p = self.headfor i in range(index):if p.next is not None:p = p.nextelse:print("index is out of range")returnp.next.value = valuedataList = DataList()dataList.append(1)dataList.append(2)dataList.append(3)dataList.append(4)dataList.append(5)dataList.append(6)# dataList.insert(7, 1)# dataList.delete(2)dataList.modify(2, 1000)dataList.show_all()
练习题

将两个单向有序链表进行合并，合并后的链表依然是单向有序链表。

首先分别找到两个链表的head, 定义为:p=l1.head和q= l2.head.next。这里因为是l2合并到l1，所以l2的可以直接找到第一个节点l2.head.next

def merge(l1, l2): p = l1.head q = l2.head.next

然后将l1的第一个节点和l2的第一个节点进行比较，这里新的链表采用降序排列，

  • 若l1 < l2，说明l2的第一个节点要排在l1的第一个节点后面，因此l1节点的位置不动，l2的第一个节点和l1的后续节点比较。
 if p.next.value < q.value: p = p.next

图中l1的第一个节点值为1，l2第一个节点值为2,因此1< 2，所以需要p后移一位：

  • 若l1>= l2,则将l2的节点插入到l1节点后面，插入流程如下图

 t = p.next p.next = q q = t p = p.next

移动后的链表状态入下图：

后面就重复上面的操作，将q的值和p.next的值进行比较，p.next = None，到整个列表末尾。

完整代码为，下代码中 list中导入的包为上面写的Datalist类的文件名称，而非python库中的list列表：

"""合并两个有序链表，要求合并后的链表也是有续链表"""from list import *dataList1 = DataList()dataList2 = DataList()dataList1.append(1)dataList1.append(3)dataList1.append(4)dataList1.append(10)dataList1.append(20)dataList2.append(2)dataList2.append(11)dataList2.append(13)dataList2.append(14)dataList2.append(30)def merge(l1, l2): """ 将有序链表l1和l2进行合并，合并后的链表仍是有序链表 #这里采用的方法是将l2合并到l1中 :param l1: :param l2: :return: """ p = l1.head q = l2.head.next while p.next is not None: if p.next.value < q.value: p = p.next#p向后移动一位 else: """如果p.next 大于等于q , 则将q插入到p的后面，并将p向后移动一位 """ t = p.next p.next = q q = t p = p.next p.next = q# 测试代码dataList1.show_all()dataList2.show_all()print("=====================")merge(dataList1,dataList2)dataList1.show_all()

最后一张合并完之后的图