Java链表详解--通俗易懂(超详细,含源码)-程序员宅基地

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

链表的分类

单向链表，双向链表
带头链表，不带头链表
循环的，非循环的

排列组合后一共有

$eq?C_%7B2%7D%5E%7B1%7D*C_%7B2%7D%5E%7B1%7D*C_%7B2%7D%5E%7B1%7D%3D8$

即一共8种链表，其中单向、不带头、非循环以及双向、不带头、非循环的链表最为重要，也是本文主要介绍的链表类型。

链表的结构

对于链表的结构，可以用如下这个图来模拟。

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Zmc5Zmc5Zmc5Zmc6bKB5YWI55Sf,size_9,color_FFFFFF,t_70,g_se,x_16

图中所示的为链表的一个节点，value是这个节点的所存储的数据值，next为下一节点的地址。

下面是一个5个节点的链表。

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Zmc5Zmc5Zmc5Zmc6bKB5YWI55Sf,size_20,color_FFFFFF,t_70,g_se,x_16

接下来，我们来实现这样的链表的增删查改：

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Zmc5Zmc5Zmc5Zmc6bKB5YWI55Sf,size_20,color_FFFFFF,t_70,g_se,x_16

第一个节点，地址假设是0x999，存储的数据是11，next存储的是下一个节点的地址(假设是0x888)

第二个节点，地址假设是0x888，存储的数据是22，next存储的是下一个节点的地址(假设是0x777)

第三个节点，地址假设是0x777，存储的数据是33，next存储的是下一个节点的地址(假设是0x666)

第四个节点，地址假设是0x666，存储的数据是44，next存储的是下一个节点的地址(假设是0x555)

第五个节点，地址假设是0x555，存储的数据是55，由于没有后续节点，next存储的是空指针null

定义一个head，存储头节点（第一个节点）的地址（假设为0x999）。

代码实现链表

1.创建节点类

节点由val域(数据域)，以及next域(指针域)组成，对于next域，其是引用类型，存放下一个节点的地址，故

用public ListNode next来创建next。

同时设置构造函数，方便对val进行初始化。

//ListNode代表一个节点
class ListNode{
    public int val;
    public ListNode next;

    //构造函数
    public ListNode(int a){
        this.val = a;
    }
}

2.创建链表

方法一：枚举法（略简单，略low）

public class MyLinkedList {

    public ListNode head;//链表的头

    public void creatList(){
        ListNode listNode1 = new ListNode(11);
        ListNode listNode2 = new ListNode(22);
        ListNode listNode3 = new ListNode(33);
        ListNode listNode4 = new ListNode(44);
        ListNode listNode5 = new ListNode(55);

        this.head = listNode1;

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

    }
}

直接进行val的赋值以及对next的初始化。

注意：不用对最后一个节点的next进行赋值，因为next是引用类型，不赋值则默认为null。

方法二：头插法public void addFirst(int data)

头插法是指在链表的头节点的位置插入一个新节点，定义一个node表示该节点，然后就是对node的next进行赋值，用node.next = this.head即可完成（注意：head应指向新节点）

代码实现

    public void addFirst(int data){
        ListNode node = new ListNode(data);
        node.next = this.head;
        this.head = node;
    }

方法三：尾插法public void addLast(int data)

尾插法是指在链表的尾节点的位置插入一个新节点，定义一个node表示该节点，然后就是对原来最后一个节点的next进行赋值，先将head移动至原来最后一个节点，用head.next = node进行赋值（注意，如果链表不为空，需要定义cur来代替head）

代码实现

    public void addLast(int data){
        ListNode node = new ListNode(data);
        if(this.head == null){
            this.head = node;
        }else {
            ListNode cur = this.head;
            while(cur.next != null){
                cur = cur.next;
            }
            cur.next = node;
        }
    }

3.打印链表：public void display()

认识了链表的结构，我们可以知道，节点与节点之间通过next产生联系。并且我们已将创建了head，即头节点的地址，通过head的移动来实现链表的打印。

注意：为了使head一直存在且有意义，我们在display()函数中定义一个cur：ListNode cur = this.head;来替代head。

对于head的移动，可用head = head.next来实现。

代码实现：

    public void display(){
        ListNode cur = this.head;
        while(cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

4.查找是否包含关键字key是否在单链表当中：public boolean contains(int key)

查找key，可以利用head移动，实现对于key的查找（注意：同样要定义一个cur来代替head）

代码实现

    public boolean contains(int key){
        ListNode cur = this.head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

5.得到单链表的长度：public int Size()

定义计数器count = 0，通过head的移动来判断链表长度（注意：同样要定义一个cur来代替head）

代码实现

    public int Size(){
        int count = 0;
        ListNode cur = this.head;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

6.任意位置插入,第一个数据节点为0号下标：public boolean addIndex(int index,int data)

比如，我们把一个值为1314，地址是0x520（设为node引用）的节点，即val域值为1314，next域为null，地址是520，将该节点插入至3号位置，

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Zmc5Zmc5Zmc5Zmc6bKB5YWI55Sf,size_20,color_FFFFFF,t_70,g_se,x_16

经过分析，需要将head先移至2号位置（注意：用cur代替head，防止head丢失），然后

node.next = cur.next使该节点的next域改为下一节点的地址，再cur.next = node.next使前一节点

的next域改为该节点的地址。

    public void addIndex(int index,int data){
        if(index < 0 ||index > Size()){   //对index位置的合法性进行判断
            return;
        }
        if(index == 0){          //相当于头插法
            addFirst(data);
            return;
        }
        if(index = Size()){      //相当于尾插法
            addLast(data);
            return;
        }
        ListNode cur = findIndex(index);//找到index位置前一位置的地址
        ListNode node = new ListNode(data);//初始化node
        node.next = cur.next;
        cur.next = node;
    }

7.删除第一次出现关键字为key的节点：public void remove(int key)

对于删除第一次出现的key值的节点，若不是头节点，我们只需将key值对应的节点的前一节点的next的域改为key值对应的节点的next域即可。

对于头节点，直接head = head.next即可。

对于key值对应的节点的前一节点，我们可以写一个函数来找到它，方便后续的代码书写。

    //找到key的前驱（前一节点）
    public ListNode searchPrev(int key){
        ListNode cur = this.head;
        while(cur.next != null){
            if(cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if(this.head == null){
            return;
        }
        if(this.head.val == key){
            this.head = this.head.next;
            return;
        }
        ListNode cur = searchPrev(key);
        if(cur == null){
            return;             //没有要删除的节点
        }
        ListNode del = cur.next;//定义要删除的节点
        cur.next = del.next;
    }

8.删除所有值为key的节点：public void removeAllKey(int key)

若要删除所有值为key的节点，其实我们只需多次调用上面所写的remove函数即可完成，但是，

若要达到面试难度，那么要求就是遍历一遍链表，删除所有值为key的节点。

情况一:key连续,如下(1,2,3节点)

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Zmc5Zmc5Zmc5Zmc6bKB5YWI55Sf,size_20,color_FFFFFF,t_70,g_se,x_16

情况二:key不连续,如下(1,3节点)

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Zmc5Zmc5Zmc5Zmc6bKB5YWI55Sf,size_20,color_FFFFFF,t_70,g_se,x_16

代码实现:

    public ListNode removeAllKey(int key){
        if(this.head = null){
            return null;
        }
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        while(cur != null){
            if(cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        if(this.head.val == key){
            this.head = this.head.next;
        }
        return this.head;
    }

9.清空链表：public void clear()

1.简单粗暴的方法：将头节点置为空head = null；即可

2.细腻温柔的做法：将每一个节点都置为空

    public void clear(){
        while(this.head != null){
            ListNode curNext = this.head.next;
            this.head.next = null;
            this.head = curNext;
        }
    }

源码

import java.util.List;


//ListNode代表一个节点
class ListNode{
    public int val;
    public ListNode next;

    //构造函数
    public ListNode(int a){
        this.val = a;
    }
}
public class MyLinkedList {

    public ListNode head;//链表的头

    public void creatList() {
        ListNode listNode1 = new ListNode(11);
        ListNode listNode2 = new ListNode(22);
        ListNode listNode3 = new ListNode(33);
        ListNode listNode4 = new ListNode(44);
        ListNode listNode5 = new ListNode(55);

        this.head = listNode1;

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

    }

    //头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = this.head;
        this.head = node;
        /*if(this.head == null){
            this.head = node;
        }else{
            node.next = this.head;
            this.head = node;
        }*/
    }

    //尾插法
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (this.head == null) {
            this.head = node;
        } else {
            ListNode cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    //打印顺序表
    public void display() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //得到单链表的长度
    public int Size() {
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    //找到index位置的前一位置的地址
    public ListNode findIndex(int index) {
        ListNode cur = head.next;
        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index, int data) {
        if (index < 0 || index > Size()) {
            return;
        }
        if (index == 0) {          //相当于头插法
            addFirst(data);
            return;
        }
        if (index == Size()) {      //相当于尾插法
            addLast(data);
            return;
        }
        ListNode cur = findIndex(index);//找到index位置前一位置的地址
        ListNode node = new ListNode(data);//初始化node
        node.next = cur.next;
        cur.next = node;
    }

    //找到key的前驱（前一节点）
    public ListNode searchPrev(int key) {
        ListNode cur = this.head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        if (this.head == null) {
            return;
        }
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        ListNode cur = searchPrev(key);
        if (cur == null) {
            return;             //没有要删除的节点
        }
        ListNode del = cur.next;//定义要删除的节点
        cur.next = del.next;
    }

    //删除所有值为key的节点
    public ListNode removeAllKey(int key) {
        if (this.head = null) {
            return null;
        }
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        while (cur != null) {
            if (cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        if (this.head.val == key) {
            this.head = this.head.next;
        }
        return this.head;
    }

    //清空链表
    public void clear() {
        while (this.head != null) {
            ListNode curNext = this.head.next;
            this.head.next = null;
            this.head = curNext;
        }
    }
}

本文链接：https://blog.csdn.net/m0_57950108/article/details/121639962

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

视频监控安防平台-国标28181-2016（GB28181-2016）平台全项检测_怎么验证是否符合28181-2016标准-程序员宅基地

文章浏览阅读1w次，点赞4次，收藏18次。视频监控安防平台-国标28181 2016 GB28181 2016平台全项检测_怎么验证是否符合28181-2016标准

In Defense of Nearest-Neighbor Based Image Classification-程序员宅基地

文章浏览阅读1.4k次。OrenBoiman, Eli Shechtman, Michal Irani. In Defense of Nearest-Neighbor Based ImageClassification. IEEE Conference on Computer Vision & Pattern Recognition,2008, 69(4): 1～8这篇文章是我在做本科毕业设计《基于视频的运动目标检测_in defense of nearest-neighbor based image classification

史上最全量化交易资源整理_量化交易交易费用对比-程序员宅基地

文章浏览阅读2.5w次，点赞48次，收藏435次。开源量化交易框架整理： https://www.oschina.net/p/samaritan https://www.oschina.net/p/vn-py https://www.oschina.net/p/abu https://www.oschina.net/p/abuquant https://github.com/sun0x00/RedTorch ..._量化交易交易费用对比

chrome浏览器崩溃终极解决方法_getfileattributes c:\users\zhang\appdata\local\goo-程序员宅基地

文章浏览阅读1.2k次。如果没有找到传说中的病毒文件，就别折腾了，卸载重装重装前备份下数据：C:\Users\{{这里是你的用户名}}}\AppData\Local\Google\Chrome将这下面的文件备份到其他位置，卸载重装。..._getfileattributes c:\users\zhang\appdata\local\google\chrome\user data\crash

俄罗斯方块java教程_JAVA课程设计——俄罗斯方块（团队）-程序员宅基地

文章浏览阅读345次。1.团队介绍1.1 团名：终于可以回家了嗷嗷嗷1.2 团员介绍2.参考来源3.项目git地址3.1Git代码管理4.前期调查5.项目功能架构图、主要功能流程图6.UML图7.运行截图7.1登陆界面7.2注册成功7.3登陆后转换为游戏界面7.4排行榜8.关键代码8.1登陆界面账号密码匹配操作，优先匹配账号8.2文件更新操作，每轮游戏过后，都会将所获得的信息进行更新8.3对文件中的分数进行排序操作，取..._java俄罗斯方块分数排行

AI绘画怎么玩？Midjourney教程来啦！-程序员宅基地

文章浏览阅读1k次，点赞42次，收藏7次。AIGC技术的未来发展前景广阔，随着人工智能技术的不断发展，AIGC技术也将不断提高。未来，AIGC技术将在游戏和计算领域得到更广泛的应用，使游戏和计算系统具有更高效、更智能、更灵活的特性。同时，AIGC技术也将与人工智能技术紧密结合，在更多的领域得到广泛应用，对程序员来说影响至关重要。未来，AIGC技术将继续得到提高，同时也将与人工智能技术紧密结合，在更多的领域得到广泛应用。感兴趣的小伙伴，赠送全套AIGC学习资料和安装工具，包含AI绘画、AI人工智能等前沿科技教程，模型插件，具体看下方。

随便推点

产品经理（22） #运营_史莱姆商家运营-程序员宅基地

文章浏览阅读247次。目录运营岗位分工解决问题活动内容运营运营究竟在做什么拉新 acquisition 用户增长增长黑客促活&留存 activation&retention转化 revenueCASE1:公众号底栏设置新媒体运营导论流量获取平台流量：基础（主要借由内容手段在各个平台做粉丝累积，用户累积）社区流量：流量沉淀微信生态：流量变现流量循环体系流量循环抖音平台简介相关概念知乎运营新平台运营通用方法论选问题——._史莱姆商家运营

JOptionPane用法--Java-程序员宅基地

文章浏览阅读410次。JOptionPane的简单应用： 1.首先引入包： import javax.swing.JOptionPane; 2.添加如下代码： Object[] options = {"确定","取消","帮助"}; //定制可供选择按钮 int response=JOpt..._joptionpane需要什么包

Java课程设计【学生信息管理系统】_学生信息管理系统java课程设计-程序员宅基地

文章浏览阅读7.2w次，点赞229次，收藏1.8k次。这次课程设计总体来说是一次非常有意义的任务，因为在这次课程设计中我学会了很多GUI编程和流类的知识，提高了编程的能力，也增加了对编程的兴趣。虽然这是一个小项目，但是能把它做好也是有很大的满足感。虽然一开始遇到很多问题，但自己都咬牙克服、迎难而上，每天都在钻研程序，然后将自己的思想与同学们交流。可以说，没有付出就没有回报，只要你肯付出，就会有收获。一件事，你只要用心去做了，将它做好，无论结果如何，你都不会留有遗憾的。_学生信息管理系统java课程设计

等保2.0|二级等保和三级等保要求对比_等保2.0三级和四级标准要求区别-程序员宅基地

文章浏览阅读1.2w次，点赞3次，收藏25次。等保2.0标准正式实施已经一年多的时间，在这一年多时间里，国内各个行业、单位陆续推进网络安全等级保护工作，特别是在关键信息基础设施的政府、金融、医疗、交通等关系国计民生的重点行业，先后出台针对行业的等级保护要求。等保2.0标准的正式实施，提升了我国网络安全保护工作水平，不断筑牢网络安全防线，有效维护各行业关键基础设施与网络信息安全。等级保护制度是我国网络安全的基本制度。等级保护是指对国家重要信息、法人和其他组织及公民的专有信息以及公开信息和存储、传输、处理这些信息的信息系统分等级实行安全保护，对信息.._等保2.0三级和四级标准要求区别

第5节LMDeploy 大模型量化部署实践：笔记_llmdeploy-程序员宅基地

文章浏览阅读1.6k次，点赞33次，收藏34次。我们先来介绍一下大模型的特点：首先就是参数量大，对于7B的模型，就需要14G以上的内存，并且由于是采用自回归的方式，所以这就需要去缓存之前的信息，这就会进一步增加消耗。而部署的定义就是将训练好的模型放在特定的环境（cpu，gpu，tpu，npu）接收输入，产生输出。这就要对模型进行优化，如模型压缩和硬化加速。从上面可以得出如何在低存储的设备上部署？如何提高token推理的速度？如何解决动态token的问题？如何提供系统吞吐量？对此现在有很多成熟的技术：低比特量化，模型并行等。_llmdeploy

信号量~~_sem_t-程序员宅基地

文章浏览阅读672次。信号量本质是一个计数器~用来描述临界资源的有效个数~POSIX和systeam V信号量都用于同步工作，达到无冲突的访问共享资源。但是POSIX可以用于线程同步~使用信号量首先就要创建一个sem_t类型的变量#include //头文件sem_t sem1;_sem_t