单向链表的缺点分析

  • 查找的方向只能是一个方向，而双向链表可以向前或者向后查找；
  • 单向链表不能自我删除，需要靠辅助节点，单链表删除节点时，总是找到temp节点(待删除节点的前一个节点)辅助操作；

    双向链表操作分析

    image.png
    双向链表的遍历和修改与单链表一样，只是遍历时可以向前也可以向后；
  1. 添加(添加到最后)
  • 先找到双向链表的最后这个节点 temp
  • temp.next = newHeroNode; newHeroNode.pre = temp;
  1. 删除
  • 找到要删除的这个节点 temp
  • temp.pre.next = temp.next; temp.next.pre = temp.pre;

双链表操作实现

1. 节点定义

  1. package com.zsy.datastructure.linkedlist.doublelinklist;
  3. /**
  4.  * 以水浒英雄信息作为双向链表的节点
  5.  *
  6.  * @author zhangshuaiyin
  7.  */
  8. public class HeroNode {
  10.     int no;
  11.     String name;
  12.     String nickName;
  13.     // next: 指向下一个节点，默认为null
  14.     HeroNode next;
  15.     // pre: 指向前一个节点，默认为null
  16.     HeroNode pre;
  18.     public HeroNode(int no, String name, String nickName) {
  19.         this.no = no;
  20.         this.name = name;
  21.         this.nickName = nickName;
  22.     }
  24.     @Override
  25.     public String toString() {
  26.         return "HeroNode{" +
  27.                 "no=" + no +
  28.                 ", name='" + name + '\'' +
  29.                 ", nickName='" + nickName + '\'' +
  30.                 '}';
  31.     }
  32. }

2. 双向链表操作方法

  1. package com.zsy.datastructure.linkedlist.doublelinklist;
  3. /**
  4.  * 单链表存储水浒英雄节点信息
  5.  *
  6.  * @author zhangshuaiyin
  7.  */
  8. public class DoubleLinkedList {
  10.     /**
  11.      * head 节点，指向链表第一个节点，定位链表地址
  12.      */
  13.     private final HeroNode head = new HeroNode(0, "", "");
  15.     /**
  16.      * @param node 添加节点：从链表最后
  17.      */
  18.     public void add(HeroNode node) {
  19.         HeroNode temp = head;
  20.         while (temp.next != null) {
  21.             temp = temp.next;
  22.         }
  23.         temp.next = node;
  24.         node.pre = temp;
  25.     }
  27.     /**
  28.      * 按照编号由小到大的顺序插入节点，编号不可重复
  29.      *
  30.      * @param node 插入节点
  31.      */
  32.     public void addByOrder(HeroNode node) {
  33.         HeroNode temp = head;
  34.         while (temp.next != null) {
  35.             if (temp.next.no == node.no) {
  36.                 System.out.printf("编号 %d 已存在，插入失败\n", node.no);
  37.                 return;
  38.             } else if (temp.next.no > node.no) {
  39.                 // 此时说明新节点应该插入 temp 的下一个位置
  40.                 break;
  41.             }
  42.             temp = temp.next;
  43.         }
  44.         //退出时代表temp已到达需要插入的节点的位置的
  45.         //插入节点的下一个节点为temp的下一个节点
  46.         node.next = temp.next;
  48.         // temp.next = null 说明插入的是第一个节点
  49.         if (temp.next != null) {
  50.             // 设置插入位置的上一个节点
  51.             temp.next.pre = node;
  52.         }
  54.         //将temp的下一个节点更改为新插入的节点
  55.         temp.next = node;
  56.         //设置插入节点的上一个节点
  57.         node.pre = temp;
  58.     }
  60.     /**
  61.      * 根据新节点信息修改链表中相同编号的节点
  62.      *
  63.      * @param node 新节点
  64.      */
  65.     public void update(HeroNode node) {
  66.         HeroNode temp = head.next;
  67.         while (temp != null) {
  68.             if (temp.no == node.no) {
  69.                 temp.name = node.name;
  70.                 temp.nickName = node.nickName;
  71.                 return;
  72.             }
  73.             temp = temp.next;
  74.         }
  75.         System.out.printf("没有找到编号是 %d 的节点，不能修改\n", node.no);
  76.     }
  78.     /**
  79.      * @param no 根据编号 no 删除链表中对应的节点
  80.      */
  81.     public void delete(int no) {
  82.         HeroNode temp = head.next;
  83.         while (temp != null) {
  84.             if (temp.no == no) {
  85.                 temp.pre.next = temp.next;
  86.                 if (temp.next != null) {
  87.                     temp.next.pre = temp.pre;
  88.                 }
  89.                 return;
  90.             }
  91.             temp = temp.next;
  92.         }
  93.         System.out.printf("没有找到编号是 %d 的节点，不能修改\n", no);
  94.     }
  96.     /**
  97.      * 打印链表信息
  98.      */
  99.     public void list() {
  100.         if (head.next == null) {
  101.             throw new RuntimeException("当前链表为空");
  102.         }
  103.         HeroNode temp = head.next;
  104.         while (temp != null) {
  105.             System.out.println(temp);
  106.             temp = temp.next;
  107.         }
  108.     }
  109. }

3. 测试方法

  1. package com.zsy.datastructure.linkedlist.doublelinklist;
  3. /**
  4.  * @author zhangshuaiyin
  5.  * @date 2021-04-06 14:33
  6.  */
  7. public class DoubleLinkedListTest {
  8.     static HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
  9.     static HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
  10.     static HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
  11.     static HeroNode hero4 = new HeroNode(4, "公孙胜", "入云龙");
  13.     static DoubleLinkedList linkedList = new DoubleLinkedList();
  15.     public static void main(String[] args) {
  16.         System.out.println("-----------------从链表最后添加节点：---------------------");
  17.         testAdd();
  19.         linkedList = new DoubleLinkedList();
  20.         System.out.println("-----------------按节点编号大小添加：---------------------");
  21.         testAddByOrder();
  23.         System.out.println("-----------------按节点编号修改节点：---------------------");
  24.         HeroNode newNode = new HeroNode(2, "Lu JunYi", "Yu QiLin");
  25.         testUpdate(newNode);
  27.         System.out.println("-----------------按节点编号删除节点：---------------------");
  28.         testDelete();
  29.     }
  31.     /**
  32.      */
  33.     private static void testDelete() {
  34.         linkedList.delete(4);
  35.         linkedList.list();
  36.     }
  38.     /**
  39.      * @param newNode 更新节点
  40.      */
  41.     private static void testUpdate(HeroNode newNode) {
  42.         linkedList.update(newNode);
  43.         linkedList.list();
  44.     }
  46.     /**
  47.      * 测试按编号大小添加元素
  48.      */
  49.     private static void testAddByOrder() {
  50.         linkedList.addByOrder(hero1);
  51.         linkedList.addByOrder(hero4);
  52.         linkedList.addByOrder(hero2);
  53.         linkedList.addByOrder(hero3);
  54.         linkedList.list();
  55.     }
  57.     /**
  58.      * add() 方法按照添加顺序从最后添加
  59.      */
  60.     public static void testAdd() {
  61.         linkedList.add(hero1);
  62.         linkedList.add(hero4);
  63.         linkedList.add(hero2);
  64.         linkedList.add(hero3);
  65.         linkedList.list();
  66.     }
  67. }