与单项链表，双向链表在反向遍历的时候更方便
所以
它不仅有 next域指向下一个节点
还有 pre 域指向前一个节点

  1. class Node {
  2.     int no;
  3.     String name;
  4.     String nickName;
  5.     // 指向前一个节点
  6.     Node pre;
  7.     // 指向下一个节点
  8.     Node next;
  10.     public Node(int no, String name, String nickName) {
  11.         this.no = no;
  12.         this.name = name;
  13.         this.nickName = nickName;
  14.     }
  16.     @Override
  17.     public String toString() {
  18.         return "[HeroNode no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
  19.     }
  21. }

双向链表的基本操作

双向链表的基本操作里只有少许操作发生了变化，其余可参考单链表

list和 update

这两个操作基本没有发生变化

  1.     // 遍历双向链表
  2.     public void list() {
  3.         if (head.next == null) {
  4.             System.out.println("当前链表为空");
  5.             return;
  6.         }
  8.         // 这里我们不需要输出头节点，所以我们可以直接让辅助指针指向第一个节点
  9.         Node temp = head.next;
  11.         while (true) {
  13.             // 这里因为我们要输出最后一个元素，所以不能 判断 temp.next == null
  14.             if (temp == null) {
  15.                 break;
  16.             }
  18.             System.out.println(temp);
  19.             temp = temp.next;
  20.         }
  22.     }       
  24.     // 根据节点的 no进行修改
  25.     public void update(Node node) {
  26.         if (head.next == null) {
  27.             System.out.println("链表为空");
  28.             return;
  29.         }
  31.         Node temp = head.next;
  33.         // 用来判断是否找到 要修改节点
  34.         boolean flag = false;
  35.         // 找到需要修改的节点
  36.         while (true) {
  38.             if (temp == null) {
  39.                 // 已经遍历完成
  40.                 break;
  41.             }
  43.             if (temp.no == node.no) {
  44.                 // 找到该节点
  45.                 flag = true;
  46.                 break;
  47.             }
  49.             temp = temp.next;
  51.         }
  53.         if (flag) {
  54.             temp.name = node.name;
  55.             temp.nickName = node.nickName;
  56.         } else {
  57.             System.out.println("没有找到编号为" + node.no + "节点");
  58.         }
  60.     }

add

add 的时候记得要 将 新加入的节点 node 指向前一个节点 temp
也就是
temp.next = node
node.pre = temp 

  1.     // 向双向链表中添加节点
  2.     // 向链表中添加新元素
  3.     public void add(Node node) {
  5.         // 用一个临时的辅助指针来代替 头指针进行遍历
  6.         Node temp = head;
  8.         // 循环遍历到最后一个节点
  9.         while (true) {
  10.             // 如果temp.next == null,说明当前节点为最后一个节点
  11.             if (temp.next == null) {
  12.                 break;
  13.             }
  15.             // temp 指针后移，指向下一个节点
  16.             temp = temp.next;
  18.         }
  20.         // 将最后一个节点 next指向新的元素
  21.         temp.next = node;
  22.         // 将新节点的 pre 指向前一个节点
  23.         node.pre = temp;
  24.     }

delete 变化

delete 变化最大，我们不需要向单链表一样找到被删节点的前一个节点了，
因为在双向链表中，被删节点本身就有前一个节点和后一个节点的信息
所以代码上我们的变化会变得比较大
具体思路为，使用辅助接点temp 找到被删节点node
temp.no == node.no

然后让被删节点的 前一个节点的next 指向 后一个节点
temp.pre.next = temp.next;
并且让后一个节点的pre域指向被删节点的前一个节点，
这里需要判断被删节点是不是最后一个节点
如果不判断的话，当temp是最后一个节点时，会报空指针异常
if (temp.next != null) {
temp.next.pre = temp.pre;
}

  1.     // 删除一个节点
  2.     public void delete(Node node) {
  3.         if (head.next == null) {
  4.             System.out.println("链表为空");
  5.             return;
  6.         }
  8.         Node temp = head.next;
  9.         boolean flag = false;
  11.         while (true) {
  13.             // 关于这里是 temp == null
  14.             // 还是 temp.next == null
  15.             // 关键看你需不需要对最后一个节点参与循环
  16.             // temp 是参与循环， temp.next 不参与
  17.             if (temp == null) {
  18.                 break;
  19.             }
  21.             if (temp.no == node.no) {
  22.                 // 找到该节点，不必像单链表那样找到前一个节点
  23.                 flag = true;
  24.                 break;
  25.             }
  27.             temp = temp.next;
  29.         }
  31.         if (flag) {
  32.             temp.pre.next = temp.next;
  33.             // 如果不判断的话，当temp是最后一个节点时，会报空指针异常
  34.             if (temp.next != null) {
  35.                 temp.next.pre = temp.pre;
  36.             }
  38.         } else {
  39.             System.out.println("没有找到编号为" + node.no + "节点");
  40.         }
  41.     }

addByOrder 升序

这个思路也发生变化，之前也是寻找前一个节点，但是现在我们同样可以找到被插入位置的节点
本来是想在 while 循环中就进行 插入
但是有一个问题就是，如果被插入的节点是最后一个节点，那么它不会被循环到，
如果将while的终止条件变成 temp == null 的话，退出循环后又会空指针异常，
所以我这里在最后又判断了一次node.no > temp.no 来保证 最后一个节点也能被插入，
这个代码可能不是最好的，但是代码是前几天实现的，现在有点懒的优化了。

  1.  public void addByOrder(Node node) {
  3.         // 用一个临时的辅助指针来代替 头指针进行遍历
  4.         Node temp = head;
  6.         boolean flag = false;
  8.         // 循环遍历到最后一个节点
  9.         while (true) {
  10.             // 如果temp.next == null,说明当前节点为最后一个节点
  11.             if (temp.next == null) {
  12.                 break;
  13.             }
  15.             if (node.no < temp.no) {
  16.                 flag = true;
  17.                 break;
  18.             }
  20.             // temp 指针后移，指向下一个节点
  21.             temp = temp.next;
  23.         }
  25.          //正常添加
  26.         if (flag == false && node.no > temp.no) {
  27.             // 将最后一个节点 next指向新的元素
  28.             temp.next = node;
  29.             // 将新节点的 pre 指向前一个节点
  30.             node.pre = temp;
  31.         } else {
  32.             temp.pre.next = node;
  33.             node.pre = temp.pre;
  35.             node.next = temp;
  36.             temp.pre = node;
  37.         }
  39.     }