当前位置:   article > 正文

向双向链表/单向链表中的结点P后插入一个新的结点new_new一个新节点

new一个新节点

一、向双向链表中插入新节点new

关于双向链表的插入问题,有些地方需要特别理解一下,有一个原则就是不能将原始链表弄丢,所以在断开原始连接之前,我们应该先要将即将断开部分的前后连接保存下来,也就是链表插入的第一步,将new的后继指向原始链表的中P的下一个结点。然后,将new的前驱指向P结点,这样就保证了链表的前后部分不丢失。然后是第三步,将P结点的后继指向新增结点new,最后,将原始结点P的下一个结点的前驱指向新加结点new, s->next->prior在其实就是等价于new结点插入之前的p->next->prior,假设原始链表中P的下一个结点为x,则也等价于x->prior。这样四步就将新节点new插入到了双向链表的结点P和x之间了。

具体操作如下四步:

  1. new->next=p->next;

  2. new->prior=p;

  3. p->next=new;

  4. new->next->prior=new;

总体来讲,要将新节点new嵌入到双向链表中,需要切断并重新连接两根线,还要再额外连两根线,总共动了四根线,所以需要四条语句来做插入。

二、向单向链表中插入新节点new
单向链表的插入原则和双向链表的原则是一样的,就是首先要确保断开之后的链表不会丢失,所以要先将P后的结点连接上。另外需要注意的是,在插入过程中,我们是不知道P后的结点的指针的,只能通过p->next去查找,如果先执行下面的第二步操作,就相当于将链表的P结点的后面部分丢失。

具体只要两步:

1.new->next=p->next;

2.p->next=new;

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Guff_9hys/article/detail/782038
推荐阅读
相关标签
  

闽ICP备14008679号