链表(Linked List)介绍

内存结构

内存上来看：链表存储空间不连续（不像数组）
aHR0cDovL2hleWdvLm9zcy1jbi1zaGFuZ2hhaS5hbGl5dW5jcy5jb20vaW1hZ2VzL2ltYWdlLTIwMjAwNzEzMTkyNjIxMDI1LnBuZw.png

链表特点

  • 链表是以节点的方式来存储，是链式存储
  • data 域存放数据，next 域指向下一个节点

  • 链表分带头节点的链表和没有头节点的链表， 根据实际的需求来确定

    链表应用场景

    水浒英雄榜

    使用带 head 头的单向链表实现【水浒英雄排行榜管理】

    链表节点定义

  • no ：英雄编号

  • name ：英雄名字
  • nickName ：英雄昵称

  • next ：指向下一个 HeroNode 节点

    1. //定义HeroNode ， 每个HeroNode 对象就是一个节点
    2. class HeroNode {
    3.   // 英雄编号
    4.   public int no;
    5.   // 英雄名字
    6.   public String name;
    7.   // 英雄昵称
    8.   public String nickName;
    9.   // 指向下一个节点
    10.   public HeroNode next;
    12.   public HeroNode(int no, String name, String nickname) {
    13.       this.no = no;
    14.       this.name = name;
    15.       this.nickName = nickname;
    16.   }
    18.   // 为了显示方法，我们重写toString
    19.   @Override
    20.   public String toString() {
    21.       return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
    22.   }
    23. }

    链表定义

    DummyHead ：头结点不存放数据，仅仅作为当前链表的入口

head 字段的值不能改变，一旦改变，就丢失了整个链表的入口，我们也就无法通过 head 找到链表了

  1. class SingleLinkedList {
  2.     // 因为head节点不能动，因此我们需要一个辅助遍历 temp
  3.     private final HeroNode head = new HeroNode(0, "", "");
  4. }

遍历链表

代码思路

  • 定义辅助变量 temp ，相当于一个指针，指向当前节点
  • 何时遍历完成？temp == null 表明当前节点为 null ，即表示已到链表末尾

  • 如何遍历？temp = temp.next ，每次输出当前节点信息之后，temp 指针后移

    代码实现

    1. // 显示链表[遍历]
    2. public void list() {
    3.   // 判断链表是否为空
    4.   if (head.next == null) {
    5.       System.out.println("链表为空");
    6.       return;
    7.   }
    8.   // 因为头节点，不能动，因此我们需要一个辅助变量来遍历
    9.   HeroNode temp = head.next;
    10.   // 判断是否到链表最后
    11.   while (temp != null) {
    12.       // 输出节点的信息
    13.       System.out.println(temp);
    14.       // 将temp后移， 一定小心
    15.       temp = temp.next;
    16.   }
    17. }

    尾部插入

    代码思路

  • 定义辅助变量 temp ，相当于一个指针，指向当前节点

  • 如何在链表末尾插入节点？
    • 首先需要遍历链表，找到链表最后一个节点，当 temp.next == null时，temp 节点指向链表最后一个节点
    • 然后在 temp 节点之后插入节点即可：temp.next = heroNode

20191210174857295.png

代码实现

  1. // 添加节点到单向链表
  2. // 思路，当不考虑编号顺序时
  3. // 1. 找到当前链表的最后节点
  4. // 2. 将最后这个节点的next 指向 新的节点
  5. public void add(HeroNode node) {
  6.     if (node == null) {
  7.         return;
  8.     }
  9.     HeroNode temp = head;
  10.     // 遍历链表，找到最后
  11.     while (temp.next != null) {
  12.         // 如果没有找到最后, 将temp后移
  13.         temp = temp.next;
  14.     }
  15.     // 当退出while循环时，temp就指向了链表的最后
  16.     // 将最后这个节点的next 指向 新的节点
  17.     temp.next = node;
  18. }

测试代码

  1. public class SingleLinkedListDemo {
  2.     public static void main(String[] args) {
  3.         // 进行测试
  4.         // 先创建节点
  5.         HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
  6.         HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
  7.         HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
  8.         HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
  9.         SingleLinkedList singleLinkedList = new SingleLinkedList();
  10.         singleLinkedList.add(hero1);
  11.         singleLinkedList.add(hero2);
  12.         singleLinkedList.add(hero3);
  13.         singleLinkedList.add(hero4);
  15.         singleLinkedList.list();
  16.     }
  17. }

按顺序插入

代码思路

  • 定义辅助变量 temp ，相当于一个指针，指向当前节点
  • 应该如何执行插入？（待插入节点为 heroNode）
    • 首先需要遍历链表，找到链表中编号值比 heroNode.no 大的节点，暂且叫它 biggerNode ，然后把 heroNode 插入到 biggerNode 之前即可
    • 怎么找 biggerNode ？当 temp.next.no > heroNode.no 时，这时 temp.next 节点就是 biggerNode 节点。
    • 为什么是 temp.next 节点？只有找到 temp 节点和 temp.next（biggerNode ）节点，才能在 temp 节点和 temp.next 节点之间插入 heroNode 节点
    • 怎么插入？
      • heroNode .next = temp.next;
      • temp.next = heroNode;

20191210174857295.png

代码实现

按照英雄排名的顺序进行插入

  1. // 第二种方式在添加英雄时，根据排名将英雄插入到指定位置
  2. // (如果有这个排名，则添加失败，并给出提示)
  3. public void addByOrder(HeroNode node) {
  4.     if (node == null) {
  5.         return;
  6.     }
  7.     // 因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
  8.     // 因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
  9.     HeroNode temp = head;
  10.     // flag标志添加的编号是否存在，默认为false
  11.     boolean flag = false;
  12.     // 遍历链表，找到最后
  13.     while (true) {
  14.         // 说明temp已经在链表的最后
  15.         if (temp.next == null) {
  16.             break;
  17.         }
  18.         // 位置找到，就在temp的后面插入
  19.         if (temp.next.no > node.no) {
  20.             break;
  21.         } else if (temp.no == node.no) {
  22.             // 说明希望添加的heroNode的编号已然存在
  23.             flag = true;
  24.             break;
  25.         }
  26.         // 后移，遍历当前链表
  27.         temp = temp.next;
  28.     }
  29.     if (flag) {
  30.         System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", node.no);
  31.     } else {
  32.         // 插入到链表中, temp的后面
  33.         node.next = temp.next;
  34.         temp.next = node;
  35.     }
  36. }

  • 测试代码

    1. public class SingleLinkedListDemo {
    2.   public static void main(String[] args) {
    3.       // 进行测试
    4.       // 先创建节点
    5.       HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
    6.       HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
    7.       HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
    8.       HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
    9.       SingleLinkedList singleLinkedList = new SingleLinkedList();
    11.       // 加入按照编号的顺序
    12.       singleLinkedList.addByOrder(hero2);
    13.       singleLinkedList.addByOrder(hero1);
    14.       singleLinkedList.addByOrder(hero3);
    15.       singleLinkedList.addByOrder(hero4);
    17.       singleLinkedList.list();
    18.   }
    19. }

    修改节点信息

    代码思路

  • 定义辅助变量 temp ，相当于一个指针，指向当前节点

  • 如何找到指定节点？temp.no = newHeroNode.no

    代码实现

    修改指定节点信息
    1. // 修改节点的信息, 根据no编号来修改，即no编号不能改.
    2. // 说明
    3. // 1. 根据 newHeroNode 的 no 来修改即可
    4. public void update(HeroNode newNode) {
    5.   if (newNode == null) {
    6.       return;
    7.   }
    8.   // 判断链表是否为空
    9.   if (head.next == null) {
    10.       System.out.println("链表为空");
    11.       return;
    12.   }
    13.   // 找到需要修改的节点, 根据no编号
    14.   // 定义一个辅助变量
    15.   HeroNode temp = head.next;
    16.   // 表示是否找到该节点
    17.   boolean flag = false;
    18.   while (true) {
    19.       if (temp == null) {
    20.           break;
    21.       }
    22.       if (temp.no == newNode.no) {
    23.           flag = true;
    24.           break;
    25.       }
    26.       temp = temp.next;
    27.   }
    28.   // 根据flag 判断是否找到要修改的节点
    29.   if (flag) {
    30.       temp.name = newNode.name;
    31.       temp.nickName = newNode.nickName;
    32.   } else {
    33.       System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newNode.no);
    34.   }
    35. }

测试代码

  1. /**
  2.  * @author shenguangyang
  3.  * @date 2022-02-27 16:52
  4.  */
  5. public class SingleLinkedListDemo {
  6.     public static void main(String[] args) {
  7.         // 进行测试
  8.         // 先创建节点
  9.         HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
  10.         HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
  11.         HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
  12.         HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
  13.         SingleLinkedList singleLinkedList = new SingleLinkedList();
  15.         // 加入按照编号的顺序
  16.         singleLinkedList.addByOrder(hero2);
  17.         singleLinkedList.addByOrder(hero1);
  18.         singleLinkedList.addByOrder(hero3);
  19.         singleLinkedList.addByOrder(hero4);
  20.         singleLinkedList.list();
  22.         // 测试修改节点的代码
  23.         HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
  24.         singleLinkedList.update(newHeroNode);
  25.         System.out.println("修改之后的链表数据: ");
  26.         singleLinkedList.list();
  27.     }
  28. }

删除节点

代码思路

  • 定义辅助变量 temp ，相当于一个指针，指向当前节点
  • 如何找到待删除的节点？遍历链表，当 temp.next == no 时，temp.next 节点就是待删除的节点
  • 如何删除？temp = temp.next.next 即可删除 temp.next 节点，该节点没有引用指向它，会被垃圾回收机制回收

20191210174857295.png

代码实现

删除指定节点

  1. // 删除节点
  2. // 思路
  3. // 1. head 不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
  4. // 2. 说明我们在比较时，是temp.next.no 和 需要删除的节点的no比较
  5. public void delete(int no) {
  6.     // 判断链表是否为空
  7.     if (head.next == null) {
  8.         System.out.println("链表为空");
  9.         return;
  10.     }
  11.     HeroNode temp = head;
  12.     // 标志是否找到待删除节点的
  13.     boolean flag = false;
  14.     while (true) {
  15.         // 已经到链表的最后
  16.         if (temp.next == null) {
  17.             break;
  18.         }
  19.         if (temp.next.no == no) {
  20.             // 找到的待删除节点的前一个节点temp
  21.             flag = true;
  22.             break;
  23.         }
  24.         // temp后移，遍历
  25.         temp = temp.next;
  26.     }
  27.     if (flag) {
  28.         temp.next = temp.next.next;
  29.     } else {
  30.         System.out.printf("要删除的 %d 节点不存在\n", no);
  31.     }
  32. }

测试代码

  1. public class SingleLinkedListDemo {
  2.     public static void main(String[] args) {
  3.         // 进行测试
  4.         // 先创建节点
  5.         HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
  6.         HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
  7.         HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
  8.         HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
  9.         SingleLinkedList singleLinkedList = new SingleLinkedList();
  11.         // 加入按照编号的顺序
  12.         singleLinkedList.addByOrder(hero2);
  13.         singleLinkedList.addByOrder(hero1);
  14.         singleLinkedList.addByOrder(hero3);
  15.         singleLinkedList.addByOrder(hero4);
  16.         singleLinkedList.list();
  18.         // 删除节点
  19.         singleLinkedList.delete(1);
  20.         singleLinkedList.delete(4);
  21.         singleLinkedList.delete(2);
  22.         System.out.println("删除之后的链表: ");
  23.         singleLinkedList.list();
  24.     }
  25. }

完整代码

  1. package com.concise.demo.data_structure.linked_list;
  3. /**
  4.  * @author shenguangyang
  5.  * @date 2022-02-27 16:52
  6.  */
  7. public class SingleLinkedListDemo {
  8.     public static void main(String[] args) {
  9.         // 进行测试
  10.         // 先创建节点
  11.         HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
  12.         HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
  13.         HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
  14.         HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
  15.         SingleLinkedList singleLinkedList = new SingleLinkedList();
  16. //        singleLinkedList.add(hero1);
  17. //        singleLinkedList.add(hero2);
  18. //        singleLinkedList.add(hero3);
  19. //        singleLinkedList.add(hero4);
  21.         // 加入按照编号的顺序
  22.         singleLinkedList.addByOrder(hero2);
  23.         singleLinkedList.addByOrder(hero1);
  24.         singleLinkedList.addByOrder(hero3);
  25.         singleLinkedList.addByOrder(hero4);
  26.         singleLinkedList.list();
  28.         // 测试修改节点的代码
  29.         HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
  30.         singleLinkedList.update(newHeroNode);
  31.         System.out.println("修改之后的链表数据: ");
  32.         singleLinkedList.list();
  34.         // 删除节点
  35.         singleLinkedList.delete(1);
  36.         singleLinkedList.delete(4);
  37.         singleLinkedList.delete(2);
  38.         System.out.println("删除之后的链表: ");
  39.         singleLinkedList.list();
  40.     }
  41. }
  43. /**
  44.  * 单链表
  45.  */
  46. class SingleLinkedList {
  47.     // 因为head节点不能动，因此我们需要一个辅助遍历 temp
  48.     private final HeroNode head = new HeroNode(0, "", "");
  50.     // 添加节点到单向链表
  51.     // 思路，当不考虑编号顺序时
  52.     // 1. 找到当前链表的最后节点
  53.     // 2. 将最后这个节点的next 指向 新的节点
  54.     public void add(HeroNode node) {
  55.         if (node == null) {
  56.             return;
  57.         }
  58.         HeroNode temp = head;
  59.         // 遍历链表，找到最后
  60.         while (temp.next != null) {
  61.             // 如果没有找到最后, 将temp后移
  62.             temp = temp.next;
  63.         }
  64.         // 当退出while循环时，temp就指向了链表的最后
  65.         // 将最后这个节点的next 指向 新的节点
  66.         temp.next = node;
  67.     }
  69.     // 第二种方式在添加英雄时，根据排名将英雄插入到指定位置
  70.     // (如果有这个排名，则添加失败，并给出提示)
  71.     public void addByOrder(HeroNode node) {
  72.         if (node == null) {
  73.             return;
  74.         }
  75.         // 因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
  76.         // 因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
  77.         HeroNode temp = head;
  78.         // flag标志添加的编号是否存在，默认为false
  79.         boolean flag = false;
  80.         // 遍历链表，找到最后
  81.         while (true) {
  82.             // 说明temp已经在链表的最后
  83.             if (temp.next == null) {
  84.                 break;
  85.             }
  86.             // 位置找到，就在temp的后面插入
  87.             if (temp.next.no > node.no) {
  88.                 break;
  89.             } else if (temp.no == node.no) {
  90.                 // 说明希望添加的heroNode的编号已然存在
  91.                 flag = true;
  92.                 break;
  93.             }
  94.             // 后移，遍历当前链表
  95.             temp = temp.next;
  96.         }
  97.         if (flag) {
  98.             System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", node.no);
  99.         } else {
  100.             // 插入到链表中, temp的后面
  101.             node.next = temp.next;
  102.             temp.next = node;
  103.         }
  104.     }
  106.     // 显示链表[遍历]
  107.     public void list() {
  108.         // 判断链表是否为空
  109.         if (head.next == null) {
  110.             System.out.println("链表为空");
  111.             return;
  112.         }
  113.         // 因为头节点，不能动，因此我们需要一个辅助变量来遍历
  114.         HeroNode temp = head.next;
  115.         // 判断是否到链表最后
  116.         while (temp != null) {
  117.             // 输出节点的信息
  118.             System.out.println(temp);
  119.             // 将temp后移， 一定小心
  120.             temp = temp.next;
  121.         }
  122.     }
  124.     // 修改节点的信息, 根据no编号来修改，即no编号不能改.
  125.     // 说明
  126.     // 1. 根据 newHeroNode 的 no 来修改即可
  127.     public void update(HeroNode newNode) {
  128.         if (newNode == null) {
  129.             return;
  130.         }
  131.         // 判断链表是否为空
  132.         if (head.next == null) {
  133.             System.out.println("链表为空");
  134.             return;
  135.         }
  136.         // 找到需要修改的节点, 根据no编号
  137.         // 定义一个辅助变量
  138.         HeroNode temp = head.next;
  139.         // 表示是否找到该节点
  140.         boolean flag = false;
  141.         while (true) {
  142.             if (temp == null) {
  143.                 break;
  144.             }
  145.             if (temp.no == newNode.no) {
  146.                 flag = true;
  147.                 break;
  148.             }
  149.             temp = temp.next;
  150.         }
  151.         // 根据flag 判断是否找到要修改的节点
  152.         if (flag) {
  153.             temp.name = newNode.name;
  154.             temp.nickName = newNode.nickName;
  155.         } else {
  156.             System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newNode.no);
  157.         }
  158.     }
  160.     // 删除节点
  161.     // 思路
  162.     // 1. head 不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
  163.     // 2. 说明我们在比较时，是temp.next.no 和 需要删除的节点的no比较
  164.     public void delete(int no) {
  165.         // 判断链表是否为空
  166.         if (head.next == null) {
  167.             System.out.println("链表为空");
  168.             return;
  169.         }
  170.         HeroNode temp = head;
  171.         // 标志是否找到待删除节点的
  172.         boolean flag = false;
  173.         while (true) {
  174.             // 已经到链表的最后
  175.             if (temp.next == null) {
  176.                 break;
  177.             }
  178.             if (temp.next.no == no) {
  179.                 // 找到的待删除节点的前一个节点temp
  180.                 flag = true;
  181.                 break;
  182.             }
  183.             // temp后移，遍历
  184.             temp = temp.next;
  185.         }
  186.         if (flag) {
  187.             temp.next = temp.next.next;
  188.         } else {
  189.             System.out.printf("要删除的 %d 节点不存在\n", no);
  190.         }
  191.     }
  192. }
  194. //定义HeroNode ， 每个HeroNode 对象就是一个节点
  195. class HeroNode {
  196.     // 英雄编号
  197.     public int no;
  198.     // 英雄名字
  199.     public String name;
  200.     // 英雄昵称
  201.     public String nickName;
  202.     // 指向下一个节点
  203.     public HeroNode next;
  205.     public HeroNode(int no, String name, String nickname) {
  206.         this.no = no;
  207.         this.name = name;
  208.         this.nickName = nickname;
  209.     }
  211.     // 为了显示方法，我们重写toString
  212.     @Override
  213.     public String toString() {
  214.         return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
  215.     }
  216. }

总结

  • 遍历链表，执行操作时，判断条件有时候是 temp ，有时候是 temp.next ，Why？
    • 对于插入、删除节点来说，需要知道当前待操作的节点（heroNode）前一个节点的地址（指针），如果直接定位至当前待操作的节点 heroNode ，那没得玩。。。因为不知道heroNode 前一个节点的地址，无法进行插入、删除操作，所以 while 循环中的条件使用 temp.next 进行判断
    • 对于更新、遍历操作来说，我需要的仅仅就只是当前节点的信息，所以 while 循环中的条件使用 temp进行判断


  • 头结点与首节点
    • 参考资料：https://blog.csdn.net/WYpersist/article/details/80288056
    • 头结点是为了操作的统一与方便而设立的，放在第一个元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。
    • 首元结点也就是第一个元素的结点，它是头结点后边的第一个结点。