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中六种批量更新Mysql的方式效率对比分析

SpringBoot中六种批量更新Mysql的方式效率对比分析

《SpringBoot中六种批量更新Mysql的方式效率对比分析》文章比较了MySQL大数据量批量更新的多种方法,指出REPLACEINTO和ONDUPLICATEKEY效率最高但存在数据风险,MyB... 目录效率比较测试结构数据库初始化测试数据批量修改方案第一种 for第二种 case when第三种
阅读更多...
python生成随机唯一id的几种实现方法

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1：使用 UUID 模块（推荐）方法 2：使用 Secrets 模块（安全敏感场景）方法
阅读更多...
Java docx4j高效处理Word文档的实战指南

Java docx4j高效处理Word文档的实战指南

《Javadocx4j高效处理Word文档的实战指南》对于需要在Java应用程序中生成、修改或处理Word文档的开发者来说,docx4j是一个强大而专业的选择,下面我们就来看看docx4j的具体使用... 目录引言一、环境准备与基础配置1.1 Maven依赖配置1.2 初始化测试类二、增强版文档操作示例2.
阅读更多...
一文详解如何使用Java获取PDF页面信息

一文详解如何使用Java获取PDF页面信息

《一文详解如何使用Java获取PDF页面信息》了解PDF页面属性是我们在处理文档、内容提取、打印设置或页面重组等任务时不可或缺的一环,下面我们就来看看如何使用Java语言获取这些信息吧... 目录引言一、安装和引入PDF处理库引入依赖二、获取 PDF 页数三、获取页面尺寸（宽高）四、获取页面旋转角度五、判断
阅读更多...
Spring Boot中的路径变量示例详解

Spring Boot中的路径变量示例详解

《SpringBoot中的路径变量示例详解》SpringBoot中PathVariable通过@PathVariable注解实现URL参数与方法参数绑定,支持多参数接收、类型转换、可选参数、默认值及... 目录一. 基本用法与参数映射1.路径定义2.参数绑定&nhttp://www.chinasem.cnbs
阅读更多...
JAVA中安装多个JDK的方法

JAVA中安装多个JDK的方法

《JAVA中安装多个JDK的方法》文章介绍了在Windows系统上安装多个JDK版本的方法,包括下载、安装路径修改、环境变量配置（JAVA_HOME和Path）,并说明如何通过调整JAVA_HOME在... 首先去oracle官网下载好两个版本不同的jdk（需要登录Oracle账号，没有可以免费注册）下载完
阅读更多...
Spring StateMachine实现状态机使用示例详解

Spring StateMachine实现状态机使用示例详解

《SpringStateMachine实现状态机使用示例详解》本文介绍SpringStateMachine实现状态机的步骤,包括依赖导入、枚举定义、状态转移规则配置、上下文管理及服务调用示例,重点解... 目录什么是状态机使用示例什么是状态机状态机是计算机科学中的​​核心建模工具​​，用于描述对象在其生命
阅读更多...
Spring Boot 结合 WxJava 实现文章上传微信公众号草稿箱与群发

Spring Boot 结合 WxJava 实现文章上传微信公众号草稿箱与群发

《SpringBoot结合WxJava实现文章上传微信公众号草稿箱与群发》本文将详细介绍如何使用SpringBoot框架结合WxJava开发工具包,实现文章上传到微信公众号草稿箱以及群发功能,... 目录一、项目环境准备1.1 开发环境1.2 微信公众号准备二、Spring Boot 项目搭建2.1 创建
阅读更多...
Java中Integer128陷阱

Java中Integer128陷阱

《Java中Integer128陷阱》本文主要介绍了Java中Integer与int的区别及装箱拆箱机制,重点指出-128至127范围内的Integer值会复用缓存对象,导致==比较结果为true,下... 目录一、Integer和int的联系1.1 Integer和int的区别1.2 Integer和in
阅读更多...
SpringSecurity整合redission序列化问题小结(最新整理)

SpringSecurity整合redission序列化问题小结(最新整理)

《SpringSecurity整合redission序列化问题小结(最新整理)》文章详解SpringSecurity整合Redisson时的序列化问题,指出需排除官方Jackson依赖,通过自定义反序... 目录1. 前言2. Redission配置2.1 RedissonProperties2.2 Red
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2