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。

相关文章

使用Python实现IP地址和端口状态检测与监控

使用Python实现IP地址和端口状态检测与监控

《使用Python实现IP地址和端口状态检测与监控》在网络运维和服务器管理中,IP地址和端口的可用性监控是保障业务连续性的基础需求,本文将带你用Python从零打造一个高可用IP监控系统,感兴趣的小伙... 目录概述：为什么需要IP监控系统使用步骤说明1. 环境准备2. 系统部署3. 核心功能配置系统效果展
阅读更多...
Java 实用工具类Spring 的 AnnotationUtils详解

Java 实用工具类Spring 的 AnnotationUtils详解

《Java实用工具类Spring的AnnotationUtils详解》Spring框架提供了一个强大的注解工具类org.springframework.core.annotation.Annot... 目录前言一、AnnotationUtils 的常用方法二、常见应用场景三、与 JDK 原生注解 API 的
阅读更多...
Java controller接口出入参时间序列化转换操作方法(两种)

Java controller接口出入参时间序列化转换操作方法(两种)

《Javacontroller接口出入参时间序列化转换操作方法(两种)》：本文主要介绍Javacontroller接口出入参时间序列化转换操作方法,本文给大家列举两种简单方法,感兴趣的朋友一起看... 目录方式一、使用注解方式二、统一配置场景：在controller编写的接口，在前后端交互过程中一般都会涉及
阅读更多...
Java中的StringBuilder之如何高效构建字符串

Java中的StringBuilder之如何高效构建字符串

《Java中的StringBuilder之如何高效构建字符串》本文将深入浅出地介绍StringBuilder的使用方法、性能优势以及相关字符串处理技术,结合代码示例帮助读者更好地理解和应用,希望对大家... 目录关键点什么是 StringBuilder？为什么需要 StringBuilder？如何使用 St
阅读更多...
Python实现微信自动锁定工具

Python实现微信自动锁定工具

《Python实现微信自动锁定工具》在数字化办公时代,微信已成为职场沟通的重要工具,但临时离开时忘记锁屏可能导致敏感信息泄露,下面我们就来看看如何使用Python打造一个微信自动锁定工具吧... 目录引言：当微信隐私遇到自动化守护效果展示核心功能全景图技术亮点深度解析1. 无操作检测引擎2. 微信路径智能获
阅读更多...
使用Java将各种数据写入Excel表格的操作示例

使用Java将各种数据写入Excel表格的操作示例

《使用Java将各种数据写入Excel表格的操作示例》在数据处理与管理领域,Excel凭借其强大的功能和广泛的应用,成为了数据存储与展示的重要工具,在Java开发过程中,常常需要将不同类型的数据,本文... 目录前言安装免费Java库1. 写入文本、或数值到 Excel单元格2. 写入数组到 Excel表格
阅读更多...
Java并发编程之如何优雅关闭钩子Shutdown Hook

Java并发编程之如何优雅关闭钩子Shutdown Hook

《Java并发编程之如何优雅关闭钩子ShutdownHook》这篇文章主要为大家详细介绍了Java如何实现优雅关闭钩子ShutdownHook,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起... 目录关闭钩子简介关闭钩子应用场景数据库连接实战演示使用关闭钩子的注意事项开源框架中的关闭钩子机制1.
阅读更多...
Python中pywin32 常用窗口操作的实现

Python中pywin32 常用窗口操作的实现

《Python中pywin32常用窗口操作的实现》本文主要介绍了Python中pywin32常用窗口操作的实现,pywin32主要的作用是供Python开发者快速调用WindowsAPI的一个... 目录获取窗口句柄获取最前端窗口句柄获取指定坐标处的窗口根据窗口的完整标题匹配获取句柄根据窗口的类别匹配获取句
阅读更多...
Maven中引入 springboot 相关依赖的方式(最新推荐)

Maven中引入 springboot 相关依赖的方式(最新推荐)

《Maven中引入springboot相关依赖的方式(最新推荐)》：本文主要介绍Maven中引入springboot相关依赖的方式(最新推荐),本文给大家介绍的非常详细,对大家的学习或工作具有... 目录Maven中引入 springboot 相关依赖的方式1. 不使用版本管理（不推荐）2、使用版本管理（推
阅读更多...
Java 中的 @SneakyThrows 注解使用方法(简化异常处理的利与弊)

Java 中的 @SneakyThrows 注解使用方法(简化异常处理的利与弊)

《Java中的@SneakyThrows注解使用方法(简化异常处理的利与弊)》为了简化异常处理,Lombok提供了一个强大的注解@SneakyThrows,本文将详细介绍@SneakyThro... 目录1. @SneakyThrows 简介 1.1 什么是 Lombok？2. @SneakyThrows
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2