Python 数据库——链表

基本概念

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

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

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

单节点结构图：

链表结构图：

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

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

"""class Node: 创建链表节点"""class Node:    def __init__(self, value, next=None):        self.value = value        self.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.head        while p.next is not None:            p = p.next        p.next = Node(value)

根据index插入

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

    def insert(self, value, index=0):        """            在index的位置插入value值        :param index: 插入位置,默认为0，插入第一个位置        :param value: 待插入的值        :return:        """        p = self.head        node = Node(value)        for i in range(index):            print("iteration:"+str(i))            if p.next is not None:                p = p.next            else:                print("index is out of range")                return        node.next = p.next        p.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.next            return        for i in range(index):            if p.next is not None:                p = p.next            else:                print("index is out of range")                return        p.next = p.next.next

修改节点

原理类似，直接上代码

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

最后附上完整的代码

"""class Node: 创建链表节点"""class Node:    def __init__(self, value, next=None):        self.value = value        self.next = next"""class DataList:实现链表的增、删、改、查等功能"""class DataList:    def __init__(self):        self.head = Node(None)    def show_all(self):        """        显示链表中所有的值        """        p = self.head        while p.next is not None:            p = p.next            print(p.value)    def append(self, value):        """        在链表结尾增加节点        """        p = self.head        while p.next is not None:            p = p.next        p.next = Node(value)    def insert(self, value, index=0):        """            在index的位置插入value值        :param index: 插入位置,默认为0，插入第一个位置        :param value: 待插入的值        :return:        """        p = self.head        node = Node(value)        for i in range(index):            print("iteration:"+str(i))            if p.next is not None:                p = p.next            else:                print("index is out of range")                return        node.next = p.next        p.next = node    def delete(self, index):        """        根据index来删除相应的节点        :param index: 需要删除的节点        :return:        """        p = self.head        # 当index ==0 时，range循环不会进行，会导致删除第一个元素失败        if index == 0:            p.next = p.next.next            return        for i in range(index):            if p.next is not None:                p = p.next            else:                print("index is out of range")                return        p.next = p.next.next    def modify(self, index, value):        """        根据index修改对应的value        :param index: 需要修改的index        :param value: 需要更新的值        :return:        """        p = self.head        for i in range(index):            if p.next is not None:                p = p.next            else:                print("index is out of range")                return        p.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 if p.next.value

  图中l1的第一个节点值为1，l2第一个节点值为2,因此1

  • 若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  
    最后一张合并完之后的图