流沙书：https://book.bornforthi.com/zh/column/jysf/Linkedlisttoimplementanunorderedlist/AI悦创博客：https://www.aiyc。top/2009.html大家好，我是九原。上周正式开始数据结构，讲解数组。下面我们来总结一下数组的知识。什么是数组？它是由相同类型的元素集合组成的数据结构，并分配一块连续的内存进行存储。通过元素的索引可以计算出元素对应的存储地址。数组的存储类型是顺序存储：数组顺序存储在内存中是什么样子的？内存是由连续的内存单元组成的，每个内存单元都有自己的地址。在这些存储单元中，有的被其他数据占用，有的空闲。数组中的每个元素都存储在一个小的内存单元中，元素排列紧密。元素的存储顺序不能被打乱，不能跳过某个存储单元进行存储。既然有顺序存储，那么就一定有无序存储？我们今天要介绍的链表就是一种无序存储。链表的使用为什么要学习链表，它的存在有什么作用？上周我们解释了数组。数组的特点是顺序存储，适合查找和修改操作。如果要删除和插入元素，腾出数组元素的位置会花费很多时间。因此，当遇到经常需要删除数据和插入数据的事情时，我们尽量不要优先使用数组来解决此类问题，因为重复使用数组只会增加我们代码的运行时间，这就是实际上对我们没有任何好处。.这时候我们就可以使用链表了。链表主要方便管理不确定长度或数量的数据。频繁插入或删除数据。链表可以轻松做到这一点，而且花费的时间比数组少很多。列表和链表的名称非常相似。他们之间有什么关系吗？List是我们接触python后使用频率最高的数据类型。List非常强大，它为我们提供了很多操作。但其实并不是所有的编程语言都有列表，没有列表的编程语言必须使用其他方法来实现列表的功能。链表可以帮助我们完成链表的实现。列表分为有序列表和无序列表。我们通常经常使用列表。数组可以用来实现有序列表，而链表可以用来实现无序列表。什么是无序列表？让我们从列表的定义开始。列表是元素的集合，每个元素都有一个相对于其他元素的位置。更具体地说，这样的列表称为无序列表。您可以将列表视为具有第一个元素、第二个元素、第三个元素等；您还可以将第一个元素称为列表的开头，将最后一个元素称为列表的结尾。为简单起见，我们假设列表中没有重复元素。什么是链表在计算机科学中，链表是一种常见的基本数据结构。它是一个线性表，但它并不是按线性顺序存储数据，而是在每个节点中存储一个指向下一个节点的指针。效果如图：看似随机的一组数字，可以通过指针连接起来。需要注意的是必须指定第一个元素在链表中的位置。一旦知道第一个元素的位置，就可以使用其中的链接信息访问第二个元素，然后是第三个元素，依此类推。对链表第一个元素的引用称为表头。最后一个元素需要知道它没有下一个元素。使用链表实现无序列表Node类我们上面提到了一个例子，如果存在一个链表，那么我们需要知道它第一个元素的位置，让计算机知道应该从哪里开始寻找元素，并告诉lastelement它没有下一个元素，所以计算机知道停止寻找元素。所以，在实现链表的时候，我们需要知道一个元素的位置，这个元素本身，这个元素指向的下一个元素是什么。只有这样，我们才能顺藤摸瓜找到下一个元素。合在一起，它们被称为节点。节点是构建链表的基本数据结构。每个节点必须包含两种内容。首先，节点必须包含要生成的链表的元素，我们称之为节点的数据变量。其次，一个节点必须持有对下一个节点的引用。在构建节点时，需要为其提供一个初始值。执行下面的赋值语句会生成一个包含数据值20的节点对象。temp=Node(20)temp.getData()#20Node类还包含访问和修改数据的方法，以及对下一个元素的引用。类节点：def__init__(self,initdata):self.data=initdataself.next=NonedefgetData(self):returnself.datadefgetNext(self):returnself.nextdefsetData(self,newdata):self.data=newdatadefsetNext(self,newnext):self.next=newnext分析python代码：我们定义了一个Node类，那么我们需要一个初始化方法__init__，它定义了一个数据元素来存放节点数据，同时也定义了一个next元素，用于指向下一个节点。next的值默认初始化为None，引用None表示该元素之后没有其他元素。getData方法主要用于获取当前节点的数据。getNext用于告诉用户链表当前节点指向的下一个节点是什么。setData方法主要用于修改当前节点的数据，传入一个新的数据（newdata），然后赋值给该节点的原始数据，这样当前节点的数据内容修改成功。setNext方法主要用于插入新节点。当我们在当前节点后面插入一个新节点时，需要告诉当前节点后面有一个新节点，所以self.next=newnext。无序列表类从上面我们可以看出，节点是无序列表的组成元素之一。每个节点通过显式引用指向下一个节点。只要知道第一个节点的位置，就可以通过下一个引用找到后续的每个元素。因此，无序列表类必须包含对第一个节点的引用。无序列表类的定义方法如下：classUnorderedList:def__init__(self):self.head=None解释一下python代码：无序列表类的生成方法包括一行代码，self.head=None表示默认序列表的头节点为空，不指向任何元素。所以我们可以想一下，当我们定义一个无序列表时，判断一个无序列表是否为空，只需要知道它的头节点是否指向空即可。我们可以用这个来扩展判断无序列表是否为空的方法头节点必须有指向别处元素的点。如果头节点为空，则表示列表只有这么长。现在我们已经做好了充分的准备，也就是知道了无序列表是怎么定义的，我们也可以使用isEmpty方法来判断里面是否有元素。我们现在要做的就是添加、修改和查询我们新创建的无序列表。Add方法想要生成一个无序列表，我们首先要向它添加元素，然后我们需要实现add方法。但是在实现之前，需要考虑一个问题：新元素应该放在哪里？这个问题是不是似曾相识？在关于数组的章节中，我们考虑了很多情况。在末尾、开头和中间添加新元素，尤其是向数组中间插入元素，处理起来非常费力。插入一个元素，剩下的很多元素都是为它腾出空间。但是现在我们实现的列表是无序的，所以新元素相对于现有元素的位置并不重要。新元素可以在任何地方。因此，将新元素放在最方便的地方是最有意义的。这里我们首先考虑插入到列表头部的元素。defadd(self):temp=Node(data)temp.getNext(self.head)self.head=temp代码解释：要向列表中添加新元素，首先要记住列表的单位是节点，要成功插入一个元素，首先我们需要生成一个包含这个元素的节点，所以我们使用Node(data)，生成一个包含要插入的元素数据的节点，并赋值给temp，这样这个节点的新名字是温度。如果要将临时节点添加到列表的头部，首先我们需要让临时节点找到头节点。我知道，就算你说你是head节点，如果你后面没有team，也不算加入listteam，所以有temp.getNext(self.head)，你已经找到head了ofthelistyouwanttojoin从现在开始，你可以名正言顺地成为第一名，所以通过这行代码self.head=temp，你被命名为列表的头。length方法我们在链表中添加多个节点后，想要计算当前链表的长度，引入length方法进行处理。我们的具体做法是使用外部引用从链表的头节点开始访问。当访问到每个节点时，根据每个节点的指针找到下一个节点，依此类推，最终计算出链表的长度。deflength(self):current=self.headcnt=0whilecurrent!=None:cnt=cnt+1current=current.getNext()returncnt代码解释：我们使用一个叫做current的外部引用，让它从中读取链表的头部开始访问，然后引入一个计数器cnt来统计节点数。之后，我们需要做的就是找出current指向的节点是否为空。如果指向的节点不为空，说明这个节点后面还有其他节点，计数器加1，以此类推，直到current指向的节点为空，提示没有其他节点在这个节点之后，我们已经到达列表的末尾，所以我们将返回计数器的数量。查找方法既然我们可以计算出列表的长度，那我们能不能找到列表中的元素呢？当然，实现的基本思路和length方法很相似。我们只需要添加一个boolean类型的变量found来表示是否找到了我们要找的元素。defsearch(self,item):current=self.headfound=Falsewhilecurrent!=Noneandnotfound:ifcurrent.getData()==item:found=Trueelse:current=current.getNext()返回找到与长度方法类似，遍历从列表的头部开始。我们使用布尔变量found来标记是否找到了所需的元素。默认情况下，我们一开始没有找到元素，found的值为False。我们在遍历链表时，使用getData方法获取判断节点元素。如果获取到的元素和我们要找的元素item一样，就告诉found找到了元素item，所以found=True，如果通过getData方法获取到的元素和item不一样，那么就继续查找下一个节点，直到该节点的元素与item相同，如果我们遍历遍历，如果整个列表都没有找到item元素，那么我们最终会返回found的默认值，即False。remove方法我们使用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方法：defremove(self,item):cur=self.headpre=Nonefound=Falsewhilenotfound:ifcur.getData()==item:found=Trueelse:pre=curcur=cur.getNext()ifpre==None:self.head=current.getNext()else:pre.setNext(cur,getNext())代码解释：先问一个问题：这段代码为什么要引入pre变量，它有什么特殊的用法吗？当我们使用循环遍历元素找到要删除的节点时，cur已经指向了要删除的节点。还记得我们刚才说的吗？要删除这个节点，我们需要将这个节点（它的前邻居）前面的节点指向它后面的节点（它的后邻居），忽略这个节点，达到删除这个节点的效果，而我们的节点类defined之后，getNext()方法就没有任何查找上一个节点的方法了，所以我们不能仅仅通过变量cur来完成删除操作。为了解决这个问题，我们引入了一个新的变量pre，cur和之前一样，标记当前在链表中的位置。新的引用pre总是指向cur访问的最后一个节点。这样当cur指向待删除节点时，pre正好指向待删除节点的“前邻居”，可以起到修改前一个节点指向的作用。搜索过程结束后，需要执行删除操作。删除操作包括以下两种情况：删除头节点和删除其他节点。如果要删除的元素恰好是链表头节点包含的元素，那么cur会指向头节点，pre仍然是它的默认值None。这种情况下，我们只需要修改cur，告诉它的头结点成为后面的结点，而不是自己，不需要修改pre的值。如果pre的值不为None，则表示要移除的节点在链表结构中的某处。在这种情况下，pre指向需要修改下一个引用的节点。我们在pre上使用setNext()方法修改节点的指向操作，也就是说pre的下一个节点会指向cur的下一个节点，而不是指向cur本身，修改指向删除cur的效果.如果是删除最后一个节点，我们应该告诉倒数第二个节点，它的下一个节点为空，即倒数第二个节点的点为None。总结恭喜你，你又完成了对数据结构类型的学习。在这篇文章中，我主要通过实现一个无序列表来详细讲解链表的操作。至于为什么不单独说明链表，主要是python的底层代码很强大。它结合了数组和链表来实现列表。数组和链表其实就是列表实现的本质。没有这两种数据结构类型，列表将不存在。.在我们平时的python使用中，一般都是比较常用到列表的，所以我们借用列表来介绍一下它的本质之一，链表。流沙团队推出辅导班，包括“Python语言辅导班、C++辅导班、java辅导班、算法/数据结构辅导班、少儿编程、pygame游戏开发”，全部为一对一教学：一对一-一对一辅导+一对一问答+作业布置+项目实践等。当然还有线下和线上的摄影课程，Photoshop，Premiere一对一教学，QQ，微信在线，随时回复时间！方式一：QQ(opensnewwindow)方式二：微信：Jiabcdefh
