1. 链表对象

  1. // 定义 HeroNode2  ， 每个 HeroNode 对象就是一个节点
  2. class HeroNode {
  3.     public String no;
  4.     public String name;
  5.     public String nickname;
  6.     public HeroNode next; // 指向下一个节点,  默认为 null
  7.     public HeroNode pre; // 指向前一个节点, 默认为 null
  9.     // 构造器
  10.     public HeroNode(String no, String name, String nickname) {
  11.         this.no = no;
  12.         this.name = name;
  13.         this.nickname = nickname;
  14.     }
  16.     // 为了显示方法，我们重新 toString
  17.     @Override
  18.     public String toString() {
  19.         return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
  20.     }
  22. }

2. 对链表对象进行操作

  1. // 创建一个双向链表的类
  2. class DoubleLinkedList {
  4.     // 先初始化一个头节点, 头节点不要动, 不存放具体的数据
  5.     private HeroNode head = new HeroNode("0", "", "");
  7.     //定义双向链表的尾节点
  8.     private HeroNode last;
  10.     // 返回头节点
  11.     public HeroNode getHead() {
  12.         return head;
  13.     }
  15.     // 遍历双向链表的方法
  16.     // 显示链表[遍历]
  17.     public List<uhjcTreeDetailVO> list() {
  18.         List<uhjcTreeDetailVO> list = new ArrayList<>();
  20.         // 判断链表是否为空
  21.         if (head.next == null) {
  22.             System.out.println("链表为空");
  23.             return null;
  24.         }
  26.         // 因为头节点，不能动，因此我们需要一个辅助变量来遍历
  27.         HeroNode temp = head.next;
  28.         while (true) {
  29.             // 判断是否到链表最后
  30.             if (temp == null) {
  31.                 break;
  32.             }
  33.             // 设置
  34.             uhjcTreeDetailVO uhjcTreeDetailVO = new uhjcTreeDetailVO();
  35.             uhjcTreeDetailVO.setNodeId(temp.name);
  36.             uhjcTreeDetailVO.setNextNodeId(temp.nickname);
  38.             list.add(uhjcTreeDetailVO);
  39.             // 输出节点的信息
  40.             System.out.println(temp);
  41.             // 将 temp 后移， 一定小心
  42.             temp = temp.next;
  43.         }
  45.         return list;
  46.     }
  48.     // 添加一个节点到双向链表的最后.
  49.     public void addLast(HeroNode heroNode) {
  50.         // 因为 head 节点不能动，因此我们需要一个辅助遍历 temp
  51.         HeroNode temp = head;
  52.         // 遍历链表，找到最后
  53.         while (true) {
  54.             // 找到链表的最后
  55.             if (temp.next == null) {
  56.                 break;
  57.             }
  58.             // 如果没有找到最后,  将将 temp 后移
  59.             temp = temp.next;
  60.         }
  61.         // 当退出 while 循环时，temp 就指向了链表的最后
  62.         // 形成一个双向链表
  63.         temp.next = heroNode;
  64.         heroNode.pre = temp;
  65.     }
  67.     //头插法
  68.     public void addFirst(HeroNode heroNode) {
  69.         //定义一个用作插入的节点
  70.         //1.假设双向链表为空
  71.         if (this.head == null) {
  72.             this.head = heroNode;
  73.             this.last = heroNode;
  74.         } else {
  75.             //2.双向链表不为空的情况下
  76.             //不懂请看上面的图解，就很简单了
  77.             heroNode.next = this.head;
  78.             this.head.pre = heroNode;
  79.             this.head = heroNode;
  80.         }
  81.     }
  83.     //在任意位置插入
  84.     public void addIndex(int index, HeroNode heroNode) {//形参index为插入元素位置，data为插入的数值
  85.         //定义一个用作插入的节点
  86.         HeroNode cur = this.head;//定义一个cur用作遍历双向链表
  87.         //1、判断插入位置的合法性
  88.         if (index < 0 || index > size()) {
  89.             System.out.println("插入位置不合法！！！");
  90.             return;
  91.         }
  92.         //2、假设插入位置为头结点的情况下，即就是头插法
  93.         if (index == 0) {
  94.             addFirst(heroNode);//调用头插法代码
  95.             return;
  96.         }
  97.         //3、假设插入位置为尾结点的情况下，即就是尾插法
  98.         if (index == size()) {
  99.             addLast(heroNode);//调用尾插法代码
  100.             return;
  101.         }
  102.         //4、在中间任意位置的情况下
  103.         while (index != 0) {
  104.             cur = cur.next;
  105.             index--;
  106.         }
  107.         //不懂请看上面的图解，就很简单了
  108.         //核心代码
  109.         heroNode.next = cur;
  110.         heroNode.pre = cur.pre;
  111.         cur.pre = heroNode;
  112.         heroNode.pre.next = heroNode;
  113.     }
  115.     //在任意位置查询
  116.     public HeroNode findIndex(int index) {
  117.         //定义一个用作查询的节点
  118.         HeroNode cur = this.head;//定义一个cur用作遍历双向链表
  119.         //1、判断插入位置的合法性
  120.         if (index < 0 || index > size()) {
  121.             System.out.println("查询位置不合法！！！");
  122.             return null;
  123.         }
  124.         //2、判断是否为头部
  125.         if (index == 0) {
  126.             return this.head;
  127.         }
  128.         //3、判断是否为尾部
  129.         if (index == size()) {
  130.             return this.last;
  131.         }
  132.         //4、在中间任意位置的情况下
  133.         while (index != 0) {
  134.             cur = cur.next;
  135.             index--;
  136.         }
  137.         return cur;
  138.     }
  140.     //求双向链表的长度（之后addIndex代码会用到）
  141.     public int size() {
  142.         int count = 0;
  143.         HeroNode cur = this.head;
  144.         while (cur != null) {
  145.             count++;
  146.             cur = cur.next;
  147.         }
  148.         return count;
  149.     }
  151.     // 修改一个节点的内容, 可以看到双向链表的节点内容修改和单向链表一样
  152.     // 只是 节点类型改成 HeroNode2
  153.     public void update(HeroNode newHeroNode) {
  154.         // 判断是否空
  155.         if (head.next == null) {
  156.             System.out.println("链表为空~");
  157.             return;
  158.         }
  159.         // 找到需要修改的节点, 根据 no 编号
  160.         // 定义一个辅助变量
  161.         HeroNode temp = head.next;
  162.         boolean flag = false; //  表示是否找到该节点
  163.         while (true) {
  164.             if (temp == null) {
  165.                 break; //  已经遍历完链表
  166.             }
  167.             if (newHeroNode.no.equals(temp.no)) {
  168.                 // 找到
  169.                 flag = true;
  170.                 break;
  171.             }
  172.             temp = temp.next;
  173.         }
  175.         // 根据 flag 判断是否找到要修改的节点
  176.         if (flag) {
  177.             temp.name = newHeroNode.name;
  178.             temp.nickname = newHeroNode.nickname;
  179.         } else { // 没有找到
  180.             System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
  181.         }
  182.     }
  184.     // 从双向链表中删除一个节点,
  185.     // 说明
  186.     // 1 对于双向链表，我们可以直接找到要删除的这个节点
  187.     // 2 找到后，自我删除即可
  188.     public void del(String no) {
  189.         // 判断当前链表是否为空
  190.         if (head.next == null) {
  191.             //  空链表
  192.             System.out.println("链表为空，无法删除");
  193.             return;
  194.         }
  196.         HeroNode temp = head.next;
  197.         // 辅助变量(指针)
  198.         boolean flag = false;
  199.         // 标志是否找到待删除节点的
  200.         while (true) {
  201.             if (temp == null) { // 已经到链表的最后
  202.                 break;
  203.             }
  204.             if (temp.no == no) {
  205.                 // 找到的待删除节点的前一个节点temp
  206.                 flag = true;
  207.                 break;
  209.             }
  210.             temp = temp.next; // temp 后移，遍历
  211.         }
  213.         // 判断 flag
  214.         if (flag) { // 找到
  215.             // 可以删除
  216.             temp.next = temp.next.next;
  217.             //[单向链表]
  218.             temp.pre.next = temp.next;
  219.             // 这里我们的代码有问题?
  220.             // 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
  221.             if (temp.next != null) {
  222.                 temp.next.pre = temp.pre;
  223.             }
  224.         } else {
  225.             System.out.printf("要删除的 %d  节点不存在\n", no);
  226.         }
  227.     }
  229. }

3. 测试

  1. public class DoubleLinkedListDemo {
  3.     public static void main(String[] args) {
  4.         // 测试
  5.         System.out.println("双向链表的测试");
  6.         // 先创建节点\
  7.         HeroNode hero1 = new HeroNode("1", "1", "0");
  8.         HeroNode hero2 = new HeroNode("2", "2", "玉麒麟");
  9.         HeroNode hero3 = new HeroNode("3", "吴用", "智多星");
  10.         HeroNode hero4 = new HeroNode("4", "林冲", "豹子头");
  11.         // 创建一个双向链表
  12.         DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
  13.         doubleLinkedList.addLast(hero1);
  14.         doubleLinkedList.addLast(hero2);
  15.         doubleLinkedList.addLast(hero3);
  16.         doubleLinkedList.addLast(hero4);
  18.         doubleLinkedList.list();
  20.         // 修改
  21.         HeroNode newHeroNode = new HeroNode("4", "公孙胜", "入云龙");
  22.         doubleLinkedList.update(newHeroNode);
  23.         System.out.println("修改后的链表情况");
  24.         List<uhjcTreeDetailVO> list = doubleLinkedList.list();
  25.         list.forEach(uhjcTreeDetailVO -> {
  27.         });
  29.         // 删除
  30.         doubleLinkedList.del("3");
  31.         System.out.println("删除后的链表情况~~");
  32.         doubleLinkedList.list();
  35.         // 随机插入
  36.         System.out.println("随机插入");
  37.         doubleLinkedList.addIndex(1, hero3);
  38.         doubleLinkedList.list();
  40.         // 查询指定节点
  41.         System.out.println("随机查询");
  42.         HeroNode index = doubleLinkedList.findIndex(1);
  43.         System.out.println(index.toString());
  45.     }
  46. }