Java实现单向链表

于 2023-03-04 14:33:06 发布
阅读量719 收藏
点赞数 2
分类专栏： Java数据结构与算法 文章标签： 链表 java 数据结构
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/XUHUANGHOST/article/details/129333847
版权

✅作者简介：热爱Java后端开发的一名学习者，大家可以跟我一起讨论各种问题喔。
🍎个人主页：Hhzzy99
🍊个人信条：坚持就是胜利！
💞当前专栏：Java数据结构与算法
🥭本文内容：Java实现单向链表的两种形式

单向链表

文章目录

单向链表的特点

单向链表，顾名思义它是单向的，一个节点有数据部分和next指针部分组成，数据部分用来保存数据，next指针指向下一个节点，所以单向链表的每个节点都只知道下一个节点是什么，而不知道上一个节点是什么。
在这里插入图片描述

单向链表代码实现（无哨兵）

/***
 *@description:单向链表
 *@author: Hhzzy99
 *@date:2023/3/4
 **/
public class SinglyLinkedList implements Iterable<Integer>{//整体
    private Node head = null;//头指针

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = head;
            @Override
            public boolean hasNext() {//是否有下一个元素
                return p != null;
            }

            @Override
            public Integer next() {//返回当前值，并指向下一个元素
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    /**
     * 节点类
     */
    private static class Node{
        int value;//值
        Node next;//下一个结点指针
        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
    /**
     * 链表头添加元素
     * @param value 元素值
     */
    public void addFirst(int value){
        //1.链表为空
//        head = new Node(value,null);
        //2.链表非空
        head = new Node(value,head);
    }

    //链表遍历
    public void loop1(Consumer<Integer> consumer){
        Node p = head;
        while(p != null){
            consumer.accept(p.value);
            p = p.next;
        }
    }

    /**
     * for循环＋函数式接口Consumer
     * @param consumer 函数式接口
     */
    public void loop2(Consumer<Integer> consumer){
        for (Node p = head; p != null; p = p.next){
            consumer.accept(p.value);
        }
    }

    /**
     * 最后一个元素
     * @return Node p
     */
    private Node findLast(){
        if(head == null)
            return null;
        Node p;
        for(p = head; p.next != null; p = p.next){
        }
        return p;
    }

    /**
     * 最后面添加元素
     * @param value 元素值
     */
    public void addLast(int value){
        Node last = findLast();
        if(last == null){
            addFirst(value);
            return;
        }
        last.next = new Node(value,null);
    }

    /**
     * 寻找索引为index的元素
     * @param index 寻找的元素的索引
     * @return Node p
     */
    private Node findNode(int index){
        int i = 0;
        for(Node p = head; p.next != null; p = p.next,i++){
            if(i == index)
                return p;
        }
        return null;
    }
    /**
     * 获取索引位置的元素
     * @param index 索引值
     * @throws IllegalArgumentException - 找不到索引，抛出index非法异常
     */
    public int get(int index){
        Node p = findNode(index);
        if(p == null)
            //抛异常
            throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));
        return p.value;
    }

    /**
     * 向索引位置插入元素
     * @param index 索引值
     * @param value 待插入值
     * @throws IllegalArgumentException - 找不到索引，抛出index非法异常
     */
    public void insert(int index, int value){
        if(index == 0){
            addFirst(value);
            return;
        }
        Node prev = findNode(index - 1);//找到上一个节点
        if (prev == null)//找不到
            throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));
        prev.next = new Node(value,prev.next);
    }

    /**
     * 删除第一个元素
     * @throws IllegalArgumentException - 找不到索引，抛出index非法异常
     */
    public void removeFirst(){
        if(head == null)
            throw new IllegalArgumentException(String.format("index [%d] 不合法%n",0));
        head = head.next;
    }

    /**
     * 删除索引为index的元素
     * @param index 要删除元素的索引值
     * @throws IllegalArgumentException - 找不到索引，抛出index非法异常
     */
    public void remove(int index){
        if(index == 0){
            removeFirst();
            return;
        }
        Node prev = findNode(index - 1);//上一个节点
        if (prev == null)
            throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));
        if (prev.next == null)
            throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));
        prev.next = prev.next.next;//prev.next是被删除的元素

    }
}

测试T1

/***
 *@description:测试
 *@author: Hhzzy99
 *@date:2023/3/4
 **/
public class TestSinglyLinkedList {
    private SinglyLinkedList getSinglyLinkedList() {
        //addFirst    addLast
        SinglyLinkedList singlyLinkedList = new SinglyLinkedList();
        singlyLinkedList.addFirst(1);
        singlyLinkedList.addLast(2);
        singlyLinkedList.addLast(3);
        singlyLinkedList.addLast(4);
        return singlyLinkedList;
    }

    @Test
    //测试get()
    public void test01(){
        SinglyLinkedList singlyLinkedList = getSinglyLinkedList();
        System.out.println(singlyLinkedList.get(2));
        System.out.println(singlyLinkedList.get(5));
    }

    @Test
    //测试insert
    public void test02(){
        SinglyLinkedList singlyLinkedList = getSinglyLinkedList();
        singlyLinkedList.loop1(value -> {
            System.out.print(value + ",");
        });
        System.out.println();
        System.out.println("=============");
        singlyLinkedList.insert(0,18);
        singlyLinkedList.loop1(value -> {
            System.out.print(value + ",");
        });
    }

    @Test
    //测试remove
    public void test03(){
        SinglyLinkedList singlyLinkedList = getSinglyLinkedList();
        singlyLinkedList.loop1(value -> {
            System.out.print(value + ",");
        });
        System.out.println();
        singlyLinkedList.removeFirst();
        for (Integer ele:singlyLinkedList) {
            System.out.print(ele + ",");
        }
        System.out.println();

    }
    @Test
    //测似remove
    public void test04(){
        SinglyLinkedList singlyLinkedList = getSinglyLinkedList();
        singlyLinkedList.loop1(value -> {
            System.out.print(value + ",");
        });
        System.out.println();
        singlyLinkedList.remove(2);
        for (Integer ele:singlyLinkedList) {
            System.out.print(ele + ",");
        }
        System.out.println();
    }
}

test01:第一个获取到值，第二个超出索引，抛出预设的异常
在这里插入图片描述
test02:符合预期
在这里插入图片描述
test03:符合预期
在这里插入图片描述
test04:符合预期
在这里插入图片描述

单向链表代码实现（有哨兵）


/***
 *@description:单向链表（带哨兵）
 *@author: Hhzzy99
 *@date:2023/3/4
 **/
public class SinglyLinkedListSentinel implements Iterable<Integer>{//整体
    private Node head = new Node(999,null);//头指针->哨兵
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = head.next;
            @Override
            public boolean hasNext() {//是否有下一个元素
                return p != null;
            }

            @Override
            public Integer next() {//返回当前值，并指向下一个元素
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    /**
     * 节点类
     */
    private static class Node{
        int value;//值
        Node next;//下一个结点指针
        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    /**
     * 链表头添加元素
     * @param value 元素值
     */
    public void addFirst(int value){
        insert(0,value);
    }

    //链表遍历
    public void loop1(Consumer<Integer> consumer){
        Node p = head.next;
        while(p != null){
            consumer.accept(p.value);
            p = p.next;
        }
    }

    /**
     * for循环＋函数式接口Consumer
     * @param consumer 函数式接口
     */
    public void loop2(Consumer<Integer> consumer){
        for (Node p = head.next; p != null; p = p.next){
            consumer.accept(p.value);
        }
    }

    /**
     * 最后一个元素
     * @return Node p
     */
    private Node findLast(){
        Node p;
        for(p = head; p.next != null; p = p.next){
        }
        return p;
    }

    /**
     * 最后面添加元素
     * @param value 元素值
     */
    public void addLast(int value){
        Node last = findLast();
        last.next = new Node(value,null);
    }

    /**
     * 寻找索引为index的元素
     * @param index 寻找的元素的索引
     * @return Node p
     */
    private Node findNode(int index){
        int i = -1;//从哨兵位置开始(-1)
        for(Node p = head; p.next != null; p = p.next,i++){
            if(i == index)
                return p;
        }
        return null;
    }
    /**
     * 获取索引位置的元素
     * @param index 索引值
     * @throws IllegalArgumentException - 找不到索引，抛出index非法异常
     */
    public int get(int index){
        Node p = findNode(index);
        if(p == null)
            //抛异常
            throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));
        return p.value;
    }

    /**
     * 向索引位置插入元素
     * @param index 索引值
     * @param value 待插入值
     * @throws IllegalArgumentException - 找不到索引，抛出index非法异常
     */
    public void insert(int index, int value){
        if(index == 0){
            addFirst(value);
            return;
        }
        Node prev = findNode(index - 1);//找到上一个节点
        if (prev == null)//找不到
            throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));
        prev.next = new Node(value,prev.next);
    }

    /**
     * 删除第一个元素
     * @throws IllegalArgumentException - 找不到索引，抛出index非法异常
     */
    public void removeFirst(){
        remove(0);
    }

    /**
     * 删除索引为index的元素
     * @param index 要删除元素的索引值
     * @throws IllegalArgumentException - 找不到索引，抛出index非法异常
     */
    public void remove(int index){
        Node prev = findNode(index - 1);//上一个节点
        if (prev == null)
            throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));
        if (prev.next == null)
            throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));
        prev.next = prev.next.next;//prev.next是被删除的元素

    }
}

测试T2

private SinglyLinkedListSentinel getSinglyLinkedListSentinel() {
        SinglyLinkedListSentinel list = new SinglyLinkedListSentinel();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addLast(4);
        return list;
    }

    @Test
    public void test05(){
        SinglyLinkedListSentinel list = getSinglyLinkedListSentinel();
        list.loop2(ele->{
                System.out.print(ele+",");
            });
        System.out.println();
        System.out.println(list.get(2));
        System.out.println(list.get(10));//抛异常
    }

    @Test
    public void test06(){
        SinglyLinkedListSentinel list = getSinglyLinkedListSentinel();
        list.loop2(ele->{
            System.out.print(ele+",");
        });
        System.out.println();
        list.insert(2,7);
        list.loop2(ele->{
            System.out.print(ele+",");
        });
        System.out.println();
        list.remove(1);
        list.loop2(ele->{
            System.out.print(ele+",");
        });
//        list.insert(7,19);//抛异常
    }

test05:符合预期，抛出预设异常
在这里插入图片描述
test06:符合预期
在这里插入图片描述

结语

本文展示了Java实现单向链表的代码，希望对大家有所帮助！大家如果感兴趣可以点点赞，关注一下，你们的支持是我最强大的动力，非常感谢您的阅读(❁´◡`❁)

评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包

打赏作者

Hhzzy99

你的鼓励将是我创作的最大动力

¥1 ¥2 ¥4 ¥6 ¥10 ¥20
扫码支付：¥1
获取中
扫码支付

您的余额不足，请更换扫码支付或充值

打赏作者

实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值