AC的召唤技术版2026年4月8日题注ACaccepted的缩写意思是通过测试点祝大家信息技术全部ACqwq使用markdown语法进行编辑学习专栏今日话题链表基础来食链表是指将需要处理的数据对象以节点的形式通过指针串联在一起的一种数据结构。啊你问我怎么知道的不懂抄的链表是不能用下标来调用的我们可以把它理解为一个盲人和一个链条盲人只知道他的第一个节点也就是头节点为了找到一个节点就必须从头节点开始摸一直找到要寻找的节点。当然双向链表就另当别论了这个之后有时间再讲吧。这里给一个基本的单向链表的列表存储格式为[元素指针]元素就是内容啦尾节点的指针指向 -1。注意节点在列表中的下标只在使用指针时使用与节点在链表中的位置无关。a[[y,3],[s,0],[a,5],[l,2],[a,-1],[w,4]]head1#头节点下标phead#指针那么很容易就可以得出这个链表是s - y - l - a - w - a -- -1指向 -1 代表链表的结束链表节点的调用敲黑板喽这个东西很重要如果你没有听懂的话之后所有的链表题你都看不懂啦。在上面的链表存储方式中a[p][0]为该节点的元素我们可以通过它来实现对该节点元素的调用a[p][1]则是该节点的指针指向下一个节点在我们的链表存储方式中即为下一个节点在存储列表中的下标。再次重申节点在列表中的下标只在使用指针时使用与节点在链表中的位置无关。并且单向链表的代码中几乎不会涉及链表的长度。除非你想要知道时间复杂度。链表的遍历我们遍历一个链表必须从头节点开始遍历双向链表除外。以下是while循环的版本我们可以通过判断该节点的指针a[p][1]是否等于 -1来判断该节点是否是尾节点如果是尾节点那么就停止循环。以下提供两个版本以下代码结束后 p 是尾节点的下标。a[[y,3],[s,0],[a,5],[l,2],[a,-1],[w,4]]head1#头节点下标phead#指针whilea[p][1]!-1:print(a[p][0])#这里打印出当前遍历的节点可以改成任意的判断与处理语句pa[p][1]print(a[p][0])#这里要注意因为while循环是先判断再执行循环所以如果使用这种while循环的话必须在循环后再执行一次遍历语句以下代码结束后 p 为 -1。a[[y,3],[s,0],[a,5],[l,2],[a,-1],[w,4]]head1#头节点下标phead#指针whilep!-1:print(a[p][0])#这里打印出当前遍历的节点可以改成任意的判断与处理语句pa[p][1]#这一个就不需要再判断了呃呃呃为什么要讲两个呢主要是第一个算是挺常见的在添加和删除单向链表尾节点时会被用到但是很明显第二个相对于第一个很明显码量减少了很多。小贴士在跟同学讲解时有很多人都提出过疑问为什么这里while循环的判断条件为什么是a[p][1]!-1那就让我们来复习一下while循环的知识当while后的条件为真时那么这个循环将会一直执行一直到条件为假时停止循环并且是先判断条件是否成立再执行循环。链表节点的添加从头部插入新节点思路如果从头部插入的话新插入的节点即为新的头节点所以我们需要将新插入的节点所指向的节点下标设为原头节点的下标即为head。在做完这一步骤之后我们还需要将head改成新节点的下标即为len(a)-1不然使下一次遍历时跳过新头节点从原头节点开始遍历。代码如下a[[y,3],[s,0],[a,5],[l,2],[a,-1],[w,4]]head1#头节点下标phead#指针new_datasyh#所需要添加的新节点的元素a.append([new_data,head])#添加新节点headlen(a)-1#改变头指针print(head,a)#打印新节点注意append和改变头指针的不能交换位置。从中间插入新节点思路如果从中间插入的话新插入节点的指针应指向下一个节点并且前一个节点的指针需要指向新节点。代码如下a[[y,3],[s,0],[a,5],[l,2],[a,-1],[w,4]]head1#头节点下标new_datasyh#所需要添加的新节点的元素p3#新节点前的那个节点的坐标a.append([new_data,a[p][1]])a[p][1]len(a)-1print(head,a)从尾部插入新节点思路如果从尾部插入的话我们需要将原来的尾节点的指针指向新节点并且新节点的指针需要指向 -1。代码如下a[[y,3],[s,0],[a,5],[l,2],[a,-1],[w,4]]head1#头节点下标new_datasyh#所需要添加的新节点的元素phead#指针whilea[p][1]!-1:#寻找尾节点pa[p][1]a.append([new_data,a[p][1]])a[p][1]len(a)-1print(head,a)链表节点的删除删除头节点思路我们直接将头指针指向头节点所指向的第二个节点就可以了这样我们遍历链表时就会直接从第二个节点开始遍历。代码如下a[[y,3],[s,0],[a,5],[l,2],[a,-1],[w,4]]head1#头节点下标heada[head][1]#将头指针指向第二个节点print(head,a)删除中间节点思路我们需要将需要删除节点的前一个节点的指针指向需要删除节点的下一个节点这样遍历的时候就会跳过这个节点指向下一个节点。代码如下a[[y,3],[s,0],[a,5],[l,2],[a,-1],[w,4]]head1#头节点下标pre3#需要删除节点的上一个节点的下标pa[pre][1]#需要删除节点的下标通过调取上一个节点的指针实现a[pre][1]a[p][1]#将上一个节点的指针指向下一个节点print(head,a)如果我们想要压缩一下代码量的话就可以这个样子a[[y,3],[s,0],[a,5],[l,2],[a,-1],[w,4]]head1#头节点下标pre3#需要删除节点的上一个节点的下标a[pre][1]a[a[pre][1]][1]#将上一个节点的指针指向下一个节点print(head,a)变式我们在上一段被稍微压缩的代码里面看到了这么一个东西a[a[pre][1]][1]这里的意思就是 pre 指向的节点的下一个节点的指针那么我们动动我们的小脑筋就可以知道a[a[pre][1]]就是 pre 指向的节点的下一个节点以此类推a[a[a[pre][1]][1]]就是 pre 指向的节点的下下个节点总结一下在最外面的 a[] 里面有几个 1 就是 pre 指向的节点之后的第几个节点。删除尾节点思路我们需要寻找到尾节点的前一个节点并将该节点的指针指向 -1这样就会使链表遍历不到尾节点和删除尾节点效果相同。为了实现“寻找到尾节点的的前一个节点”我们就需要使用刚才我们讲到的知识点了通过判断a[a[p][1]][1]是否为 -1 来寻找到尾节点的前一个节点。a[[y,3],[s,0],[a,5],[l,2],[a,-1],[w,4]]head1#头节点下标phead#指针whilea[a[p][1]][1]!-1:#寻找尾节点的前一个节点pa[p][1]a[p][1]-1#将尾节点的前一个节点的指针改为-1print(head,a)例题最后致读者呃呃呃这一刊《AC的召唤》从之前要求到现在才更新完制作周期还是太长了毕竟我只有很少的时间写所以给大家说声抱歉qwq。希望大家能够从《AC的召唤》中学到点东西吧。还有一个链表的运用之后和栈和队列一起更。下期预告栈与队列好啦这一期《AC的召唤》就更到这里啦感谢大家的观看BY HAPPINESS23333