首页 > 编程语言 >Java-单向链表实现

Java-单向链表实现

时间：2024-09-06 19:53:15浏览次数：12  
标签：Node index Java list 单向 next 链表 data 节点

什么是链表？

        链表是一种常见的数据结构，用于存储一系列元素。与数组不同，链表中的元素（节点）在内存中不必是连续的。每个节点包含数据部分和指向下一个节点的引用（指针）。链表的主要优点是插入和删除操作的时间复杂度为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循环遍历
    @Override
    public Iterator<Integer> iterator() {
        //匿名内部类
        return new Iterator<Integer>() {
            Node current  = head;
            @Override
            public boolean hasNext() { //判断是否有下一个节点
                return current!= null;
            }

            @Override
            public 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 {


    @Test
    public 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 + " ");
        });
    }

    @Test
    public 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);
        }
    }

    @Test
    public 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);
        }

    }

    @Test
    public 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));
    }

    @Test
    public 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);
        }
    }

    @Test
    public 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);
        }
    }


    @Test
    public 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循环遍历
    @Override
    public Iterator<Integer> iterator() {
        //匿名内部类
        return new Iterator<Integer>() {
            Node current  = head.next;
            @Override
            public boolean hasNext() { //判断是否有下一个节点
                return current!= null;
            }

            @Override
            public 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异常。

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

标签：Node,index,Java,list,单向,next,链表,data,节点
From： https://blog.csdn.net/Broken_x/article/details/141963194

相关文章

  • java集合基础练习题
    List集合.ArrayList,LinkedList,Vector三者的相同点与不同点？(“Vector”可百度)【面试题】共同点：他们都实现了List接口，意味着他们具有相同的基本操作，如添加、删除、获取元素有序性和可重复性，他们都是有序的，即插入顺序和迭代顺序相同，都允许存储重复的元素都可以动态调整大......
  • Spire.Office for Java 9.8.0 FIX
    独立Java库用于处理Office、PDF和条形码Spire.OfficeforJava是E-iceblue提供的企业级OfficeJavaAPI的组合，包括Spire.DocforJava、Spire.XLSforJava、Spire.PresentationforJava、Spire.PDFforJava和Spire.BarcodeforJava。开发人员可以使用Spire.Off......
  • JavaScript学习文档（14）：深入对象、内置构造函数、综合案例
    目录一、深入对象1、创建对象三种方式2、构造函数（1）构造函数（2）说明：（3）利用构造函数创建多个对象（4）实例化执行过程3、实例成员和静态成员（1）实例成员：（2）静态成员：二、内置构造函数1、Object2、Array（1）数组常见实例方法-核心方法（2）员工涨薪计算成本案例（3）还有些数组常见方法（4......
  • 基于Java的旅游景区网站系统设计与实现
    演示地址前台地址：http://travel.gitapp.cn后台地址：http://travel.gitapp.cn/admin后台管理帐号：用户名：admin123密码：admin123功能介绍平台采用B/S结构，后端采用主流的Springboot框架进行开发，前端采用主流的Vue.js进行开发。整个平台包括前台和后台两个部分。前台功......
  • javascript网页设计案例
    JavaScript在网页设计中扮演着重要的角色，能够实现动态效果和交互功能，提升用户体验。下面，我将通过一个具体的案例——“动态图片轮播”来展示JavaScript在网页设计中的应用。案例：动态图片轮播1.HTML结构<!DOCTYPEhtml><htmllang="zh"><head>  <metacharset="UTF-......
  • 内核链表
    一、特性内核链表：双向循环有头链表组成：将链表的结点作为结构体成员存在，只放指向前驱结点和后继结点的指针offsetof获取结构体中的成员到结构体开头中的偏移量container_of通过偏移量获取结构体首地址但应用层不能使用上述两个宏，处理方法：将节点作为结构体第一个成员（结构......
  • JMC揭秘：如何精准监控Java应用性能
    对于我们常用的HotSpot来说，有更强大的工具，那就是JMC。JMC集成了一个非常好用的功能：JFR（JavaFlightRecorder）。FlightRecorder源自飞机的黑盒子，是用来录制信息然后事后分析的。在Java11中，它可以通过jcmd命令进行录制，主要包括configure、check、start、dump、stop......
  • Java线程池详解
    线程池解释线程池采用了池化思想，能够有效的管理线程的生命周期，减少了每次获取资源的消耗，提高了资源的利用率。类似池化实现还有数据库连接池、HTTP连接池等好处减少了线程创建和销毁的开销提高了响应速度使得线程更加方便管理常见使用场景量大处理时间较短......
  • 一次Java性能调优实践【代码+JVM 性能提升70%】
    这是我第一次对系统进行调优，涉及代码和JVM层面的调优。如果你能看到最后的话，或许会对你日常的开发有帮助，可以避免像我一样，犯一些低级别的错误。本次调优的代码是埋点系统中的报表分析功能，小公司，开发结束后，没有CodeReview环节，所以下面某些问题，也许在CodeReview环节就可以避免......
  • postgresql java jdbc 负载均衡解决方案
    在PostgreSQL和JavaJDBC的环境中实现负载均衡，可以有效提升数据库性能和可用性。以下是一个基于PostgreSQL和JavaJDBC的负载均衡解决方案，包括主从复制、连接池、以及负载均衡器的集成。1.PostgreSQL主从复制PostgreSQL的主从复制是实现读写分离的重要前提。主节点（Ma......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99