当前位置: 首页> 教育> 就业 > 双链表的实现

双链表的实现

时间:2025/7/30 8:38:17来源:https://blog.csdn.net/wyuchen123/article/details/139888752 浏览次数:0次

         这是C++算法基础-数据结构专栏的第二十篇文章,专栏详情请见此处


引入

        上次我们学习了单链表,单链表中的每个节点都只存储了它们的下一个节点,只能从前往后遍历,而双链表中的每个节点都存储了它们的上、下两个节点,不仅能从前往后遍历,还能从后往前遍历。

        下面我们就来讲双链表的实现。

        双链表与单链表的性质是大致相同的,如果想了解具体内容,可以移步至我的这篇博客:单链表的实现。

        在这里就不再详细讲解,只讲解定义和主体过程qwq

定义

        链表的定义也在单链表的实现里讲解了,不再详细讲解。

        双向链表中同样有数据域和指针域。与单链表不同之处在于,指针域有左右(或上一个、下一个)之分,用来连接上一个结点、当前结点、下一个结点。它的主要用途是优化某些问题。

过程

        双链表对于过程的说明也在单链表的实现里讲解了,不再详细讲解。

        双链表的最主要操作有三个:构建、插入(写入)数据和删除数据

        构建双链表

        与单链表不同的是,除了存储每个节点的值e\left [ \right ],对于连接节点的数组,需要用到l[]r[]两个数组,分别存储了每个节点的上一个节点的下标和下一个节点的下标;接着,本来我们需要创建一个头结点head尾结点tail的,但我们这次偷个懒,将下标为0的位置分配给head,将下标为1的位置分配给tail,它们只有一个指向:head指向后一个节点tail指向前一个节点,刚开始它们互相指向对方,链表中有节点后头结点head就指向第一个节点,尾结点tail就指向最后一个节点;其次还需要一个变量idx,表示当前节点的下标,刚开始需要赋值为2(想一想为什么)。

        向链表中插入(写入)数据

        k节点后插入一个节点的流程大致如下:

  1. idx节点的e\left [ \right ]中存储数值;
  2. idx节点的l[]存储为k
  3. idx节点的r[]存储为k节点所存储的r[]
  4. k节点所存储的r[]l[]存储为idx
  5. k节点的r[]存储为idx

        首先,图一展示了起始状态;然后,在新节点上面储存数据(第一步,图二);由于新节点要插在k节点后, k节点所存储的下一个节点前,所以新节点的上一个节点要赋值为k节点,下一个节点要赋值k节点所存储的下一个节点(第二、三步,图三);最后,k节点所存储的下一个节点的上一个节点要赋值为idx节点,k节点的下一个节点要赋值为idx节点(第四、五步,图四)。

        还有一点需要注意,操作完成后需要idx++,以便进行下一个节点的插入。

        除了向k节点后插入一个节点,也有向头节点后插入一个节点和向k节点前插入一个节点的操作,这三者虽然代码实现有所不同,但是思路大同小异,那后两者的代码就不再展示了,留给读者去思考。(删除数据也有类似操作,后面也不再讲解)

        向链表中插入(写入)数据

        k节点后的节点删除的流程大致如下:

  1. k节点所存储的r[]所存储的r[]的 l[]存储为k
  2. k节点的r[]存储为k节点所存储的r[]所存储的r[]

        首先,图一展示了起始状态;然后, k节点所存储的下一个节点所存储的下一个节点的上一个节点要赋值为k节点,k节点的下一个节点要赋值为k节点所存储的下一个节点所存储的下一个节点(第一、二步,图二)(懵(⊙_⊙)?)。

代码

        下面给出双链表的实现代码:

int e[N],l[N],r[N],idx;void init(){l[1]=0;r[0]=1;idx=2;
}void add(int k,int x){e[idx]=x;l[idx]=k;r[idx]=r[k];l[r[k]]=idx;r[k]=idx++;
}void remove(int k){l[r[r[k]]]=k;r[k]=r[r[k]];
}
        代码解释

        第一行的各种变量和数组已经在前面讲解了,这里不再详细讲解;init()函数的作用是初始化;add()函数的作用是将x插到下标是k的节点后面;remove()函数的作用是将下标是k的节点后面的节点删掉。


上一篇-单链表的实现    C++算法基础专栏文章    下一篇-​​​​​​​栈的实现.


每周六更新一篇文章,内容一般是自己总结的经验或是在其他网站上整理的优质内容

点个赞,关注一下呗~

关键字:双链表的实现

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: