跳到主要内容

五：双链表的增、删、改、查

文章目录​

  • 前言
  • 一、双链表的应用实例
  • 二、单链表的缺点分析
  • 三、双链表增删改查思路
  • 四、代码实现
  • 4.1 项目结构
    • 4.2 HeroNode.java 节点类
  • 4.3 DoubleLinkedList.java 双链表类
  • 4.4 DoubleLinkedListMain.java 测试类
  • 4.5 测试结果

前言​

一、双链表的应用实例​

使用带head头节点的双向链表实现 - 水浒传英雄排行榜

二、单链表的缺点分析​

1、 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找；
2、 单向链表**不能自我删除**，需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点(认真体会).；

三、双链表增删改查思路​

  • 分析 双向链表的遍历，添加，修改，删除的操作思路

1、 遍历方和单链表一样，只是可以向前，也可以向后查找；
2、 第一种添加(默认添加到双向链表的最后)；
(1) 先找到双向链表的最后这个节点
(2) temporary.next = newNode;
(3) newNode.pre = temporary; 3、 第二种添加(按编号的顺序添加)；
(1)用辅助节点的No与新插入的No比较，找到要插入的前一个节点
(2)先挂载后面：newNode.next = temporary.next; temporary.next.pre = newNode;
(3)在挂载前面：temporary.next = newNode; newNode.pre = temporary; 4、 修改思路和原来的单向链表一样.；
5、 删除；
(1) 因为是双向链表，因此，我们可以实现自我删除某个节点
(2) 直接找到要删除的这个节点，比如temp
(3) temp.pre.next = temp.next
(4) temp.next.pre = temp.pre;

  • 上面的思路说明的逻辑图如下：