1. Toy模板网首页
  2. > Toy博客

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

9月前 作者：小扳 分类：Toy博客 阅读(47) 违法举报

这篇具有很好参考价值的文章主要介绍了Java 数据结构篇-实现单链表核心API。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

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

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

文章目录

        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 单链表的创建

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

代码如下：

public class SingleLists{
    //头节点
    private Node hand = null;


    //节点
    private static class Node {
        //数据
        private int data;
        //指向下一个节点
        private Node next;

        public Node() {
        }

}

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

        2.1 单链表 - 头插节点

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

代码如下：

    //实现头插节点
    public void addFirst(int data) {
/*        if (hand == null){
            hand = new Node(data,null);
        }else {
            hand = new Node(data,hand);
        }*/
        
        //对以上代码进行简化得以下代码：
        hand = new Node(data,hand);
        
    }

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

        2.2 单链表 - 遍历

        实现遍历的方式有三种：

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

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

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

        2.2.1 使用简单的 for/while 循环

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

代码如下：

    //遍历方式：打印方式
    public void myPrint(){
        if (hand == null){
            throw new RuntimeException("hand is null！！！！");
        }
        //第一种：
/*        Node p = hand;
        //用while来实现
        while (p != null){
            System.out.println(p.data);
            p = p.next;
        }*/
        //第二种：
        //用for来实现
        for (Node p = hand;p !=null;p = p.next){
            System.out.println(p.data);
        }
    }

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

        2.2.2 实现 forEach 方法

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

代码如下：

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

具体调用该方法的使用：

        singleLists.myForEach(new Consumer<Integer>() {
            @Override
            public void accept(Integer integer) {
                System.out.println(integer);
            }
        });

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

        2.2.3 实现迭代器的方法

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

代码如下：

    //遍历方式：使用迭代器循环
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = hand;
            @Override
            public boolean hasNext() {
                return p != null;
            }

            @Override
            public Integer next() {
                int k = p.data;
                p = p.next;
                return k;
            }
        };

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

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

具体调用该方法的使用：

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

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

        2.3 单链表 - 尾插节点

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

代码如下：

    //尾插节点
    public void addLast(int data) {
        if (hand == null) {
            addFirst(data);
            return;
        }
        Node p = hand;
        while (p.next != null){
            p = p.next;
        }
        p.next = new Node(data,null);
    }

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

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

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

代码如下：

    //根据索引获取某个节点
    private Node findNode(int index) {
        int i = 0;
        for (Node p = hand ; p != null ; p = p.next,i++)
        {
            if (i == index) {
                return p;
            }
        }
        return null;
    }



    //根据索引得到对应的数据
    public int get(int index) {
        Node p = findNode(index);
        if (p == null){
            throw new RuntimeException("找不到该索引!!!");
        }
        return p.data;
    }

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

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

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

代码如下：

    //根据索引插入数据
    public void insert(int index , int data){
        if (index == 0){
            addFirst(data);
        }
        Node prev = findNode(index - 1);
        if (prev == null){
            throw new RuntimeException("index is illegal");
        }
        prev.next =  new Node(data,prev.next);
    }

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

        2.6 单链表 - 头删节点

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

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

代码如下：

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

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

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

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

代码如下：

    //根据索引来删除节点
    public void remove(int index) {
        if (index == 0) {
            removeFirst();
            return;
        }
        Node prev = findNode(index - 1);
        if (prev == null){
            throw new RuntimeException("There are no nodes anymore");
        }
        Node move = prev.next;
        if (move == null) {
            throw new RuntimeException("There are no nodes anymore");
        }
        prev.next = move.next;
    }

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

 

         3.0 实现单链表的完整代码


import java.util.Iterator;
import java.util.function.Consumer;

//整体
public class SingleLists implements Iterable<Integer>{
    //头节点
    private Node hand = null;


    //节点
    private static class Node {
        //数据
        private int data;
        //指向下一个节点
        private Node next;

        public Node() {
        }

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    //实现头插节点
    public void addFirst(int data) {
/*        if (hand == null){
            hand = new Node(data,null);
        }else {
            hand = new Node(data,hand);
        }*/

        //对以上代码进行简化得以下代码：
        hand = new Node(data,hand);

    }

    //遍历方式：打印方式
    public void myPrint(){
        if (hand == null){
            throw new RuntimeException("hand is null！！！！");
        }
        //第一种：
/*        Node p = hand;
        //用while来实现
        while (p != null){
            System.out.println(p.data);
            p = p.next;
        }*/
        //第二种：
        //用for来实现
        for (Node p = hand;p !=null;p = p.next){
            System.out.println(p.data);
        }
    }

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

    //遍历方式：使用迭代器循环
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = hand;
            @Override
            public boolean hasNext() {
                return p != null;
            }

            @Override
            public Integer next() {
                int k = p.data;
                p = p.next;
                return k;
            }
        };
    }

    //尾插节点
    public void addLast(int data) {
        if (hand == null) {
            addFirst(data);
            return;
        }
        Node p = hand;
        while (p.next != null){
            p = p.next;
        }
        p.next = new Node(data,null);
    }

    //根据索引获取某个节点
    private Node findNode(int index) {
        int i = 0;
        for (Node p = hand ; p != null ; p = p.next,i++)
        {
            if (i == index) {
                return p;
            }
        }
        return null;
    }

    //根据索引得到对应的数据
    public int get(int index) {
        Node p = findNode(index);
        if (p == null){
            throw new RuntimeException("找不到该索引!!!");
        }
        return p.data;
    }

    //根据索引插入数据
    public void insert(int index , int data){
        if (index == 0){
            addFirst(data);
        }
        Node prev = findNode(index - 1);
        if (prev == null){
            throw new RuntimeException("index is illegal");
        }
        prev.next =  new Node(data,prev.next);
    }

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

    //根据索引来删除节点
    public void remove(int index) {
        if (index == 0) {
            removeFirst();
            return;
        }
        Node prev = findNode(index - 1);
        if (prev == null){
            throw new RuntimeException("There are no nodes anymore");
        }
        Node move = prev.next;
        if (move == null) {
            throw new RuntimeException("There are no nodes anymore");
        }
        prev.next = move.next;
    }


}

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

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

加 "哨兵" 的代码如下：

import java.util.Iterator;
import java.util.function.Consumer;

//整体
public class SingleLists implements Iterable<Integer>{
    //头节点
    private final Node hand = new Node(0,null);


    //节点
    private static class Node {
        //数据
        private int data;
        //指向下一个节点
        private Node next;

        public Node() {
        }

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    //实现头插节点
    public void addFirst(int data) {
        //对以上代码进行简化得以下代码：
        //hand.next = new Node(data,hand.next);
        insert(0,data);

    }

    //遍历方式：打印方式
    public void myPrint(){
        for (Node p = hand.next;p !=null;p = p.next){
            System.out.println(p.data);
        }
    }

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

    //遍历方式：使用迭代器循环
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = hand.next;
            @Override
            public boolean hasNext() {
                return p != null;
            }

            @Override
            public Integer next() {
                int k = p.data;
                p = p.next;
                return k;
            }
        };
    }

    //尾插节点
    public void addLast(int data) {
        Node p = hand;
        while (p.next != null){
            p = p.next;
        }
        p.next = new Node(data,null);
    }

    //根据索引获取某个节点
    private Node findNode(int index) {
        int i = -1;
        for (Node p = hand ; p != null ; p = p.next,i++)
        {
            if (i == index) {
                return p;
            }
        }
        return null;
    }

    //根据索引得到对应的数据
    public int get(int index) {
        Node p = findNode(index);
        if (p == null){
            throw new RuntimeException("找不到该索引!!!");
        }
        return p.data;
    }

    //根据索引插入数据
    public void insert(int index , int data){
        Node prev = findNode(index - 1);
        if (prev == null){
            throw new RuntimeException("index is illegal");
        }
        prev.next =  new Node(data,prev.next);
    }

    //头删节点
    public void removeFirst() {
        //hand = hand.next;
        remove(0);
    }

    //根据索引来删除节点
    public void remove(int index) {
        Node prev = findNode(index - 1);
        if (prev == null){
            throw new RuntimeException("There are no nodes anymore");
        }
        Node move = prev.next;
        if (move == null) {
            throw new RuntimeException("There are no nodes anymore");
        }
        prev.next = move.next;
    }
}

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

 

Java 数据结构篇-实现单链表核心API,数据结构,java文章来源地址https://www.toymoban.com/news/detail-744984.html

到了这里，关于Java 数据结构篇-实现单链表核心API的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • java数据结构与算法：单链表 SinglyLinkedList

    java数据结构与算法：单链表 SinglyLinkedList

    2024年01月20日
    浏览(52)
  • 【数据结构】-- 单链表的实现

    【数据结构】-- 单链表的实现

    在前面我们学习了顺序表，顺序表在数组的基础上提供了很多现成的方法，方便了我们对数据的管理，但是我们也发现顺序表有着许多不足： 在处理大型的数据时，需要频繁的增容且在中间删除或插入数据时需要遍历顺序表，这些性质导致了顺序表的 效率较低 。这时我们就

    2024年04月27日
    浏览(49)
  • 数据结构之单链表及其实现！

    数据结构之单链表及其实现！

    目录 ​编辑 1.  顺序表的问题及思考 2.链表的概念结构和分类 2.1 概念及结构 2.2 分类 3. 单链表的实现 3.1 新节点的创建 3.2 打印单链表 3.3 头插 3.4 头删 3.5 尾插 3.6 尾删 3.7 查找元素X 3.8 在pos位置修改 3.9 在任意位置之前插入 3.10 在任意位置删除 3.11 单链表的销毁 4. 完整代码

    2024年03月12日
    浏览(55)
  • 【（数据结构）— 单链表的实现】

    【（数据结构）— 单链表的实现】

    概念： 链表是⼀种 物理存储结构上非连续、 非顺序的存储结构，数据元素的 逻辑顺序 是通过链表中的 指针链接 次序实现的 。 链表的结构跟⽕⻋⻋厢相似，淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/加上，不会影响

    2024年02月08日
    浏览(48)
  • 【数据结构】单链表的实现

    【数据结构】单链表的实现

    🌇个人主页：平凡的小苏 📚学习格言：别人可以拷贝我的模式，但不能拷贝我不断往前的激情 🛸C语言专栏：https://blog.csdn.net/vhhhbb/category_12174730.html 🚀数据结构专栏：https://blog.csdn.net/vhhhbb/category_12211053.html         家人们更新不易，你们的👍点赞👍和⭐关注⭐真的对我

    2023年04月09日
    浏览(62)
  • 【数据结构—单链表的实现】

    【数据结构—单链表的实现】

    提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档 目录 前言 1. 链表的概念及结构 2. 单链表的实现 2.1单链表头文件——功能函数的定义 2.2单链表源文件——功能函数的实现 2.3 单链表源文件——功能的测试 3.具体的理解操作图 4. 链表的分类 总结 世上

    2024年02月05日
    浏览(62)
  • 【数据结构——队列的实现（单链表）】

    【数据结构——队列的实现（单链表）】

    1.出入队列的方式：队尾进入，对首出队列。 2.出队列和入队列的关系是：一对一的。

    2024年02月04日
    浏览(45)

  • 【数据结构】单链表完整代码实现

    前置文章：顺序表的代码实现 每个结点除了存放数据元素外，还要存储指向下一个结点的指针。 不要求大片连续空间 改变容量方便 不可随机存取 要耗费一定空间存放指针 代码结构： 定义单链表结构 初始化单链表 单链表的取值方法 单链表的查找方法 单链表的插入方法 单

    2024年02月07日
    浏览(37)

  • 【数据结构】Golang 实现单链表

    通过指针将一组零散的内存块串联在一起 ， 把内存块称为链表的“ 结点 ”。 记录下个结点地址的指针叫作 后继指针 next ，第一个结点叫作 头结点 ，把最后一个结点叫作 尾结点 。 定义单链表 在 golang 中可以通过结构体定义单链表： 操作单链表 使用 golang 实现单链表常用

    2024年02月10日
    浏览(41)
  • 【数据结构】单链表的简单实现

    【数据结构】单链表的简单实现

    提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档 单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元

    2024年02月04日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包