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。

相关文章

Spring Boot中WebSocket常用使用方法详解

Spring Boot中WebSocket常用使用方法详解

《SpringBoot中WebSocket常用使用方法详解》本文从WebSocket的基础概念出发,详细介绍了SpringBoot集成WebSocket的步骤,并重点讲解了常用的使用方法,包括简单消... 目录一、WebSocket基础概念1.1 什么是WebSocket1.2 WebSocket与HTTP
阅读更多...
SpringBoot+Docker+Graylog 如何让错误自动报警

SpringBoot+Docker+Graylog 如何让错误自动报警

《SpringBoot+Docker+Graylog如何让错误自动报警》SpringBoot默认使用SLF4J与Logback,支持多日志级别和配置方式,可输出到控制台、文件及远程服务器,集成ELK... 目录01 Spring Boot 默认日志框架解析02 Spring Boot 日志级别详解03 Sp
阅读更多...
Python使用python-can实现合并BLF文件

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库：CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合
阅读更多...
java中反射Reflection的4个作用详解

java中反射Reflection的4个作用详解

《java中反射Reflection的4个作用详解》反射Reflection是Java等编程语言中的一个重要特性,它允许程序在运行时进行自我检查和对内部成员（如字段、方法、类等）的操作,本文将详细介绍... 目录作用1、在运行时判断任意一个对象所属的类作用2、在运行时构造任意一个类的对象作用3、在运行时判断
阅读更多...
Python使用OpenCV实现获取视频时长的小工具

Python使用OpenCV实现获取视频时长的小工具

《Python使用OpenCV实现获取视频时长的小工具》在处理视频数据时,获取视频的时长是一项常见且基础的需求,本文将详细介绍如何使用Python和OpenCV获取视频时长,并对每一行代码进行深入解析... 目录一、代码实现二、代码解析1. 导入 OpenCV 库2. 定义获取视频时长的函数3. 打开视频文
阅读更多...
golang版本升级如何实现

golang版本升级如何实现

《golang版本升级如何实现》：本文主要介绍golang版本升级如何实现问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录golanwww.chinasem.cng版本升级linux上golang版本升级删除golang旧版本安装golang最新版本总结gola
阅读更多...
java如何解压zip压缩包

java如何解压zip压缩包

《java如何解压zip压缩包》：本文主要介绍java如何解压zip压缩包问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java解压zip压缩包实例代码结果如下总结java解压zip压缩包坐在旁边的小伙伴问我怎么用 java 将服务器上的压缩文件解压出来，
阅读更多...
SpringBoot中SM2公钥加密、私钥解密的实现示例详解

SpringBoot中SM2公钥加密、私钥解密的实现示例详解

《SpringBoot中SM2公钥加密、私钥解密的实现示例详解》本文介绍了如何在SpringBoot项目中实现SM2公钥加密和私钥解密的功能,通过使用Hutool库和BouncyCastle依赖,简化... 目录一、前言1、加密信息(示例)2、加密结果(示例)二、实现代码1、yml文件配置2、创建SM2工具
阅读更多...
Spring WebFlux 与 WebClient 使用指南及最佳实践

Spring WebFlux 与 WebClient 使用指南及最佳实践

《SpringWebFlux与WebClient使用指南及最佳实践》WebClient是SpringWebFlux模块提供的非阻塞、响应式HTTP客户端,基于ProjectReactor实现,... 目录Spring WebFlux 与 WebClient 使用指南1. WebClient 概述2. 核心依
阅读更多...
Mysql实现范围分区表(新增、删除、重组、查看)

Mysql实现范围分区表(新增、删除、重组、查看)

《Mysql实现范围分区表(新增、删除、重组、查看)》MySQL分区表的四种类型（范围、哈希、列表、键值）,主要介绍了范围分区的创建、查询、添加、删除及重组织操作,具有一定的参考价值,感兴趣的可以了解... 目录一、mysql分区表分类二、范围分区（Range Partitioning1、新建分区表：2、分
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2