Java-单向链表实现

2024-09-06 23:12
文章标签 java 实现 链表 单向

本文主要是介绍Java-单向链表实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

什么是链表？

        链表是一种常见的数据结构，用于存储一系列元素。与数组不同，链表中的元素（节点）在内存中不必是连续的。每个节点包含数据部分和指向下一个节点的引用（指针）。链表的主要优点是插入和删除操作的时间复杂度为O(1)，但访问特定元素的时间复杂度为O(n)。

头节点

        在单链表的数据结构中，头节点并不是一个独立的节点，而是一个指针或引用，指向链表中第一个数据节点。它的作用是标记链表的起始位置，以便能够遍历和操作链表中的所有节点。在大多数的单链表实现中，“头节点”本身并没有特别之处，它仅仅是一个指向第一个有效节点的引用。

什么是哨兵节点？

        哨兵节点（也称为哑节点或伪节点）是一个特殊的节点，通常不包含实际数据，仅用于简化链表的操作。在单向链表中，哨兵节点通常作为头节点使用，使得链表的插入、删除等操作更加统一和简单。

代码实现： 

没有将头节点设置为哨兵节点，以下是单向链表的Java实现代码，并解释了关键部分：

package school.singlelinkedlist;import java.util.Iterator;
import java.util.function.Consumer;/*** 文件名: null.java* 作者: 20526* 创建时间: 2024/9/6 15:17* 描述:单向链表实现*/
public class SingleLinkedList implements Iterable<Integer>{private Node head = null; // 头节点//节点类public static class Node {int data;Node next;public Node(int data, Node next) {this.data = data;this.next = next;}}//链表遍历public void traverse(Consumer <Integer> consumer) {Node current = head;//定义一个指针，进行遍历，默认指向头节点while (current!= null) {consumer.accept(current.data);//调用consumer.accept(data)方法，对当前节点的数据进行处理current = current.next;//指针向后移动}}public void traverse2(Consumer <Integer> consumer){for (Node current = head; current!= null; current = current.next){consumer.accept(current.data);}}//实现迭代器，可以用增强for循环遍历@Overridepublic Iterator<Integer> iterator() {//匿名内部类return new Iterator<Integer>() {Node current  = head;@Overridepublic boolean hasNext() { //判断是否有下一个节点return current!= null;}@Overridepublic Integer next() { //返回当前值，并指向下一个节点int value = current.data;current = current.next;return value;}};}//添加节点到链表头public void addfirst(int data) {
//      head = new Node(data, null);head = new Node(data, head);}//查找链表尾节点private Node findlast(){Node p ;if (head == null)return null;for (p = head; p.next!= null; p = p.next){}return p;}//添加节点到链表尾public void addlast(int data){Node last = findlast();if (last == null) {addfirst(data);return;}else{last.next = new Node(data, null);}}//根据索引插入节点public void add(int index, int data) throws IllegalArgumentException {if (index == 0 ) {addfirst(data);return;}Node prev = findNode(index-1);if (prev == null) {throw  illegalIndex(index);}prev.next = new Node(data, prev.next);}//查找节点private Node findNode(int index) {int i = 0;for (Node p = head; p!= null; p = p.next,i++){if (i == index)return p;}return null;//如果没有找到，返回null}public int get(int index) {Node p = findNode(index);if (p == null){illegalIndex(index);}return p.data;}//索引不合法，抛出异常private  IllegalArgumentException illegalIndex(int index) {throw new IllegalArgumentException(String.format("Index: [%d]不合法%n", index));}//删除首节点public void removefirst(int index) {if (head == null)throw new IllegalArgumentException("空链表");head = head.next;}//根据索引删除节点public void remove(int index) {if (index == 0) {removefirst(index);return;}Node prev = findNode(index-1);//上一个节点if (prev == null) {throw  illegalIndex(index);}Node remove = prev.next;//被删除的节点if (remove == null) {throw  illegalIndex(index);}prev.next = remove.next;}// 根据索引修改节点的值public void set(int index, int data) throws IllegalArgumentException {Node node = findNode(index); // 查找指定索引的节点if (node == null) {throw illegalIndex(index); // 如果节点不存在，抛出索引不合法的异常}node.data = data; // 修改节点的值}}

测试代码：

package school.singlelinkedlist;import org.junit.Test;public class SingleLinkedListTest {@Testpublic void test1() {SingleLinkedList list = new SingleLinkedList();list.addfirst(1);list.addfirst(2);list.addfirst(3);list.addfirst(4);list.addfirst(5);list.traverse(data -> {System.out.println(data + " ");});list.traverse2(data -> {System.out.println(data + " ");});}@Testpublic void test2() {SingleLinkedList list = new SingleLinkedList();list.addfirst(1);list.addfirst(2);list.addfirst(3);list.addfirst(4);list.addfirst(5);for (Integer i : list) {System.out.println(i);}}@Testpublic void test3() {SingleLinkedList list = new SingleLinkedList();list.addfirst(1);list.addlast(2);list.addlast(3);list.addlast(4);for (Integer i : list) {System.out.println(i);}}@Testpublic void test4() {SingleLinkedList list = new SingleLinkedList();list.addfirst(1);list.addlast(2);list.addlast(3);list.addlast(4);System.out.println(list.get(0));System.out.println(list.get(1));}@Testpublic void test5() {SingleLinkedList list = new SingleLinkedList();list.addfirst(1);list.addlast(2);list.addlast(3);list.addlast(4);list.add(2, 5);
//        list.add(6, 6);for (Integer i : list) {System.out.println(i);}}@Testpublic void test6() {SingleLinkedList list = new SingleLinkedList();list.addfirst(1);list.addlast(2);list.addlast(3);list.addlast(4);list.addlast(5);for (Integer i : list) {System.out.println(i);}System.out.println("------------删除后-------------");
//        list.removefirst(0);list.remove(2);for (Integer i : list) {System.out.println(i);}}@Testpublic void test7() {SingleLinkedList list = new SingleLinkedList();list.addfirst(1);list.addlast(2);list.addlast(3);list.addlast(4);list.addlast(5);list.set(1,1);for (Integer i : list) {System.out.println(i);}}}

关键点解释

head = new Node(data, head);

这行代码的作用是在链表的头部添加一个新节点。具体解释如下：

  1. new Node(data, head):

    • new Node(data, head)是通过调用Node类的构造函数来创建一个新的节点对象。在构造函数中，data代表新节点的数据值，而head代表当前头节点，即链表的第一个节点。
    • 通过传入head作为构造函数的第二个参数，新节点的next指针将指向当前的头节点。因此，新节点成为链表中的第一个节点，而原来的头节点成为新节点的下一个节点。

  2. head = new Node(data, head);:

    • 这行代码将head引用更新为新的节点对象。通过这种方式，链表的头节点即被更新为新创建的节点。

        简而言之，这个操作在链表的头部插入了一个新的节点，使新的节点成为链表的第一个节点。旧的头节点则被移到第二个位置。

头节点设置为哨兵节点

package school.singlelinkedlist;import java.util.Iterator;
import java.util.function.Consumer;/*** 文件名: null.java* 作者: 20526* 创建时间: 2024/9/6 15:17* 描述:单向链表实现*/
public class SingleLinkedList implements Iterable<Integer>{//    private Node head = null; // 头节点private Node head = new Node(0, null);//节点类public static class Node {int data;Node next;public Node(int data, Node next) {this.data = data;this.next = next;}}//链表遍历public void traverse(Consumer <Integer> consumer) {Node current = head.next;//定义一个指针，进行遍历，默认指向头节点while (current!= null) {consumer.accept(current.data);//调用consumer.accept(data)方法，对当前节点的数据进行处理current = current.next;//指针向后移动}}public void traverse2(Consumer <Integer> consumer){for (Node current = head.next; current!= null; current = current.next){consumer.accept(current.data);}}//实现迭代器，可以用增强for循环遍历@Overridepublic Iterator<Integer> iterator() {//匿名内部类return new Iterator<Integer>() {Node current  = head.next;@Overridepublic boolean hasNext() { //判断是否有下一个节点return current!= null;}@Overridepublic Integer next() { //返回当前值，并指向下一个节点int value = current.data;current = current.next;return value;}};}//添加节点到链表头public void addfirst(int data) {add(0, data);}//查找链表尾节点private Node findlast(){Node p ;for (p = head; p.next!= null; p = p.next){}return p;}//添加节点到链表尾public void addlast(int data){Node last = findlast();last.next = new Node(data, null);}//根据索引插入节点public void add(int index, int data) throws IllegalArgumentException {Node prev = findNode(index-1);if (prev == null) {throw  illegalIndex(index);}prev.next = new Node(data, prev.next);}//查找节点private Node findNode(int index) {int i = -1;for (Node p = head; p!= null; p = p.next,i++){if (i == index)return p;}return null;//如果没有找到，返回null}public int get(int index) {Node p = findNode(index);if (p == null){illegalIndex(index);}return p.data;}//索引不合法，抛出异常private  IllegalArgumentException illegalIndex(int index) {throw new IllegalArgumentException(String.format("Index: [%d]不合法%n", index));}//删除首节点public void removefirst(int index) {remove(0);}//根据索引删除节点public void remove(int index) {Node prev = findNode(index-1);//上一个节点if (prev == null) {throw  illegalIndex(index);}Node remove = prev.next;//被删除的节点if (remove == null) {throw  illegalIndex(index);}prev.next = remove.next;}// 根据索引修改节点的值public void set(int index, int data) throws IllegalArgumentException {Node node = findNode(index); // 查找指定索引的节点if (node == null) {throw illegalIndex(index); // 如果节点不存在，抛出索引不合法的异常}node.data = data; // 修改节点的值}}

        下面是将头节点设置为哨兵节点后的改动优化，与上面的略有不同，不过大致思路都一样，去掉了一些特殊情况的处理

  1. 哨兵节点：代码中private Node head = new Node(0, null);定义了一个哨兵节点。这个节点不存储实际数据，仅用于简化链表操作。

  2. 遍历方法：traverse和traverse2方法展示了两种遍历链表的方式，均使用Consumer接口来处理每个节点的数据。

  3. 迭代器实现：iterator方法实现了Iterable接口，使得链表可以通过增强for循环进行遍历。

  4. 插入和删除操作：add和remove方法展示了如何在链表中插入和删除节点。由于使用了哨兵节点，这些操作变得更加简单和统一。

  5. 异常处理：illegalIndex方法用于处理索引不合法的情况，抛出IllegalArgumentException异常。

        通过使用哨兵节点，链表的操作变得更加简洁和高效，避免了在处理头节点时需要特殊处理的麻烦。 希望对你有所帮助……

这篇关于Java-单向链表实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1143391。

相关文章

springboot集成easypoi导出word换行处理过程

springboot集成easypoi导出word换行处理过程

《springboot集成easypoi导出word换行处理过程》SpringBoot集成Easypoi导出Word时,换行符n失效显示为空格,解决方法包括生成段落或替换模板中n为回车,同时需确... 目录项目场景问题描述解决方案第一种：生成段落的方式第二种：替换模板的情况，换行符替换成回车总结项目场景s
阅读更多...
SpringBoot集成redisson实现延时队列教程

SpringBoot集成redisson实现延时队列教程

《SpringBoot集成redisson实现延时队列教程》文章介绍了使用Redisson实现延迟队列的完整步骤,包括依赖导入、Redis配置、工具类封装、业务枚举定义、执行器实现、Bean创建、消费... 目录1、先给项目导入Redisson依赖2、配置redis3、创建 RedissonConfig 配
阅读更多...
SpringBoot中@Value注入静态变量方式

SpringBoot中@Value注入静态变量方式

《SpringBoot中@Value注入静态变量方式》SpringBoot中静态变量无法直接用@Value注入,需通过setter方法,@Value(${})从属性文件获取值,@Value(#{})用... 目录项目场景解决方案注解说明1、@Value("${}")使用示例2、@Value("#{}"php
阅读更多...
SpringBoot分段处理List集合多线程批量插入数据方式

SpringBoot分段处理List集合多线程批量插入数据方式

《SpringBoot分段处理List集合多线程批量插入数据方式》文章介绍如何处理大数据量List批量插入数据库的优化方案：通过拆分List并分配独立线程处理,结合Spring线程池与异步方法提升效率... 目录项目场景解决方案1.实体类2.Mapper3.spring容器注入线程池bejsan对象4.创建
阅读更多...
线上Java OOM问题定位与解决方案超详细解析

线上Java OOM问题定位与解决方案超详细解析

《线上JavaOOM问题定位与解决方案超详细解析》OOM是JVM抛出的错误,表示内存分配失败,：本文主要介绍线上JavaOOM问题定位与解决方案的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录一、OOM问题核心认知1.1 OOM定义与技术定位1.2 OOM常见类型及技术特征二、OOM问题定位工具
阅读更多...
Python的Darts库实现时间序列预测

Python的Darts库实现时间序列预测

《Python的Darts库实现时间序列预测》Darts一个集统计、机器学习与深度学习模型于一体的Python时间序列预测库,本文主要介绍了Python的Darts库实现时间序列预测,感兴趣的可以了解... 目录目录一、什么是 Darts？二、安装与基本配置安装 Darts导入基础模块三、时间序列数据结构与
阅读更多...
基于 Cursor 开发 Spring Boot 项目详细攻略

基于 Cursor 开发 Spring Boot 项目详细攻略

《基于Cursor开发SpringBoot项目详细攻略》Cursor是集成GPT4、Claude3.5等LLM的VSCode类AI编程工具,支持SpringBoot项目开发全流程,涵盖环境配... 目录cursor是什么？基于 Cursor 开发 Spring Boot 项目完整指南1. 环境准备2. 创建
阅读更多...
Python使用FastAPI实现大文件分片上传与断点续传功能

Python使用FastAPI实现大文件分片上传与断点续传功能

《Python使用FastAPI实现大文件分片上传与断点续传功能》大文件直传常遇到超时、网络抖动失败、失败后只能重传的问题,分片上传+断点续传可以把大文件拆成若干小块逐个上传,并在中断后从已完成分片继... 目录一、接口设计二、服务端实现（FastAPI）2.1 运行环境2.2 目录结构建议2.3 serv
阅读更多...
C#实现千万数据秒级导入的代码

C#实现千万数据秒级导入的代码

《C#实现千万数据秒级导入的代码》在实际开发中excel导入很常见,现代社会中很容易遇到大数据处理业务,所以本文我就给大家分享一下千万数据秒级导入怎么实现,文中有详细的代码示例供大家参考,需要的朋友可... 目录前言一、数据存储二、处理逻辑优化前代码处理逻辑优化后的代码总结前言在实际开发中excel导入很
阅读更多...
Spring Security简介、使用与最佳实践

Spring Security简介、使用与最佳实践

《SpringSecurity简介、使用与最佳实践》SpringSecurity是一个能够为基于Spring的企业应用系统提供声明式的安全访问控制解决方案的安全框架,本文给大家介绍SpringSec... 目录一、如何理解 Spring Security？—— 核心思想二、如何在 Java 项目中使用？——
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2