单链表、双向链表的应用及面试题

链表概述

1. 链表介绍

   链表是一种物理存储单元上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的。

   

2. 链表特点

   • 链表是以结点形式存储的，是链式存储
   • 每个结点包含 data 区域和 next 区域
   • 如上图各个结点并不是连续存储的
   • 链表分带头结点链表和没有带头结点链表，根据实际的需求来确定带头结点链表逻辑结构

单链表

单链表 (带头结点) 逻辑结构示意图：

简单实现

使用带 head 头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作。

思路分析

1. 添加结点

• 直接添加到链表的尾部：

  思路是：先找到当前链表的最后结点，将最后这个结点的 next 指向新的结点

  

• 添加指定编号（排名）的结点

  

2. 修改结点

1. 通过遍历找到要修改的编号的结点:

2. 修改该编号的数据域

   temp.name = newHeroNode.name
   temp.nickname = newHeroNode.nickname

3. 删除指定编号的结点

1. 【head】 不能动，因此我们需要一个【temp】 辅助结点找到待删除结点的前一个结点。

   在比较时，是 【temp.next.no】 和【需要删除的结点的 no】 比较。

2. 删除时，只需要让 【temp.next】 指向(成为)【temp.next.next】，中间的结点因为没有被指向，就会被 GC 回收掉。

   temp.next = temp.next.next

   

4. 查询指定编号的结点

遍历链表，如果找到目标编号的阶段就返回该结点，找不到则输出提示信息。

代码实现

1. HeroNode 类，每个 HeroNode 对象就是一个结点，每个结点都有数据域和一个指针域，指针域指向直接后继。

   public class HeroNode {
   	public int no;
   	public String name;
   	public String nickname;
   	/**指向下一个结点**/
   	public HeroNode next;
   	/**构造器**/
   	public HeroNode(int hno, String name, String nickname) {
   		this.no = no;
   		this.name = name;
   		this.nickname = nickname;
   	}
   
   	@Override
   	public String toString() {
   		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
   	}
   	
   }

2. SingleLinkedList 类，管理英雄，实现增删改查的功能

   public class SingleLinkedList {
       //先初始化一个头结点, 头结点不要动, 不存放具体的数据
       private HeroNode head = new HeroNode(0, "", "");
   
       /**返回头结点**/
       public HeroNode getHead() {
           return head;
       }
   
       /**
        *  添加结点到链表尾部
        *   1. 找到当前链表的最后结点
        *   2. 将最后这个结点的【next】指向新的结点
        */
       public void add(HeroNode newheroNode) {
           //【head】结点不能动，需要一个辅助遍历的结点【temp】
           HeroNode temp = head;
           //遍历链表，找到最后结点
           while(true) {
               //找到链表的最后结点
               if(temp.next == null) {
                   break;
               }
               //如果没有找到, 将【temp】结点后移
               temp = temp.next;
           }
           //退出while循环时，【temp】就指向了链表的最后
           //将最后这个结点指向新的结点
           temp.next = newheroNode;
       }
   
       //添加指定编号（排名）的英雄结点
       //如果这个编号的结点已经存在，则添加失败，给出提示
       public void addByOrder(HeroNode newheroNode) {
           //头结点不能动，通过一个辅助指针(变量)来帮助找到添加的位置
           //【temp】是添加位置的前一个结点，否则插入不了
           HeroNode temp = head;
            // flag 标志要添加编号的结点是否存在，默认为false
           boolean flag = false;
           while(true) {
               //说明【temp】已经在链表的最后
               if(temp.next == null) {
                   break; 
               }
               //位置找到，就在【temp】的后面插入
               if(temp.next.no > newheroNode.no) { 
                   break;
               } else if (temp.next.no == newheroNode.no) {
                   //说明希望添加的编号的【heroNode】已然存在
                   flag = true; 
                   break;
               }
               //后移，遍历当前链表，逐个比较【heroNode】的编号
               temp = temp.next; 
           }
           //该编号的结点已经存在，不能添加
           if(flag) { 
               System.out.printf("准备插入的编号为 %d 的英雄已经存在, 无法再加入!\n", newheroNode.no);
           } else {
               //插入到链表中, 【temp】的后面
               newheroNode.next = temp.next;
               temp.next = newheroNode;
           }
       }
   
       //修改指定编号的结点的信息（数据域）
       public void update(HeroNode newHeroNode) {
           //判断链表是否空
           if(head.next == null) {
               System.out.println("链表为空~");
               return;
           }
           //用来定位目标结点的辅助结点
           HeroNode temp = head.next;
           //表示是否找到该结点
           boolean flag = false; 
           //遍历链表，找到要修改的结点
           while(true) {
               //已经遍历完链表
               if (temp == null) {
                   break; 
               }
               if(temp.no == newHeroNode.no) {
                   //要修改的目标结点找到了
                   flag = true;
                   break;
               }
               temp = temp.next;
           }
           //根据flag 判断是否找到要修改的结点
           if(flag) {
               temp.name = newHeroNode.name;
               temp.nickname = newHeroNode.nickname;
           } else { 
               //没有找到
               System.out.printf("找不到编号为 %d 的英雄，无法修改！
   ", newHeroNode.no);
           }
       }
   
       //删除指定编号（no）的结点
       //head不能动，因此我们需要一个【temp】辅助结点找到待删除结点的前一个结点
       //在比较时，是 temp.next.no 和 需要删除的结点的no 比较
       public void del(int no) {
           HeroNode temp = head;
           // 标志是否找到待删除结点的前一个结点
           boolean flag = false; 
           while(true) {
               //已经遍历到链表最后
               if(temp.next == null) { 
                   break;
               }
               //找到了待删除结点的前一个结点【temp】
               if(temp.next.no == no) {
                   flag = true;
                   break;
               }
               //temp后移，继续遍历
               temp = temp.next; 
           }
           ////找到，可以删除
           if(flag) { 
               temp.next = temp.next.next;
           }else {
               System.out.printf("要删除的这个编号的 %d 英雄不存在!\n", no);
           }
       }
   
       //显示链表[遍历]
       public void list() {
           //判断链表是否为空
           if(head.next == null) {
               System.out.println("链表为空");
               return;
           }
           //因为头结点，不能动，因此我们需要一个辅助变量来遍历
           HeroNode temp = head.next;
           while(true) {
               //判断是否到链表最后
               if(temp == null) {
                   break;
               }
               //输出结点的信息
               System.out.println(temp);
               //将temp后移，一定小心
               temp = temp.next;
           }
       }
                                 
   	
    //查询指定编号的结点
       public HeroNode query(int no){
           //用来辅助遍历的结点
           HeroNode temp = head;
           while (true){
               //遍历完链表，没有找到该编号的结点
               if (temp.next == null){
                   return null;
               }
               //找到目标编号的结点，就返回该结点
               if (temp.next.no == no){
                   return temp.next;
               }
               temp = temp.next;
           }
       }
       
                                
   }

3. 程序测试及结果：

   public class Test {
       public static void main(String[] args) {
           //创建结点
           HeroNode hero1 = new HeroNode(1, "松江", "及时雨");
           HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
           HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
           HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
   
           //创建一个空的单链表
           SingleLinkedList singleLinkedList = new SingleLinkedList();
   
           //在链表末尾添加结点
           singleLinkedList.add(hero1);
           singleLinkedList.add(hero3);
   
           //添加指定编号（排名）的结点
           singleLinkedList.addByOrder(hero2);
           singleLinkedList.addByOrder(hero3);
           singleLinkedList.addByOrder(hero4);
   
           System.out.println("-------------修改前的单链表：");
           //遍历打印单链表中所有结点
           singleLinkedList.list();
   
           //修改指定编号的结点的信息
           HeroNode hero5 = new HeroNode(2, "鲁智深", "花和尚");
           singleLinkedList.update(hero5);
           HeroNode hero6 = new HeroNode(5, "武松", "行者");
           singleLinkedList.update(hero6);
   
           System.out.println("-------------修改后的单链表：");
           //遍历打印单链表中所有结点
           singleLinkedList.list();
   
           //删除指定编号的结点
           singleLinkedList.del(1);
           singleLinkedList.del(6);
           System.out.println("-------------删除后的单链表：");
           //遍历打印单链表中所有结点
           singleLinkedList.list();
   
           //查询指定编号的结点
           System.out.println("-------------查询到的英雄如下：");
           System.out.println(singleLinkedList.query(3));
           System.out.println(singleLinkedList.query(1));
   
           //返回有效结点个数
           System.out.println("-------------有效结点个数为：" + getLength(singleLinkedList.getHead()));
   
           //查找倒数第 k 个结点
           System.out.println("-------------倒数第 2 个结点为：");
           System.out.println(findLastIndexNode(singleLinkedList.getHead(), 2));
   
           //反转单链表
           reverseList(singleLinkedList.getHead());
           System.out.println("-------------反转后的单链表：");
           singleLinkedList.list();
   
           //利用栈逆序打印单链表
           System.out.println("-------------利用栈逆序打印单链表:");
           reversePrint(singleLinkedList.getHead());
       }
   }

   

Josephu问题

思路分析

• 创建环形链表的思路图解

  

• 小孩出圈的思路分析图

  

代码实现

1. boy 类：每个 boy 对象就是一个小孩结点；

   public class Boy {
       private int no;
       private Boy next;
   
       public Boy(int no) {
           this.no = no;
       }
   
       public int getNo() {
           return no;
       }
   
       public void setNo(int no) {
           this.no = no;
       }
   
       public Boy getNext() {
           return next;
       }
   
       public void setNext(Boy next) {
           this.next = next;
       }
   
       @Override
       public String toString() {
           return "Boy{" +
                   "no=" + no +
                   '}';
       }
   }

2. CircleSingleLinkedList 类：模拟单向循环链表，解决 Josephu 问题。

       public void showBoy() {
           // 判断链表是否为空
           if (first == null) {
               System.out.println("没有任何小孩~~");
               return;
           }
           // first不能动，使用一个辅助指针完成遍历
           Boy curBoy = first;
           while (true) {
               System.out.printf("小孩的编号 %d \n", curBoy.getNo());
               // 说明已经遍历完毕
               if (curBoy.getNext() == first) {
                   break;
               }
               // 让辅助指针curBoy后移，继续遍历
               curBoy = curBoy.getNext();
           }
       }
   
       /**
        * 根据用户输入，计算小孩（结点）出圈顺序
        * @param startNo [in] 表示从第几个小孩开始计数
        * @param countNum [in] 表示数几下让一个小孩出圈
        * @param nums [in] 表示最初有多少小孩在圈中
        */
       public void countBoy(int startNo, int countNum, int nums) {
           // 先对数据进行校验
           if (first == null || startNo < 1 || startNo > nums) {
               System.out.println("参数输入有误， 请重新输入");
               return;
           }
           // helper是用来遍历的辅助指针，first此时依然指向（是）头结点
           Boy helper = first;
           // 利用辅助指针遍历链表 , 让helper指向（成为）链表最后一个节点
           while (true) {
               // 说明helper指向（是）最后小孩结点
               if (helper.getNext() == first) {
                   break;
               } // helper指向最后一个小孩节点
               //让helper后移，继续遍历
               helper = helper.getNext();
           }
           //遍历先让first指向第一个数数的小孩startNo，才能开始
           //让helper先指向开始数数的小孩前面一个人,作为后面判断游戏结束的依据
           //同时小孩出圈后重新让链表形成环也需要借助helper节点来完成
           for (int j = 0; j < startNo - 1; j++) {
               first = first.getNext();
               helper = helper.getNext();
           }
           //当小孩报数时，让first 和 helper 指针同时 的移动  m  - 1 次, 然后出圈
           //这里是一个循环操作，直到圈中只有一个节点
           while (true) {
               // 当开始数数的小孩的前一个人是他自己时，说明环中只有一个节点
               if (helper == first) {
                   break;
               } //环中只剩一个人，游戏结束
               //让 first 和 helper 同时移动 countNum - 1
               for (int j = 0; j < countNum - 1; j++) {
                   first = first.getNext();
                   helper = helper.getNext();
               } //这时first指向的节点，就是要出圈的小孩节点
               System.out.printf("小孩%d出圈\n", first.getNo());
               //让first指向first后面一个节点（小孩），让原来的first出圈
               first = first.getNext();
               //让现在的first结点成为原first节点（已出圈节点）前面一个节点的后继
               //重新构成环
               helper.setNext(first);
           } //游戏结束，helper和first是同一个结点，也就是最后一个小孩
           System.out.printf("最后留在圈中的是小孩%d \n", first.getNo());
   
       }
   }

3. 测试及程序运行结果

   public class Test {
       public static void main(String[] args) {
           //创建一个循环单向链表对象
           CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
   
           //创建有5个小孩（结点）的环形链表
           circleSingleLinkedList.addBoy(5);
   
           //遍历打印环形链表
           System.out.println("————圈中的小孩：————");
           circleSingleLinkedList.showBoy();
   
           //打印小孩出拳的顺序
           System.out.println("————小孩出队顺序：————");
           circleSingleLinkedList.countBoy(1,2,5);
       }
   }

   

面试题

单链表的常见面试题如下:

1. 求单链表中有效结点的个数:

   public static int getLength(HeroNode head){
           //空链表
           if (head.next == null){
               return 0;
           }
           int length = 0;
           //定义一个用遍历的辅助接点
           //从第一个结点开始，不计头结点
           HeroNode cur = head.next;
           while (cur != null){
               length++;
               cur = cur.next;
           }
           return length;
       }

2. 查找单链表中的倒数第 k 个结点 【新浪面试题】

   1. 编写一个方法，接受 head 结点，同时接受一个 index （即 k）；

   2. 遍历整个链表，得到链表的总长度 length ;

      length = getLength(singleLinkedList.getHead() )

   3. 得到链表的 length 后，遍历链表，寻找第（length - index）个有效结点。

   public static HeroNode findLastIndexNode(HeroNode head, int k) {
           //如果链表为空返回null
           if (head.next == null) {
               return null;
           }
           //第一次遍历得到链表长度
           int size = getLength(head);
           //先检查 k 是否合法
           if (k <= 0 || k > size) {
               return null;
           }
           //再次遍历到 size-k 位置，得到倒数第k个结点
           //用来遍历的辅助结点
           HeroNode temp = head.next;
           //从正数第一个有效结点开始,循环定位到倒数第k个结点
           for (int i = 0; i < size - k; i++) {
               temp = temp.next;
           }
           return temp;
       }

3. 单链表的反转【腾讯面试题，有点难度】

   1. 先定义一个结点：

      reverseHead = new HeroNode();

   2. 从头到尾遍历原来的链表，每遍历一个结点，就将其取出，插入到 【reverseHead】 的后面（紧挨着 reverseHead）；

      

   3. 让 【head.next】 指向（成为） 【reverseNode.next】 。

      

   public static void reverseList(HeroNode head) {
           //如果当前链表为空或者只有一个结点，就无需反转
           if (head.next == null || head.next.next == null) {
               return;
           }
           //定义一个辅助遍历链表的指针（变量）
           HeroNode cur = head.next;
           //指向当前结点【cur】的下一个结点，临时保存链表的后半部分
           HeroNode nextNode = null;
           HeroNode reverseHead = new HeroNode(0, "", "");
           //遍历原来的链表，，依次将每个结点取出，放在新的链表 reversHead 的最前端；
           while (cur != null) {
               //临时保存当前结点的下一个结点
               nextNode = cur.next;
               //让cur的下一个结点指向新链表的最前端
               cur.next = reverseHead.next;
               //将cur连接到新的链表上
               reverseHead.next = cur;
               //让cur后移
               cur = nextNode;
           }
           //将head.next指向reverseNode.next;
           head.next = reverseHead.next;
       }

4. 从尾到头打印单链表 【百度，要求方式1：反向遍历 。 方式2：Stack栈】

   • 先将单链表反转，再遍历打印（不建议，会破坏单链表本身的结构）。

     reverseList(singleLinkedList.getHead());
     singleLinkedList.list();

   • 将单链表各个结点压入栈中，利用栈先进后出的特点，实现单链表的逆序打印。（不会改变链表本身的结构）

     public static void reversePrint(HeroNode head) {
             //空链表，不能打印
             if (head.next == null) {
                 return;
             }
             //创建一个栈
             Stack<HeroNode> stack = new Stack<HeroNode>();
             //用于辅助遍历的结点
             HeroNode cur = head.next;
             //将单链表所有的有效结点压入栈中
             while (cur != null) {
                 stack.push(cur);
                 cur = cur.next;
             }
             //弹栈并打印结点
             while (stack.size() > 0) {
                 //stack 栈的特点是先进后出
                 System.out.println(stack.pop());
             }
         }

5. 合并两个有序的单链表，且合并之后的链表依然有序。

双向链表

双向链表（double-liked list）是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

优点

单链表	双向链表
只能向一个方向查找	可以向前或者向后查找
不能自我删除，需要靠辅助节点	可以自我删除

思路分析

• 遍历

  单链表一样，只是可以向前，也可以向后查找。找到目标编号的阶段就返回该结点，找不到则输出提示信息。

• 添加

  • 添加到双向链表的最后

    • 非循环双向链表

      先遍历找到最后一个结点（尾结点），使尾结点成为要添加结点的前驱，再让新结点变成尾结点的后继即可。

      //让新添加结点成为最后一个结点的后继
      temp.next = newHeroNode
      //让最后一个结点成为新添加结点的前驱
      newHeroNode.pre = temp;

    • 循环双向链表

      和下面插入到链表中间的操作一样。

  • 插入到双向链表中间

    插入操作时，其实并不复杂，不过顺序很重要，千万不能写反了。

    假设要插入的结点为 s ，要实现将结点 s 插入到结点 p 和 p.next 之间,需要下面几步:

    1. 让前一个结点成为新结点的前驱；

    2. 让后面一个结点成为新结点的后继；

    3. 让新结点成为后面一个结点的前驱；

    4. 让新结点成为前面一个结点的后继。

       

    //把p赋值给s的前驱，如图中①
    s.prior = p;
    //把p.next赋值给s的后继，如图中②
    s.next = p.next
    //把s赋值给p->next的前驱，如图中③
    p.next.prior = s;
    //把s赋值给p的后继，如图中④
    p.next = s;

    关键在于它们的顺序，由于第 2 步和第 3 步都用到了 【p.next】，如果第 4 步先执行，则会使得 【p.next】提前变成了 【s】，使得插入的工作完不成。

    所以我们不妨把上面这来图在理解的基础上记忆，顺序是：先搞定 s 的前驱和后继，再搞定后结点的前驱，最后解决前结点的后继。

• 修改

  1. 通过遍历找到要修改的编号的结点；

  2. 修改该编号的数据域。

     temp.name = newHeroNode.name
     temp.nickname = newHeroNode.nickname

• 删除

  因为是双向链表，可以实现自我删除某个结点。找到要删除结点 p ，只需要下面两个步骤：

  

  //把p.next赋值给p.prior的后继如图中①
  p.prior.next = p.next
  //把p.prior赋值给p.next的前驱，如图中②
  p.next.prior = p.prior;

代码实现

1. 定义 HeroNode ， 每个 HeroNode 对象就是一个结点，每个结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

   public class HeroNode {
       public int no;
       public String name;
       public String nickname;
       /**
        * 指向下一个结点，默认null
        */
       public HeroNode next;
       /**
        * 指向前一个结点，默认null
        */
       public HeroNode pre;
   
       /**
        * 构造器
        **/
       public HeroNode(int no, String name, String nickname) {
           this.no = no;
           this.name = name;
           this.nickname = nickname;
       }
   
       /**
        * 为方便打印，我们重写toString
        */
       @Override
       public String toString() {
           return "HeroNode{" +
                   "no=" + no +
                   ", name='" + name + '\'' +
                   ", nickname='" + nickname + '\'' +
                   '}';
       }
   }

2. 模拟双向链表，实现增删改查功能。

   public class DoubleLinkedList {
       /**
        * 初始化一个头结点, 头结点不能动不要, 不存放具体的数据
        */
       private HeroNode head = new HeroNode(0, "", "");
   
       /**
        * 返回头结点
        */
       public HeroNode getHead() {
           return head;
       }
   
       /**
        * 遍历打印双向链表
        */
       public void list() {
           // 判断链表是否为空
           if (head.next == null) {
               System.out.println("链表为空");
               return;
           }
           // 因为头结点，不能动，因此我们需要一个辅助变量来遍历
           HeroNode temp = head.next;
           while (true) {
               // 判断是否到链表最后
               if (temp == null) {
                   break;
               }
               // 输出结点的信息
               System.out.println(temp);
               // 将temp后移，一定小心
               temp = temp.next;
           }
       }
   
       /**
        * 添加结点到双向链表的最后
        * 这里我们的链表是非循环双向链表
        * @param heroNode [in] 传入链表的头结点
        */
       public void add(HeroNode heroNode) {
           // 因为head结点不能动，因此我们需要一个辅助遍历 temp
           HeroNode temp = head;
           // 遍历链表，找到最后
           while (true) {
               // 找到链表的最后
               if (temp.next == null) {
                   break;
               }
               // 如果没有找到最后, 继续将temp后移
               temp = temp.next;
           } //当退出while循环时，temp就指向了链表的最后
           // 让新添加结点成为最后一个结点的后继
           temp.next = heroNode;
           // 让最后一个结点成为新添加结点的前驱
           heroNode.pre = temp;
       }
   
       /**
        * 添加英雄结点到链表中间的指定位置（编号）
        * 如果这个编号的结点已经存在，则添加失败，给出提示
        * @param newHeroNode [in] 要添加的结点
        */
       public void addByOrder(HeroNode newHeroNode) {
           //头结点不能动，通过一个辅助指针(变量)来帮助找到添加的位置
           //【temp】是添加位置的前一个结点，否则插入不了
           HeroNode temp = head;
           // flag 标志要添加编号的结点是否存在，默认为false
           boolean flag = false;
           while(true) {
               //说明【temp】已经在链表的最后
               if(temp.next == null) {
                   break;
               }
               //位置找到，就在【temp】的后面插入
               if(temp.next.no > newHeroNode.no) {
                   break;
               } else if (temp.next.no == newHeroNode.no) {
                   //说明希望添加的编号的【heroNode】已然存在
                   flag = true;
                   break;
               }
               //后移，遍历当前链表，逐个比较【heroNode】的编号
               temp = temp.next;
           }
           //该编号的结点已经存在，不能添加
           if(flag) {
               System.out.printf("准备插入的编号为 %d 的英雄已经存在, 无法再加入!\n", newHeroNode.no);
           } else {
               //让前一个结点成为新结点的前驱
               newHeroNode.pre = temp;
               //让后面一个结点成为新结点的后继
               newHeroNode.next = temp.next;
               //让新结点成为后面一个结点的前驱
               temp.next.pre = newHeroNode;
               //让新结点成为前面一个结点的后继
               temp.next = newHeroNode;
           }
       }
   
   
       /**
        * 修改特定结点的内容
        * 双向链表的结点内容修改和单向链表一样
        * @param newHeroNode [in] 要修改成的结点
        */
       public void update(HeroNode newHeroNode) {
           // 判断是否空
           if (head.next == null) {
               System.out.println("链表为空~");
               return;
           }
           // 定义一个辅助遍历的变量
           HeroNode temp = head.next;
           // 标识是否找到该结点
           boolean flag = false;
           // 遍历链表，根据no找到需要修改的结点
           while (true) {
               if (temp == null) {
                   break;
               } // 已经遍历完链表
               if (temp.no == newHeroNode.no) {
                   // 找到
                   flag = true;
                   break;
               }
               temp = temp.next;
           }
           // 根据flag的值，判断是否找到要修改的结点
           if (flag) {
               temp.name = newHeroNode.name;
               temp.nickname = newHeroNode.nickname;
           } else { // 没有找到
               System.out.printf("没有找到 编号 %d 的结点，不能修改\n", newHeroNode.no);
           }
       }
   
       /**
        * 从双向链表中删除指定编号的结点
        * 对于双向链表，找到要删除的结点后，可以直接自我删除
        * 不必像单链表那样，需要利用前一个结点来删除
        * 注意我们这里的双向链表是非循环的
        * @param no [in] 要删除的结点的编号（no）
        */
       public void del(int no) {
           // 判断当前链表是否为空
           if (head.next == null) {
               System.out.println("链表为空，无法删除");
               return;
           }
           // 辅助变量(指针)
           HeroNode temp = head.next;
           // 标志是否找到待删除结点的
           boolean flag = false;
           while (true) {
               if (temp == null) {
                   break;
               } // 已经到链表的最后结点的next
               if (temp.no == no) {
                   // 找到了的待删除结点（就是当前结点temp）
                   flag = true;
                   break;
               }
               // 没有找到，temp后移继续遍历
               temp = temp.next;
           } //遍历查找结束
   
           // 根据flag的值，判断是否存在要删除的结点
           if (flag) {
               // 可以删除
               temp.pre.next = temp.next;
               // 由于我们的链表是非循环的
               // 如果删除的是最后一个结点，就不需要执行下面这句话，否则出现空指针
               if (temp.next != null) {
                   temp.next.pre = temp.pre;
               }
           } else {
               System.out.printf("要删除的 %d 结点不存在\n", no);
           }
       }
   
       /**
        * 查询指定编号的结点
        * @param no
        * @return
        */
       public HeroNode query(int no){
           //用来辅助遍历的结点
           HeroNode temp = head;
           while (true){
               //遍历完链表，没有找到该编号的结点
               if (temp.next == null){
                   return null;
               }
               //找到目标编号的结点，就返回该结点
               if (temp.next.no == no){
                   return temp.next;
               }
               temp = temp.next;
           }
       }
   }

3. 测试及程序运行结果

   public class Test {
       public static void main(String[] args) {
        // 先创建结点
           HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
           HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
           HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
           HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
   
           // 创建一个双向链表
           DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
   
           //在链表末尾添加结点
           doubleLinkedList.add(hero1);
           doubleLinkedList.add(hero4);
   
           //在链表中间添加指定编号的结点添加结点
           doubleLinkedList.addByOrder(hero2);
           doubleLinkedList.addByOrder(hero3);
   
           System.out.println("-------------修改前的双向链表：");
           //遍历打印单链表中所有结点
           doubleLinkedList.list();
   
           //修改指定结点
           HeroNode hero5 = new HeroNode(4, "公孙胜", "入云龙");
           doubleLinkedList.update(hero4);
           HeroNode hero6 = new HeroNode(5, "武松", "行者");
           doubleLinkedList.update(hero5);
           System.out.println("-------------修改后的双向链表：");
           //遍历打印单链表中所有结点
           doubleLinkedList.list();
   
           // 删除指定编号的结点
           doubleLinkedList.del(3);
           doubleLinkedList.del(5);
           System.out.println("-------------删除后的双向链表：");
           doubleLinkedList.list();
   
           //查询指定编号的结点
           System.out.println("-------------查询到的结点如下（null表示编号不存在）：");
           System.out.println(doubleLinkedList.query(4));
           System.out.println(doubleLinkedList.query(3));
   
       }
   }