继续分享嵌入式技术，操作系统，算法，c语言/python等。，欢迎您的关注和支持。
在上一篇文章中，我们谈到了链表的基本概念和一些搜索和遍历的方法。在本文中，我们将主要讨论插入和删除链表的操作以及如何通过堆栈来创建链表。
链表的插入
首先，我们来看看如何插入链表。
要在单链表中第i个数据元素之前插入一个数据元素，需要先在单链表中找到第i-1个节点并用指针pre指示，然后申请一个新的节点并用指针p指示，让p节点的指针字段指向第i个节点，然后修改第i-1个节点的指针指向s。
算法描述:
p=(节点*)malloc(sizeof(节点))；/*分配空*/p-& gt；info = x；/*设置新节点*/p-& gt；next = q-& gt；接下来；q->；next = p；注意，它必须是p-& gt；next = q-& gt；接下来；然后q->；next = p；两者的顺序不能颠倒。
为什么这个留给大家去思考。
链表的插入根据插入位置的不同分为头插入、尾插入和中间插入，不同位置的插入方式也不同。以下是插入操作的逻辑伪代码，供大家理解。
1.工作指针q =空初始化；
2.找到第i-1个节点，使工作指针q指向它；
3.如果搜索不成功，我！=1，插入位置不合理，输出位置不合理；否则，
生成元素值为x的新节点p；
判断插入位置是表头还是非表头。
如果是头，将新节点p插入头中，p作为新头；否则，在节点q之后插入新的节点p
4.返回到新标题。
代码实现:
node *insert(节点head,datatype x，int i) { node *p，* q；q= findkth(head，i-1)；/*找到第i个节点*/ if(！q & &我！= 1)printf(& # 34；\ n找不到节点%d。无法插入%d！"，i-1，x)；else { p =(node *)malloc(sizeof(node))；/*分配空*/p-& gt；info = x；/*设置新节点*/ if(i==1){ /*插入的节点是单链表的第一个节点*/p-& gt；下一个=头；/* insert(1)*/head = p；/* insert(2)*/} else { p-& gt；next = q-& gt；接下来；/* insert (1)*/ q->next = p；/* insert (2)*/}}返回头；}注意:
在上面i=1的情况下，我这里所陈述的是没有前导节点的链表的插入逻辑。
p->；下一个=头；/* insert(1)*/head = p；/* insert (2)*/带有前导节点的链表与此操作略有不同。我们先来看看有表头和无表头的区别。
首先不带表头的链表我们的head结点直接就表示的是头结点，head就表示头结点。而带头结点的链表实在head和头结点之间有追加了一个结点，用head->next来指向头结点
带头结点的链表前导节点的链表
不带头结点的链表没有头节点的链表
以上两张图就是两者的区别。
那么，了解了这个区别之后，如何实现前导节点的头插入，其实很简单。
p->；next = head-& gt；接下来；/* insert(1)*/head–>；next = p；/*插入(2)*/有没有发现头插和中插、尾插的方式是一样的？
链表的删除
要删除单链表中的第i个节点，必须先通过计数找到第i-1个节点，并使pre指向第i个节点的下一个，然后删除第i个节点，释放node 空。
算法描述:
p=pre->接下来；pre->；next = p-& gt；接下来；免费(p)；上面第二步也可以写成pre->next = pre-& gt；下一个-& gt；接下来；就是不好看。它的结构是一样的。
上面说的插入分为头插和尾插，同样的删除也可以。我们先来看看他们的逻辑伪代码，让大家看得懂。
1:工作指针pre=null初始化；
2.判断单链表是否为空，返回head，函数结束；
3:如果i=1，直接删除第一个节点，返回head，函数结束；
4.找到第i-1个节点，使工作指针pre指向该节点；
5:如果pre不存在或pre->next不存在，表示删除位置错误，函数在head返回时结束；
否则，
5.1将删除的节点临时存储在p中；
5.2解链，即将节点pre的后继节点从链表中移除；
5.3释放被删除的节点p；
5.4回到头部；；
代码实现:
链表deleone(链表头，int i) {node *pre=null，* p；if(head = = null){ printf(& # 34；单链表是空\ n & # 34；);回程头；//单链表是空} if (i == 1) {/*是要删除的表的第一个节点*/p = head；/*p指向第一个节点*/head = head-& gt；接下来；/* delete */ free(p)从链表中删除；/*释放被删除的节点*/返回头；} pre= findkth(head，i-1)；/*pre是第i个节点的前任*/if(pre = = null | | pre-& gt；next == null) {printf(“节点%d不存在”，i)；回程头；} else { p = pre-& gt；接下来；pre->；next = p-& gt；接下来；免费(p)；回程头；}上面同样的代码表示没有前导节点的操作。如果是领导节点链表，操作起来相对简单，因为领导节点链表删除的是头节点和尾节点，中间节点的方法是一样的，不需要对i-1的分支做特殊处理。
首节点的头删除操作如下:
p=pre->接下来；pre->；next = p-& gt；接下来；免费(p)；好了，先分享到这里。下一篇文章将分享如何创建链表，以及如何通过堆叠来实现。
如果你觉得文章对你有帮助，请喜欢并关注。如有错误，请指正。
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文链接：https://www.andon8.com/394050.html