当前位置： 首页 > news >正文

Java实现单向链表

news 2025/8/4 2:53:12

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

单向链表

文章目录

  • 单向链表
    • 单向链表的特点
    • 单向链表代码实现（无哨兵）
    • 测试T1
    • 单向链表代码实现（有哨兵）
    • 测试T2
  • 结语

单向链表的特点

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

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

/****@description:单向链表*@author: Hhzzy99*@date:2023/3/4**/
public class SinglyLinkedList implements Iterable<Integer>{//整体private Node head = null;//头指针@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {Node p = head;@Overridepublic boolean hasNext() {//是否有下一个元素return p != null;}@Overridepublic 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    addLastSinglyLinkedList 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//测试insertpublic 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//测试removepublic 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//测似removepublic 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);//头指针->哨兵@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {Node p = head.next;@Overridepublic boolean hasNext() {//是否有下一个元素return p != null;}@Overridepublic 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;}@Testpublic 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));//抛异常}@Testpublic 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实现单向链表的代码，希望对大家有所帮助！大家如果感兴趣可以点点赞，关注一下，你们的支持是我最强大的动力，非常感谢您的阅读(❁´◡`❁)

http://www.lryc.cn/news/28875.html

相关文章：

  • 3月4日,30秒知全网,精选7个热点
  • EXCEL-职业版本（2）
  • java中延时队列的实现
  • 基于java的circle buffer的实现
  • 通用方法——为什么重写equals还要重写hashcode
  • JavaSE学习进阶day2_01 包和权限修饰符
  • Android性能调优 - 省电优化
  • ElasticSearch - SpringBoot整合ES之全文搜索匹配查询 match
  • 句子的改写和扩写
  • DockerFile创建及案例
  • 第十四届蓝桥杯三月真题刷题训练——第 1 天
  • 基于容器云提交spark job任务
  • Linux系统调用之目录操作函数
  • 设计模式-策略模式
  • 面试+算法：罗马数字及Excel列名与数字互相转换
  • Connext DDS路由服务Routing Service（1）
  • 如何使用SaleSmartly进行Facebook Messenger 营销、销售和支持
  • 教资教育知识与能力中学教学
  • IDEA中使用Tomcat的两种方式：集成本地Tomcat使用Tomcat Maven插件
  • IP 地址的简介
  • 3D动作/动画特效
  • python 多线程编程之_thread模块
  • vue：vue2与vue3的区别
  • SQL数据库语法
  • 人机界面艺术设计
  • 【办公类-19-01-02】办公中的思考——Python,统计教职工的姓名中那些字最多？
  • HCIP实验1
  • 一个Bug让人类科技倒退几十年？
  • 2023王道考研数据结构笔记第四章串
  • 【AI绘图学习笔记】深度学习相关数学原理总结(持续更新)