双向链表的实现

  • A+

从双向链表这个名字

就可以知道很多了

普通的单链表,只能往这一个方向进行查找遍历

而双向链表,他可以从两个方向进行查找

只要知道了某个结点,就可以知道它的前驱和后继

下面实现一下


这里定义一个抽象的数据类

用于保存数据,前驱,后继

声明一个指向头结点的引用

声明一个指向尾结点的引用

定义一个int变量用于保存链表的长度


初始化链表为空链表

新建头结点

前驱和后继都为null

初始化尾结点也为头结点


注意的是双向链表

所以要设置它们的前驱和后继

这里只是在尾部添加,所以新加结点后面不会有结点

这里就只需要修改与原尾结点的联系


这里又不同于在尾部添加结点

这里在头部添加

则表示新加的结点的前面有头结点

后面有链表的第一个结点(除了空链表的情况下)

需要设置的不单单是新加的结点

还需要设置它前驱的后继

设置它后继的前驱

都还是它

(绕傻你^_^)


这个重点说说吧

前面那些都可以参考单链表,并没有什么不同

双向链表既然可以有两个方向可以查找元素

当然是哪边近就要从哪边查找啦

所以

①还是要判断一下索引的合法性

②判断一下是那一边离index近,如果是左边就用前面遍历

如果是右边就用后面遍历

③遍历到第index个结点(自己理解或看单链表)

④返回这个节点

0返回的是头结点


不说了!!!


插入结点

需要设置新加结点的前驱为被插结点的前驱

新加结点的后继为被插结点

设置被插结点的前驱为新加结点

设置被插结点前驱的后继为新加结点

总共关系要设置4个

注意好顺序,别把结点改乱了


这里注意的就是如果要删除的是最后一个结点的话

是不需要设置被删结点的后继的前驱的

因为它都没有后继

尾结点被删除后,那么上一个结点就是尾结点了


测试

结果

双向链表的实现


双向链表也是可以有循环结构的

我就不实现了

循环结构可以通过一个结点遍历整个链表

双向链表也可以啊,虽然不是顺序性的

但也可以结合栈反序一下实现顺序性啊

具体需求,具体使用吧!

  • 我的微信
  • 扫一扫加我微信
  • weinxin
  • 微信我的
  • 我微信扫一扫加
  • weinxin

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: