关于python:04久远讲算法链表实现无序列表

流沙 book：https://book.bornforthi.com/zh/column/jysf/Linkedlisttoimplementanunorderedlist/

AI 悦创博客：https://www.aiyc.top/2009.html

你好，我是长远，上周开始咱们算是正式入门了数据结构，进行了数组的解说。

咱们当初来总结回顾一下数组的常识。

数组是什么？

是由雷同类型的元素的汇合所组成的数据结构，调配一块间断的内存来存储。利用元素的索引（index）能够计算出该元素对应的存储地址。

数组的贮存类型

顺序存储：数组在内存中的顺序存储，具体是什么样子呢？

内存是由一个个间断的内存单元组成的，每一个内存单元都有本人的地址。在这些内存单元中，有些被他数据占用了，有些是闲暇的。

数组中的每一个元素，都存储在小小的内存单元中，并且元素之间严密排列，既不能打乱元素的存储程序，也不能跳过某个存储单元进行存储。

既然有顺序存储，那么肯定就有无序存储咯？咱们明天要介绍的链表便是无序存储的类型。

咱们为什么要学链表，它的存在又有什么作用呢？

上周咱们解说到数组，数组的特点便是顺序存储，实用于查找和批改操作，如果要进行删除和插入元素的操作的时候，数组元素腾地位这件事就要破费不少工夫，因而遇到一些常常要删除数据，插入数据的事件的时候，咱们尽量不优先思考用数组去解决这类问题，因为这样重复的应用数组，只会减少咱们代码的运行工夫，对咱们其实是没什么益处的。

这种时候咱们就能够应用链表了，链表次要是便于管理长度或数量不确定的数据，常常插入或者删除数据，链表轻而易举就能做到这些，破费的工夫绝对于数组少很多。

列表和链表名字很像，它们之间有什么关系么？

列表是咱们接触 python 当前，最常常用到的数据类型，列表十分的弱小，它为咱们提供了很多操作。然而其实不是所有的编程语言都有列表的，而没有列表的编程语言，就要通过别的形式去实现列表的性能。链表便能够帮忙咱们实现列表的实现。

而列表又分为有序列表和无序列表，咱们平时是十分常见列表的，数组就能够用来实现有序列表，而链表则用来实现无序列表。

无序列表是什么？

先从列表的定义来剖析，列表是元素的汇合，其中每一个元素都有一个绝对于其余元素的地位。更具体地说，这种列表称为无序列表。能够认为列表有第一个元素、第二个元素、第三个元素，等等；也能够称第一个元素为列表的终点，称最初一个元素为列表的起点。为简略起见，咱们假如列表中没有反复元素。

在计算机科学中，链表是一种常见的根底数据结构，是一种线性表，然而并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。成果如图：

看似随便的一组数字，通过指针能够将它们进行连贯。

须要留神的是，必须指明链表中第一个元素的地位。一旦晓得第一个元素的地位，就能依据
其中的链接信息拜访第二个元素，接着拜访第三个元素，依此类推。指向链表第一个元素的援用被称作头。最初一个元素须要晓得本人没有下一个元素。

上文咱们提到了一个例子，一个链表如果存在，那么咱们须要晓得它第一个元素的地位，让计算机分明它应该从哪里开始寻找元素，还要通知最初一个元素它没有下一个元素，让计算机懂得进行寻找元素。因而在实现链表时，咱们须要晓得一个元素的地位，以及元素本身，以及这个元素指向的下一个元素是什么，只有这样咱们能力顺藤摸瓜找到接下来的元素嘛，咱们将这一系列所需的货色合在一起，称作节点。

节点是构建链表的根本数据结构。每一个节点都必须蕴含有两种内容。首先，节点必须蕴含要生成的链表的元素，咱们称之为节点的数据变量。其次，节点必须保留指向下一个节点的援用。
在构建节点时，须要为其提供初始值。执行上面的赋值语句会生成一个蕴含数据值 20 的节点对象。

temp = Node(20) 
temp.getData()
#20

Node 类也蕴含拜访和批改数据的办法，以及指向下一个元素的援用。


class Node:
    def __init__(self,initdata):
        self.data = initdata
        self.next = None
    
    def getData(self):
        return self.data
    
    def getNext(self):
        return self.next
    
    def setData(self,newdata):
        self.data = newdata
        
    def setNext(self,newnext):
        self.next = newnext

对 python 代码进行剖析：

咱们定义一个 Node 类，那就须要有初始化办法__init__，其中定义了一个 data 元素，用来寄存节点的数据，又定义了一个 next 元素，用来指向下一个节点。next 的值默认初始化为 None，指向 None 的援用代表着该元素前面没有其余元素。

getData 办法次要是用于获取以后节点的数据。

getNext 用于通知使用者该链表以后节点指向的下一节点是什么。

setData 办法次要用于批改以后节点的数据，传入一个新的数据（newdata），而后将其赋值给节点的原数据，这样，以后节点的数据内容就批改胜利啦。

setNext 办法次要用于插入新节点，当咱们在以后节点的前面插入一个新的节点得时候，要通知以后节点它的前面有了新的节点，所以才有了 self.next = newnext。

由上文可知，节点是无序列表的形成因素之一。每一个节点都通过显式的援用指向下一个节点。只有晓得第一个节点的地位，其后的每一个元素都能通过下一个援用找到。因而，无序列表类必须蕴含指向第一个节点的援用。

无序列表类的定义方法如下：

class UnorderedList: 
     def __init__(self): 
         self.head = None

对 python 代码进行解说：

无序列表类的生成办法包含有一行代码，self.head = None 即默认该无序列表的头节点为空，不指向任何元素。

因而咱们能够加以思考，当咱们定义一个无序列表时，判断一个无序列表是否为空，咱们只须要晓得它的头节点是不是指向空就能够了。咱们能够以此延长出判断无序列表是否为空的办法 isEmpty().

def isEmpty(self):
        return self.head == None

仅仅一行代码，如果头节点不为空，那则阐明头节点必然有指向别处的元素，如果头节点为空那阐明这个列表只有这么长。

当初咱们曾经做好了十足的后期筹备了，即晓得了无序列表是怎么定义的，也能够通过 isEmpty 办法来判断它其中是否有元素了。当初要做的便是对咱们新建的无序列表进行增上改查操作了。

想生成一个无序列表，咱们首先要向其中增加元素，那么咱们就须要实现 add 办法。但在实现之前，须要思考一个问题：新元素要被放在哪个地位？

这个问题是否似曾相识？在数组章节中，咱们思考了很多状况，在开端，在结尾，在两头退出新的元素，尤其是将元素插入到数组两头，解决起来十分的吃力，插入一个元素，剩下的不少元素都要为它腾出地位。然而当初咱们要实现的列表是无序的，因而新元素绝对于已有元素的地位并不重要。新的元素能够在任意地位。因而，将新元素放在最简便的地位是最正当的抉择。这里咱们首先思考元素在列表头部插入。

def add(self):
        temp = Node(data)
        temp.getNext(self.head)
        self.head = temp

代码解说：

要向列表中退出新的元素，咱们首先要记起，列表的组成单位为节点，想要胜利插入一个元素，首先咱们要生成一个蕴含有此元素的节点，因而咱们应用了 Node(data)，生成了一个蕴含有要插入的元素 data 的节点，并将其赋值给 temp，以此这个节点的新名字就叫 temp 了，temp 节点想要退出到列表的首部，首先咱们要让 temp 节点找到头节点，这样子才有说服力，如果连本人想要退出的列表队伍的首部都不意识，就算你说你是头节点了，你的后边没有队伍，也不算是退出到列表队伍中啊，因而才有了 temp.getNext(self.head) , 你找到了你要退出的列表的首部当前，你就能够名正言顺的成为第一名了，因而通过 self.head = temp 这行代码，你被冠名了列表首部这个名字。

咱们向列表中增加多个节点之后，想要计算以后列表的长度，咱们引入 length 办法进行解决。

咱们的具体做法是用一个内部援用从列表的头节点开始拜访。随着拜访每一个节点，而后依据每个节点的指针指向去寻找下一个节点，以此类推最初计算出列表的长度。

def length(self):
        current = self.head
        cnt = 0
        while current != None:
            cnt = cnt + 1
            current = current.getNext()
            
        return cnt

代码解说：

咱们应用了一个叫做 current 的内部援用，让它从列表的头部开始进行拜访，而后又引入了一个计数器 cnt，用来计算节点的个数，之后咱们要做的便是，寻找 current 所指向的节点是否为空，如果指向的节点不为空，则阐明该节点前面还有另外的节点存在，计数器加 1，如此循环直到 current 指向的节点为空，这就在揭示咱们，该节点后没有别的节点了，曾经到了列表的尾部，因而咱们将返回计数器的个数即可。

既然咱们能对列表的长度进行计算，那么咱们能不能查找列表中的元素呢？当然能够，实现的基本思路和 length 办法是十分类似的，咱们只须要退出一个 boolean 类型的变量 found 来示意咱们是否找到了咱们要查找的那个元素即可。

def search(self,item):
        current  = self.head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
        return found

与在 length 办法中类似，遍历从列表的头部开始。咱们应用布尔型变量 found 来标记是否找到所需的元素。默认一开始咱们没有找到元素，found 的值为 False，当咱们对列表进行遍历时，咱们应用 getData 办法来进行判断节点元素的获取，如果获取到的元素和咱们要查找的元素 item 雷同，咱们就通知 found，咱们找到了 item 这个元素，因而有 found = True，如果通过 getData 办法获取到的元素与 item 不同，那么咱们就持续寻找下一个节点，直到节点的元素与 item 雷同为止，如果咱们找遍了整个列表都没有找到 item 元素，那咱们最终就要返回 found 的默认值了，即为 False。

咱们通过 remove 办法来进行列表元素的删除。要删除列表中的某个元素，咱们是否要思考先找到这个元素咱们能力对其进行删除操作呢，因而其实 remove 办法和 search 办法也是非常相像的，咱们首先要应用 search 办法找到咱们要删除的元素，而后对其进行删除即可。然而删除具体要怎么删除呢？咱们回到最后的那副图片。假如我要删除 21 这个节点，以咱们失常的思维去想的话，间接去掉 21 不就好了么！然而这会呈现一个问题，那便是，34 自身是指向 21 的，而 21 又指向了 56，唐突的把 21 删掉的话，34 又要指向哪里呢？56 也没有被指向的对象了，整个列表就从 21 这里断开了！咱们不能因为一个元素的删除，就使得整个列表因而作废，因而咱们要思考，如果删除 21 的同时，又使得列表持续存在。

这时，咱们就能够思考，如果我把 21 删掉了的话，34 和 56 岂不是前后街坊了？那这样的话，我间接让 34 忽视 21，转而指向 56 不就能够了，又因为列表的长度是通过节点指向进行计算的嘛，只有没有节点指向 21，就相当于 21 不存在于列表中，从而达到了 21 被删除的成果。

利用代码来实现 remove 办法：

def remove(self,item):
        cur = self.head
        pre = None
        found = False
        while not found :
            if cur.getData() == item:
                found = True
            else:
                pre = cur
                cur = cur.getNext()
                
        if pre == None:
            self.head = current.getNext()
        else:
            pre.setNext(cur,getNext())

代码解说：

先提出一个问题：为什么这段代码里引入了 pre 变量，它有什么非凡的用法么？

当咱们应用循环进行元素遍历时，查找到要删除的节点时，cur 曾经指向了要被删除的节点，还记得咱们刚刚说的么？要删除这个节点，咱们就要将这个节点后面的节点（它的前街坊）指向它前面的节点（它的后街坊），忽视该节点，达到删除该节点的成果，而咱们定义的节点类外面之后 getNext() 办法，没有任何对于查找前节点的办法，因而咱们只通过 cur 这一个变量，是无奈实现删除操作的。为了解决这一问题，咱们引入了一个新的变量 pre，cur 与之前一样，标记在链表中的以后地位。新的援用 pre 总是指向 cur 上一次拜访的节点。这样一来，当
cur 指向须要被移除的节点时，pre 正好指向要删除节点的“前街坊”，能够起到批改前节点指向的作用。

一旦搜寻过程完结，就须要执行删除操作。而删除操作又包含有以下两种状况：删除头节点，删除其余节点。

如果被删除的元素正好是链表的头节点所蕴含的元素的话，那么 cur 会指向头节点，而 pre 则仍旧为它的默认值 None，在这种状况下，咱们只须要批改 cur 即可，通知它头节点变成了它前面那个节点，而不再是它自身就能够了，无需批改 pre 的值。

如果 pre 的值不是 None，则阐明须要移除的节点在链表构造中的某个地位。在这种状况下，pre 指向了 next 援用须要被批改的节点。咱们对 pre 进行 setNext() 办法来进行节点的指向批改操作，这将意味着，pre 的下一个节点将指向 cur 的下一个节点，而不再是指向 cur 自身了，修了指向，从而起到了删除 cur 的成果。

如果是删除最初的节点，咱们应该通知倒数第二个节点，它的下一个节点为空，即倒数第二个节点的指向为 None。

祝贺你，又实现了一个数据结构类型的学习，在本次的文章中，我次要通过实现无序列表的形式来对链表的操作进行了具体的解说，至于为什么不独自进行链表的解说，最次要还是因为 python 底层的代码写的十分的弱小，它将数组和链表联合在一起进而实现了列表，数组和链表其实就是列表实现的实质，没有这两个数据结构类型，列表便不会存在。咱们平时的 python 应用中，个别都更罕用列表，因而咱们以列表为由，引出了它的实质之一，链表。

流沙团队推出辅导班啦，包含「Python 语言辅导班、C++ 辅导班、java 辅导班、算法 / 数据结构辅导班、少儿编程、pygame 游戏开发」，全部都是一对一教学：一对一辅导 + 一对一答疑 + 安排作业 + 我的项目实际等。当然，还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线，随时响应！

办法一：QQ (opens new window)

办法二：微信：Jiabcdefh

关于python:04久远讲算法链表实现无序列表

链表的应用

什么是链表

应用链表实现无序列表

Node 类

无序列表类

Add 办法

length 办法

Search 办法

remove 办法

总结