• Java 数据结构篇-实现单链表核心API

    🔥博客主页： 小扳_-CSDN博客
    ❤感谢大家点赞👍收藏⭐评论✍       

    文章目录

            1.0 单链表的说明

            2.0 单链表的创建

            2.1 单链表 - 头插节点

            2.2 单链表 - 遍历

            2.2.1 使用简单的 for/while 循环

            2.2.2 实现 forEach 方法

            2.2.3 实现迭代器的方法

            2.3 单链表 - 尾插节点

            2.4 单链表 - 通过索引获取数据

            2.5 单链表 - 通过索引插入数据

            2.6 单链表 - 头删节点

            2.7 单链表 - 根据节点来删除数据

             3.0 实现单链表的完整代码

            4.0 实现加 "哨兵" 的单链表 

            1.0 单链表的说明

            单链表是一种数据结构。数据结构是指数据的组织、管理和存储的方式，而单链表是一种常见的线性数据结构，用于存储一系列具有相同类型的元素。它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。单链表可以通过指针的方式实现元素的插入、删除和查找等操作。

            2.0 单链表的创建

           把单链表封装成一个类，面向对象编程的思路。类中需要的成员变量为头节点、节点，又可以把节点封装成一个类，为更好把节点类封装起来，将其设置为静态内部类。

    代码如下：

    1. public class SingleLists{
    2.     //头节点
    3.     private Node hand = null;
    4.  
    5.  
    6.     //节点
    7.     private static class Node {
    8.         //数据
    9.         private int data;
    10.         //指向下一个节点
    11.         private Node next;
    12.  
    13.         public Node() {
    14.         }
    15.  
    16. }

            注意的是，这些成员都不会对外访问的，所以需要把成员变为私有成员。

            2.1 单链表 - 头插节点

           顾名思义，就是在头节点处插入新的节点，使其成为新的头节点。需要考虑两种情况，第一种情况，头节点为 null 时，直接就可以将创建出来的对象被 hand 引用了。第二种情况，头节点不为 null 时，需要将创建的对象的 next 引用指向 hand 的引用，而当前创建的对象就要被 hand 引用。

    代码如下：

    1.     //实现头插节点
    2.     public void addFirst(int data) {
    3. /*        if (hand == null){
    4.             hand = new Node(data,null);
    5.         }else {
    6.             hand = new Node(data,hand);
    7.         }*/
    8.         
    9.         //对以上代码进行简化得以下代码：
    10.         hand = new Node(data,hand);
    11.         
    12.     }

            需要注意的时，该 API 是对外访问。

            2.2 单链表 - 遍历

            实现遍历的方式有三种：

            第一种方式，使用简单的 for/while 循环。

            第二种方式，实现 forEach 方法。

            第三种方式，实现迭代器的方法。

            2.2.1 使用简单的 for/while 循环

            一般 hand 是不会去移动或者去改变其引用，则需要临时的变量 p 来指向 hand 的对象。循环的条件为 p != null，每一次循环结束都需要 p 去移动到下一个节点处，p = p.next 。

    代码如下：

    1.     //遍历方式：打印方式
    2.     public void myPrint(){
    3.         if (hand == null){
    4.             throw new RuntimeException("hand is null！！！！");
    5.         }
    6.         //第一种：
    7. /*        Node p = hand;
    8.         //用while来实现
    9.         while (p != null){
    10.             System.out.println(p.data);
    11.             p = p.next;
    12.         }*/
    13.         //第二种：
    14.         //用for来实现
    15.         for (Node p = hand;p !=null;p = p.next){
    16.             System.out.println(p.data);
    17.         }
    18.     }

            还需要注意，for 与 while 这两种的实现逻辑是一样的，假如 hand 的引用为空，则没必要去循环了，直接去抛出错误。

            2.2.2 实现 forEach 方法

            对于 for/while 的遍历方法直接把 “方法写死了”，forEeach 方法是对 for/while 的方法进行了升级。参数为 Consumer 内部类，再重写 accept 方法。

    代码如下：

    1.     //遍历方式:实现forEach，由于跟以下的代码有冲突，先改名为 myForEach。
    2.     public void myForEach(Consumer consumer){
    3.         for (Node p = hand; p != null;p = p.next){
    4.             consumer.accept(p.data);
    5.         }
    6.     }

    具体调用该方法的使用：

    1.         singleLists.myForEach(new Consumer() {
    2.             @Override
    3.             public void accept(Integer integer) {
    4.                 System.out.println(integer);
    5.             }
    6.         });

            这样对外获取的数据可以自由支配使用，不仅仅打印输出了。

            2.2.3 实现迭代器的方法

            需要实现接口 Iterable ，该接口支持泛型，目前先实现整数类型的单链表。重写 hasNext() 与 next() 方法。

    代码如下：

    1.     //遍历方式：使用迭代器循环
    2.     @Override
    3.     public Iterator iterator() {
    4.         return new Iterator() {
    5.             Node p = hand;
    6.             @Override
    7.             public boolean hasNext() {
    8.                 return p != null;
    9.             }
    10.  
    11.             @Override
    12.             public Integer next() {
    13.                 int k = p.data;
    14.                 p = p.next;
    15.                 return k;
    16.             }
    17.         };

            重写完的 hasNext() 这个方法的作用：是判断当前 p 是否为 null ，如果是就停止遍历，结束了。反之继续遍历下去。

            重写之后的 next() 方法的作用：做了两个动作，第一个动作就是获取当前的数据；第二个动作就是将 p 移向下一个节点。

    具体调用该方法的使用：

    1.         for (Integer value:singleLists) {
    2.             System.out.println(value);
    3.         }

            同理，这个方式不仅仅只有打印输出了，自由支配使用。

            2.3 单链表 - 尾插节点

            找最后的节点后面插入新的节点，如果只有头节点，需要不断的遍历，直到最后一个节点。遍历的条件为 p.next != null，跟以上的条件需要区别开来，这里需要得到最后的节点，可不能 p !=null 一直下去，这样就会找不到最后的节点。

    代码如下：

    1.     //尾插节点
    2.     public void addLast(int data) {
    3.         if (hand == null) {
    4.             addFirst(data);
    5.             return;
    6.         }
    7.         Node p = hand;
    8.         while (p.next != null){
    9.             p = p.next;
    10.         }
    11.         p.next = new Node(data,null);
    12.     }

            需要注意的是，单独分开当 hand 为 null 时，因为 hand.next == null 了，但是对于hand 为 null 时也可以插入节点呀，所以 当 hand 为 null 时，可以调用头插节点的方法。

            2.4 单链表 - 通过索引获取数据

            单链表是不连续的，不用直接通过索引来访问节点去读取数据，因此，先独立设置一个方法，需设置一个 i 记数点，每一个遍历完 i++ ,直到 i == index 时，先返回该节点。再独立另一个方法，通过该节点来读取该数据。

    代码如下：

    1.     //根据索引获取某个节点
    2.     private Node findNode(int index) {
    3.         int i = 0;
    4.         for (Node p = hand ; p != null ; p = p.next,i++)
    5.         {
    6.             if (i == index) {
    7.                 return p;
    8.             }
    9.         }
    10.         return null;
    11.     }
    12.  
    13.  
    14.  
    15.     //根据索引得到对应的数据
    16.     public int get(int index) {
    17.         Node p = findNode(index);
    18.         if (p == null){
    19.             throw new RuntimeException("找不到该索引!!!");
    20.         }
    21.         return p.data;
    22.     }

            对于找不到的节点，需要抛出异常，需要注意的是，findNode 方法是不对外访问的，需要封装起来。

            2.5 单链表 - 通过索引插入数据

            先获取插入位置的前一个 prev 节点，然后 prev.next 去指向插入的节点的对象，插入节点的 next 去引用原先 prev.next 的对象。

    代码如下：

    1.     //根据索引插入数据
    2.     public void insert(int index , int data){
    3.         if (index == 0){
    4.             addFirst(data);
    5.         }
    6.         Node prev = findNode(index - 1);
    7.         if (prev == null){
    8.             throw new RuntimeException("index is illegal");
    9.         }
    10.         prev.next =  new Node(data,prev.next);
    11.     }

             需要注意的是，先判断插入点是否为头节点，如果是头节点，则调用头插的方法。再去判断其他情况通过 findNode() 方法是否得到 null，如果是，需要抛出异常。

            2.6 单链表 - 头删节点

            顾名思义直接删除头节点，思路为： hand 这个引用需要指向 hand.next ，这就是删除了第一个节点，没用引用的对象，在 Java 中回自动回收的，不会占内存，这也就是删除了。

    代码如下：

    1.     //头删节点
    2.     public void removeFirst() {
    3.         if (hand == null){
    4.             throw new RuntimeException("There are no nodes anymore");
    5.         }
    6.         hand = hand.next;
    7.     }

            需要注意，删除前先判断 hand 是否为 null 。

            2.7 单链表 - 根据节点来删除数据

            先找到要删除节点的前一个 prev 节点，然后再去找到 要删除的节点 move = prev.next ，接着将 prev.next = move.next 即可。

    代码如下：

    1.     //根据索引来删除节点
    2.     public void remove(int index) {
    3.         if (index == 0) {
    4.             removeFirst();
    5.             return;
    6.         }
    7.         Node prev = findNode(index - 1);
    8.         if (prev == null){
    9.             throw new RuntimeException("There are no nodes anymore");
    10.         }
    11.         Node move = prev.next;
    12.         if (move == null) {
    13.             throw new RuntimeException("There are no nodes anymore");
    14.         }
    15.         prev.next = move.next;
    16.     }

            在删除节点的时候需要先判断 index 是否为 0，如果是，则调用头删的方法，再通过 findNode() 方法来找到删除节点的前一个节点，如果得到的节点为 null，则需要抛出异常，同样的如果得到的需要删除的节点为 null ，则需要抛出异常。

     

             3.0 实现单链表的完整代码

    1.  
    2. import java.util.Iterator;
    3. import java.util.function.Consumer;
    4.  
    5. //整体
    6. public class SingleLists implements Iterable{
    7.     //头节点
    8.     private Node hand = null;
    9.  
    10.  
    11.     //节点
    12.     private static class Node {
    13.         //数据
    14.         private int data;
    15.         //指向下一个节点
    16.         private Node next;
    17.  
    18.         public Node() {
    19.         }
    20.  
    21.         public Node(int data, Node next) {
    22.             this.data = data;
    23.             this.next = next;
    24.         }
    25.     }
    26.  
    27.     //实现头插节点
    28.     public void addFirst(int data) {
    29. /*        if (hand == null){
    30.             hand = new Node(data,null);
    31.         }else {
    32.             hand = new Node(data,hand);
    33.         }*/
    34.  
    35.         //对以上代码进行简化得以下代码：
    36.         hand = new Node(data,hand);
    37.  
    38.     }
    39.  
    40.     //遍历方式：打印方式
    41.     public void myPrint(){
    42.         if (hand == null){
    43.             throw new RuntimeException("hand is null！！！！");
    44.         }
    45.         //第一种：
    46. /*        Node p = hand;
    47.         //用while来实现
    48.         while (p != null){
    49.             System.out.println(p.data);
    50.             p = p.next;
    51.         }*/
    52.         //第二种：
    53.         //用for来实现
    54.         for (Node p = hand;p !=null;p = p.next){
    55.             System.out.println(p.data);
    56.         }
    57.     }
    58.  
    59.     //遍历方式:实现forEach，由于跟以下的代码有冲突，先改名为 myForEach。
    60.     public void myForEach(Consumer consumer){
    61.         for (Node p = hand; p != null;p = p.next){
    62.             consumer.accept(p.data);
    63.         }
    64.     }
    65.  
    66.     //遍历方式：使用迭代器循环
    67.     @Override
    68.     public Iterator iterator() {
    69.         return new Iterator() {
    70.             Node p = hand;
    71.             @Override
    72.             public boolean hasNext() {
    73.                 return p != null;
    74.             }
    75.  
    76.             @Override
    77.             public Integer next() {
    78.                 int k = p.data;
    79.                 p = p.next;
    80.                 return k;
    81.             }
    82.         };
    83.     }
    84.  
    85.     //尾插节点
    86.     public void addLast(int data) {
    87.         if (hand == null) {
    88.             addFirst(data);
    89.             return;
    90.         }
    91.         Node p = hand;
    92.         while (p.next != null){
    93.             p = p.next;
    94.         }
    95.         p.next = new Node(data,null);
    96.     }
    97.  
    98.     //根据索引获取某个节点
    99.     private Node findNode(int index) {
    100.         int i = 0;
    101.         for (Node p = hand ; p != null ; p = p.next,i++)
    102.         {
    103.             if (i == index) {
    104.                 return p;
    105.             }
    106.         }
    107.         return null;
    108.     }
    109.  
    110.     //根据索引得到对应的数据
    111.     public int get(int index) {
    112.         Node p = findNode(index);
    113.         if (p == null){
    114.             throw new RuntimeException("找不到该索引!!!");
    115.         }
    116.         return p.data;
    117.     }
    118.  
    119.     //根据索引插入数据
    120.     public void insert(int index , int data){
    121.         if (index == 0){
    122.             addFirst(data);
    123.         }
    124.         Node prev = findNode(index - 1);
    125.         if (prev == null){
    126.             throw new RuntimeException("index is illegal");
    127.         }
    128.         prev.next =  new Node(data,prev.next);
    129.     }
    130.  
    131.     //头删节点
    132.     public void removeFirst() {
    133.         if (hand == null){
    134.             throw new RuntimeException("There are no nodes anymore");
    135.         }
    136.         hand = hand.next;
    137.     }
    138.  
    139.     //根据索引来删除节点
    140.     public void remove(int index) {
    141.         if (index == 0) {
    142.             removeFirst();
    143.             return;
    144.         }
    145.         Node prev = findNode(index - 1);
    146.         if (prev == null){
    147.             throw new RuntimeException("There are no nodes anymore");
    148.         }
    149.         Node move = prev.next;
    150.         if (move == null) {
    151.             throw new RuntimeException("There are no nodes anymore");
    152.         }
    153.         prev.next = move.next;
    154.     }
    155.  
    156.  
    157. }

            4.0 实现加 "哨兵" 的单链表 

            哨兵是单链表中的一个特殊节点，它不在乎存储什么数据元素，只用于标记链表的开始或结束。在单链表中，通常有一个头节点作为链表的起始位置。而哨兵节点是在头节点之前或尾节点之后的一个额外节点，用于简化链表的操作。简单来说，就是 hand 不在为 null ,始终有节点，这么一来，就会节省了考虑 hand == null 的情况发生了，写出来的代码更加简洁了。

    加 "哨兵" 的代码如下：

    1. import java.util.Iterator;
    2. import java.util.function.Consumer;
    3.  
    4. //整体
    5. public class SingleLists implements Iterable{
    6.     //头节点
    7.     private final Node hand = new Node(0,null);
    8.  
    9.  
    10.     //节点
    11.     private static class Node {
    12.         //数据
    13.         private int data;
    14.         //指向下一个节点
    15.         private Node next;
    16.  
    17.         public Node() {
    18.         }
    19.  
    20.         public Node(int data, Node next) {
    21.             this.data = data;
    22.             this.next = next;
    23.         }
    24.     }
    25.  
    26.     //实现头插节点
    27.     public void addFirst(int data) {
    28.         //对以上代码进行简化得以下代码：
    29.         //hand.next = new Node(data,hand.next);
    30.         insert(0,data);
    31.  
    32.     }
    33.  
    34.     //遍历方式：打印方式
    35.     public void myPrint(){
    36.         for (Node p = hand.next;p !=null;p = p.next){
    37.             System.out.println(p.data);
    38.         }
    39.     }
    40.  
    41.     //遍历方式:实现forEach，由于跟以下的代码有冲突，先改名为 myForEach。
    42.     public void myForEach(Consumer consumer){
    43.         for (Node p = hand.next; p != null;p = p.next){
    44.             consumer.accept(p.data);
    45.         }
    46.     }
    47.  
    48.     //遍历方式：使用迭代器循环
    49.     @Override
    50.     public Iterator iterator() {
    51.         return new Iterator() {
    52.             Node p = hand.next;
    53.             @Override
    54.             public boolean hasNext() {
    55.                 return p != null;
    56.             }
    57.  
    58.             @Override
    59.             public Integer next() {
    60.                 int k = p.data;
    61.                 p = p.next;
    62.                 return k;
    63.             }
    64.         };
    65.     }
    66.  
    67.     //尾插节点
    68.     public void addLast(int data) {
    69.         Node p = hand;
    70.         while (p.next != null){
    71.             p = p.next;
    72.         }
    73.         p.next = new Node(data,null);
    74.     }
    75.  
    76.     //根据索引获取某个节点
    77.     private Node findNode(int index) {
    78.         int i = -1;
    79.         for (Node p = hand ; p != null ; p = p.next,i++)
    80.         {
    81.             if (i == index) {
    82.                 return p;
    83.             }
    84.         }
    85.         return null;
    86.     }
    87.  
    88.     //根据索引得到对应的数据
    89.     public int get(int index) {
    90.         Node p = findNode(index);
    91.         if (p == null){
    92.             throw new RuntimeException("找不到该索引!!!");
    93.         }
    94.         return p.data;
    95.     }
    96.  
    97.     //根据索引插入数据
    98.     public void insert(int index , int data){
    99.         Node prev = findNode(index - 1);
    100.         if (prev == null){
    101.             throw new RuntimeException("index is illegal");
    102.         }
    103.         prev.next =  new Node(data,prev.next);
    104.     }
    105.  
    106.     //头删节点
    107.     public void removeFirst() {
    108.         //hand = hand.next;
    109.         remove(0);
    110.     }
    111.  
    112.     //根据索引来删除节点
    113.     public void remove(int index) {
    114.         Node prev = findNode(index - 1);
    115.         if (prev == null){
    116.             throw new RuntimeException("There are no nodes anymore");
    117.         }
    118.         Node move = prev.next;
    119.         if (move == null) {
    120.             throw new RuntimeException("There are no nodes anymore");
    121.         }
    122.         prev.next = move.next;
    123.     }
    124. }

            需要注意的是，哨兵节点并不是必需的，可以根据具体的需求来决定是否使用哨兵节点。在某些情况下，如果链表的操作较为简单，不涉及插入和删除等复杂操作，可以不使用哨兵节点来简化代码。

     

  • 相关阅读:
    2024年最新版FL Studio21.2.3 Build 4004 for Mac 版激活下载和图文激活教程
    电脑蓝牙与ESP32蓝牙连接，让电脑发现ESP32
    Python3 安装 Matplotlib 报错 pip 无法卸载 pillow 解决方案
    归并排序（C）递归与分治策略
    PO接口日志 RSXMB_SHOW_STATUS 统计消息状态概览
    SQL基本查询
    软件设计模式白话文系列（九）装饰者模式
    JavaDS —— 单链表 与 LinkedList
    贰[2]，OpenCV函数解析
    网络编程TP/IP （尹圣雨）（韩） 第二章 课后习题
  • 原文地址：https://blog.csdn.net/Tingfeng__/article/details/134231658