当前位置：首页 > news >正文

数据结构--------单链表下

news 2026/5/15 6:47:06

书接上回，本章主要讲的是单链表的头删，尾删，指定位置插入删除，链表的查找和链表的销毁；

一.链表的操作

1.头删

文字描述如下：正所谓头删，删除的肯定是链表的头元素，但是我们要怎么样进行操作呢？首先在删除之前我们肯定要断言一下传过来的链表的地址是不为空的以及链表也是不能为空的：代码语言：assertI（pphead&&*pphead）；然后我们要头删，删除的是头结点的元素，我们在删除之前肯定是要定义一个next指针，其数据类型应该是SLTNode*,next指针指向的头结点的下一个结点；代码语言：SLTNode* next = (*pphead)->next;(注意这里的括号是不能省略的，因为->操作符的优先级高于*)，保存好之后我们就可以free(*pphead)这个头结点了，再将next指针指向的结点成为新的头结点；代码语言：*pphead=next；画个图再熟悉一下这个代码！

这里存储数据数据1的结点为刚开始的头结点，存储数据2的结点为头结点的next结点，按照文字描述走一遍，存储数据2的结点变为新的头结点，存储数据3的结点变为next结点；

代码：

上述是分析多个结点，接下来我们分析只存在一个结点的时候。同样我们画图分析：

上述的描述同样适用！说到这里我们的头删就讲完了！

2.尾删

文字描述：同样的尾删删除的则是链表尾结点的数据，同样的分成链表当中存在多个结点或者只有一个结点。同样的在进行操作之前我们还是要断言传过来的链表的地址是不为空的以及链表也是不能为空的：代码语言：assertI（pphead&&*pphead）；接下来我们要找尾结点，定义一个ptail指针起初它指向头结点以及一个prev指针指向空，SLTNode* prev=NULL，SLTNode* ptail = *pphead；遍历这个ptail指针让他找尾，当ptail找到尾的时候prev也找到ptail之前的结点；先将prev的next指针置为空，再将ptail指针free掉；画图理解一下吧：

按照上述的文字描述即可实现尾删的操作了！代码如下：

当链表中只有一个结点的时候我们就不能按照多个结点的方式来尾删了，画图理解：

当只有一个结点的时候(*pphead==NULL)，我们直接手动free(*pphead)，之后再手动将*pphead置为空(*pphead=NULL)！

3.查找指定位置的结点

文字描述：首先我们创建一个pcur指针指向头结点（SLTNode*pcur=*pphead），接下来遍历整个链表即while（pcur）也就是pcur！=NULL指针的时候进入循环条件，判断pcur->data==x；等于则说明我们找到了要查找的指定位置，返回指定位置即可也就是pcur。若找不到，我们返回NULL。画图理解：

代码：

4.指定pos位置之前插入数据

文字描述：指定位置之前插入数据，同样的我们在开始操作的时候首先要断言传过去的pphead不能为空，以及pos指针不能为空即assert（pphead&&pos）（pphead!=NULL && pos!=NULL）。首先我们判断pos所在的位置，如果pos在第一个结点的位置那么就是头插，我们直接调用头插的函数代码，如果pos不在第一个结点的位置，找pos前一个结点，创建一个prev指针让其找到pos结点，我们根据数据x申请一个结点大小的空间称为newnode。当找到prev和pos结点的时候，让prev的next指针指向newnode，再让newnode的next指针指向pos。

先定义一个遍历指针从头结点开始往后走，找到指定位置的前驱结点。
动态开辟新结点，给新结点的数据域赋值。
让新结点的 next 指针指向原来指定位置的结点。
让前驱结点的 next 指针指向这个新结点。
插入完成，链表链接关系重构完毕

画图理解：

代码：

5.指定pos位置之后插入数据

文字描述：指定pos位置之后插入数据，同样的我们在开始操作的时候首先要断言传过去的pphead不能为空，以及pos指针不能为空即assert（pphead&&pos）（pphead!=NULL &&pos!=NULL）。我们创建一个newnoed结点存储x数据，然后找到pos以及pos->next结点。这里的插入顺序是有先后之分的：我们先将newnode->next指向pos->next指针指向的位置，其次将pos->next指向newnode；看直观的图像吧！代码：

6.删除指定pos位置的数据

文字描述：同样的我们在开始操作的时候首先要断言传过去的pphead不能为空，以及pos指针不能为空即assert（pphead&&pos）（pphead!=NULL &&pos!=NULL）。分为三种情况，当pos在头结点和尾结点之间的时候与pos在尾结点的时候，创建pcur变量，遍历链表当pcur->next==pos跳出循环，找到pcur，pos->next以及pos结点。先让prev->next指针指向pos->next指针然后free(pos)结点，再将其置为空。当pos为头结点的时候之间使用上面编译好的头删的函数。

先判断链表是否为空，若为空，直接结束操作。
定义遍历指针，从头节点开始遍历，找到pos 位置的前驱节点。
用临时指针保存要删除的 pos 位置节点。
让前驱节点的 next 指针，指向被删节点的下一个节点。
释放被删除节点的内存，防止内存泄漏。
删除完成，链表节点链接重新连通。

图像理解：

代码：

7.删除pos之后的数据

文字描述：首先还是断言判空！同样的我们在开始操作的时候首先要断言传过去的pphead不能为空，以及pos指针不能为空即assert（pphead&&pos）（pphead!=NULL &&pos!=NULL）。我们可以思考一下当删除pos之后的结点的时候受到影响的结点应该有三个！一个是pos结点，pos->next结点，pos->next->next结点，这三个结点。所以我们先创建一个del指针指向pos->next，那么del->next指针也就是pos->next->next。我们直接free（del）之前，先将pos->next指针指向del->next然后再free(del)，再将del置为NULL；

代码：8.链表的销毁

这个销毁函数的核心逻辑，就是用 pcur 遍历每个结点，用 next 存好下一个结点的地址，
释放当前结点后再移动游标，最后把外面的头指针置空，全程保证不会丢失结点地址，也不会访问非法内存。

代码：