当前位置：首页 > news >正文

数据结构：链表

news 来源：原创 2025/7/17 14:45:53

链表的概念及结构：

链表的概念：

链表是一种物理储存结构上非连续的储存结构，数据元素的逻辑顺序是通过引用链接次序实现的

那物理存储结构连续是什么意思？

之前我们讲过顺序表，顺序表的底层是数组，如下：

因为数组开辟的空间，是连续的，这里所储存的数据，它们在物理储存结构上是连续的。

链表的结构：

链表是一个节点链接另一个节点的，一个节点都是一个对象。

如果我用链表储存11,22,33,44,55这几个数据，首先我们有五个节点，因为节点是对象，所以会分配地址。

并把这些数据储存到对应的节点里面，然后再将他们连接起来。

这个链表叫做单向不带头非循环链表。

这是单向带头非循环链表，两个的区别是，带头链表多了一个头（也叫哨兵位），头插一个元素时，带头链表会将新的元素放在头（哨兵位）的后面。带头链表的值没有意义，所以也可以不用放数据。但是不带头链表，头插的时候，头插在第一个元素的前面即可。

链表分类：

这就是循环链表，最后一个节点又指向第一个节点，形成一个圈。

单向不带头非循环链表的实现：

我先创建一个内部类（节点）：

static class ListNode(){int val;Listnode next;
//构造方法public ListNode(int val){this.val=val;}
}
//还要有一个头结点
ListNode head=null;

在ListNode类中，val用来存储数据，而next用来指向下一个节点，再写一个构造方法用来初始化val值。

定义一个头节点可以利于遍历链表。

实现链表dispaly（打印链表）：

如何打印上面链表？我们要打印出每个节点的val值，并利用每个节点的next找到下一个节点。

一直这样循环，一直到最后一个节点的next值为null停止。

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

这里要注意一点：不要直接拿头结点head去遍历链表，会导致最后head指向链表的尾部，后续操作就不方便了。所以重新定义一个cur节点等于头结点。用cur来遍历数组。

实现链表addFirst（头插）：

在实现链表头插时要分情况：

1.如果链表为空：

这种情况，只用定义新的节点，让头结点指向新节点

public void addFirst(int data){
//链表为空的情况if(head==null){ListNode node=new ListNode(data);head=node;}
}

2、如果链表不为空：

这种情况怎么头插呢？

首先：我们还是要第一个新的节点，让这个新的节点的next值指向head头节点，最后将head头节点指向新的头结点。

public void addFirst(int data){
//链表为空的情况if(head==null){ListNode node=new ListNode(data);head=node;
//链表不为空的情况}else{ListNode node=new ListNode(data);node.next=head;head=node;}
}

最后发现，这两种情况可以合并为：

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

实现链表addLast（尾插）：

实现尾插时也要分情况

1.如果链表不为空：

如果对这个链表进行尾插，应该怎么做呢？

首先我们要遍历链表到这个链表的尾部，然后将要插入的节点与尾节点连接，完成尾插。

public void addLast(int data){
//创建一个新的节点ListNode node=new ListNode(data);ListNode cur=head;
//遍历到链表尾部while(cur.next!=null){cur=cur.next;}
//插入尾部cur.next=node;
}

2.如果链表为空：

如果用上面1的方法，会出现空指针异常。

所以如果为空链表，我们就直接将head头节点指向需要插入的节点,加一个if语句进行判断。

public void addLast(int data){ListNode node=new ListNode(data);
//为空链表的情况if(head==null){head=node;}
//不为空链表的情况ListNode cur=head;while(cur.next!=null){cur=cur.next;}cur.next=node;
}

实现链表size（求链表长度）：

既然要求链表的长度，并定义一个计数器，遍历链表时，只要当前节点不为null，计数器就加1

注意：这里遍历链表时，我们不用head，重新定义一个节点指向head，然后往后遍历。

public int size(){
int count=0;//计数器
ListNode node=head;
//开始遍历数组while(node!=null){count++;node=node.next;}return count;
}

实现链表addIndex（指定位置下插入数据）：

既然要在指定位置下插入数据，我们首先就要考虑所提供的下标是否越界：

所以Index（下标）不能小于0，也不能大于链表的长度。

然后如果Index==0，则直接调用头插的方法，如果index==链表的长度，就直接调用尾插的方法。

这里有一个新节点ListNode node =new ListNode(25)，要把新节点25插入到22和33之间，应该怎么做呢？

这里我们重新定义一个cur=head；

将cur遍历到22节点的位置

因为我们要将25这个节点插入2下标的位置，所以要将cur从head移动2-1个位置到22这个位置（这样才方便插入）

node.next=cur.next;

cur.next=node;

public void addIndex(int Index,int data){
int len=size();//求链表的长度 
//判断Index下标是否异常 if(Index<0||Index>len){System.out.print("下标异常");return ;}
//特殊处理Index==0或者Index==len
if(Index==0){addFirst(data);}
if(Index==len){addLast(data);}
//插入到链表的中间下标
ListNode cur=head;
ListNode node=new ListNode(data);
//找到插入下标的前一个位置
while(Index-1!=0){cur=cur.next;
Index--;}
//开始插入
node.next=cur.next;
cur.next=node;
}

`实现链表remove（删除指定节点）：

给一个链表，我们如果要删除33这个节点，应该怎么删除呢？

首先，如果这个节点为空，我们直接提前返回。

我们如果要删除33这个节点，那我们要重新定义一个节点，让这个节点指向被删除的节点的前一个节点，也就是22这个节点。怎么找呢？

先有一个大循环，遍历链表，直到链表为空，然后嵌套一个if，找到被删除节点的前一个节点。

//这个函数用来删除节点
public void remove(int key){if(head==null){return ;}
//如果第一个节点是要删除的节点if(head.val==key){head=head.next;}
//第三种情况
ListNode node=findKey(key);//这时node节点就是要删除的节点的前一个节点
node.next=node.next.next;//删除key节点
}
//这个函数用来找到被删除节点的前一个节点public ListNode findKey(int key){ListNode cur=head;
//遍历链表
while(cur!=null){if(cur.next.val==key){return cur;}cur=cur.next;}
return null;
}

实现链表clear（清空链表）：

清空链表有两种方法：

1.最简单的方法：将链表的头节点置为空。

public void clear(ListNode head){head=null;
}

2.第二种方法：遍历链表，将链表的所有的节点全部置为空。

public void clear(ListNode head){
ListNode cur=head;while(cur!=null){ListNode curN=cur.next;//curN指向后一个节点cur.next=null;//将当前的cur节点的next域置为nullcur=curN;//将cur移到curN的位置}
}

数据结构：链表

链表的概念及结构： 链表的概念： 链表是一种物理储存结构上非连续的储存结构，数据元素的逻辑顺序是通过引用链接次序实现的那物理存储结构连续是什么意思？ 之前我们讲过顺序表，顺序表的底层是数组，如下…...

编程日记 2025/7/17 14:45:53

【高并发内存池】从零到一的项目之高并发内存池整体框架设计及thread cache设计

个人主页 ： zxctscl 专栏【C】、【C语言】、【Linux】、【数据结构】、【算法】如有转载请先通知文章目录前言1. 高并发内存池整体框架设计2. 高并发内存池--thread cache2.1 定长内存池的问题2.2 整体框架2.3 自由链表2.4 thread cache哈希桶的对齐规则2.5…...

编程日记 2025/7/17 14:44:35

电气动调节单座V型球阀带阀杆节流套沟槽孔板的作用-耀圣

电气动调节单座V球阀杆节流套是阀门中的一个重要组件，主要用于调节和控制流体介质的流量、压力或流速，同时兼具导向、密封和稳定阀杆运动降低流速减少冲刷的作用。以下是其具体功能和应用场景的详细说明： 1. 节流与流量控制** 作用原理**&am…...

编程日记 2025/7/17 14:29:00

vscode使用笔记

文章目录安装快捷键 vscode是前端开发的一款利器。安装快捷键 ctrlp # 查找文件(和idea的双击shift不一样) ctrlshiftf # 搜索内容...

编程日记 2025/7/17 14:38:45

基于 SpringAI 整合 DeepSeek 模型实现 AI 聊天对话

目录 1、Ollama 的下载配置与 DeepSeek 的本地部署流程 1.1 下载安装 Ollama 1.2 搜索模型并进行本地部署 2、基于 SpringAI 调用 Ollama 模型 2.1 基于OpenAI 的接口规范（其他模型基本遵循） 2.2 在 IDEA 中进行创建 SpringAI 项目并调用 DS 模型 3、基…...

编程日记 2025/7/17 14:00:21

Idea创建项目的搭建方式

目录一、普通Java项目二、普通JavaWeb项目三、maven的JavaWeb项目四、maven的Java项目一、普通Java项目 1. 点击 Create New Project 2. 选择Java项目，选择JDK，点击Next 3. 输入项目名称（驼峰式命名法），可选…...

编程日记 2025/7/17 8:02:59

【MATLAB第115期】基于MATLAB的多元时间序列的ARIMAX的预测模型

【MATLAB第115期】基于MATLAB的多元时间序列的ARIMAX的预测模型 ‌一、简介 ARIMAX‌（Autoregressive Integrated Moving Average with eXogenous inputs）模型是一种结合自回归（AR）、差分（I）、移动平均&a…...

编程日记 2025/7/15 4:12:25

【以太网安全】——防护高级特性配置总结

目前网络中以太网技术的应用非常广泛、然后、各种网络攻击的纯在（例如针对ARP DHCP 等攻击）不仅造成了网络合法用户无法正常访问网络资源、而且对网络信息安全构成严重威胁、以下配置是对局域网安全配置命令做详解主要的安全威胁 MAC攻击:泛洪、欺骗 …...

编程日记 2025/7/9 1:27:42

微信小程序 van-dropdown-menu

点击其他按钮，关闭van-dropdown-menu下拉框 DropdownMenu 引入页面使用index.wxmlindex.scssindex.ts(重点)index.ts(全部) DropdownMenu 引入在app.json或index.json中引入组件 "usingComponents": {"van-dropdown-menu": "vant/weapp…...

编程日记 2025/7/16 8:07:02

再见 Smartdaili，你好 Decodo！

我们将翻开新的篇章，推出新的名称以及更好的代理和刮擦解决方案。了解我们如何帮助全球用户构建、测试和扩展他们的公共网络数据项目。 Smartproxy，即后来的Smartdaili，由一个行业专业人士和企业家团队于2018年创立，其使命是创建一…...

编程日记 2025/7/16 22:03:06

海量文本中的词语距离：在 O(n) 时间内找到最近的词对

想象一个巨大的日志文件、一部鸿篇巨著或者网络爬虫抓取的数据——它们可能达到 TB 级别。现在，假设你需要找出两个特定的词（比如词语1 和词语2）在这段庞大文本中出现时，彼此“靠得最近”的距离是多少。挑战： …...

编程日记 2025/7/16 22:19:06

TextCNN 模型文本分类实战：深度学习在自然语言处理中的应用

在自然语言处理（NLP）领域，文本分类是研究最多且应用最广泛的任务之一。从情感分析到主题识别，文本分类技术在众多场景中都发挥着重要作用。最近，我参与了一次基于 TextCNN 模型的文本分类实验，从数据准备到…...

编程日记 2025/7/12 15:26:37

前台调用接口的方式及速率对比

一、引言在现代 Web 开发中，前台与后台的数据交互至关重要，而调用接口是实现这一交互的关键手段。不同的接口调用方式在速率上可能存在差异，这会影响用户体验和应用性能。本文将详细介绍几种常见的前台调用接口方式，并对它们的速…...

编程日记 2025/6/29 9:32:49

高级java每日一道面试题-2025年4月21日-基础篇[反射篇]-如何使用反射获取一个类的所有方法？

如果有遗漏,评论区告诉我进行补充面试官: 如何使用反射获取一个类的所有方法？ 我回答: 在Java中，反射是一种强大的机制，允许程序在运行时检查或“反射”自身，从而动态地操作类、字段、方法和构造函数等。这在需要动态调用方法…...

编程日记 2025/7/11 23:28:52

中间件：Tomcat、Redis、Nginx jar包要和tomcat相匹配 jar包：commons-pool2-2.2.jar、jedis-2.5.2.jar、tomcat-redis-session-manage-tomcat7.jar 配置Tomcat /conf/context.xml <?xml version1.0 encodingutf-8?> <!--Licensed to the A…...

编程日记 2025/7/11 22:56:32

2.6 递归

递归特性： >.一递一归 >.终止条件一般为：0 1 -1 #测试函数的返回值为函数 def test_recursion():return test_recursion() print(test_recursion()) RecursionError: maximum recursion depth exceeded #案例：计算 …...

编程日记 2025/7/16 17:02:38

鸿蒙应用开发：如何修改APP名称与APP的图标

如何修改APP的名称？ 修改APP的名称需要修改entry/src/main/resources/base/element/string.json文件将EntryAbility_label的value修改为“需要修改成的名字”。文件目录： 代码修改： {"string": [{"name": "modu…...

编程日记 2025/7/15 16:44:48

AI 模型在前端应用中的典型使用场景和限制

典型使用场景 1. 智能表单处理 // 使用TensorFlow.js实现表单自动填充 import * as tf from tensorflow/tfjs; import { loadGraphModel } from tensorflow/tfjs-converter;async function initFormPredictor() {// 加载预训练的表单理解模型const model await loadGraphMod…...

编程日记 2025/7/17 14:14:20

前端性能优化全攻略：JavaScript 优化、DOM 操作、内存管理、资源压缩与合并、构建工具及性能监控

1 为什么需要性能优化？ 1.1 性能优化的核心价值：用户体验与业务指标性能优化不仅是技术层面的追求，更是直接影响用户体验和业务成败的关键因素。用户体验（UX）： 响应速度：用户期望页面加载时…...

编程日记 2025/7/9 6:36:30

使用 acme.sh 自动更新 SSL 证书的指南

上篇文章讲了一下如何利用acme.sh来申请ssl，但没有讲3个月到期后如何续期，续期的时候会碰到什么问题？ 1.查看当前的当前签发域名的到期时间 acme.sh list 2.重新申请ssl acme.sh --issue --dns dns_namesilo -d xxx.ai -d *.xxx.ai --dns…...

编程日记 2025/7/16 20:17:31

查看Spring Boot项目所有配置信息的几种方法，包括 Actuator端点、日志输出、代码级获取等方式，附带详细步骤和示例

以下是查看Spring Boot项目所有配置信息的几种方法，包括 Actuator端点、日志输出、代码级获取等方式，附带详细步骤和示例： 1. 使用Spring Boot Actuator Actuator是Spring Boot提供的监控和管理工具，包含/configprops端点可查看…...

编程日记 2025/6/29 9:32:50

C++与C

文章目录 C与C命令空间const关键字new/delete表达式引用（重点）概念引用的本质引用的使用场景引用作为函数的参数引用作为函数的返回值总结强制转换函数重载extern "C"默认参数 bool类型inline（内联）函数异常处理&…...

编程日记 2025/7/10 14:18:24

Nginx中间件的解析

目录一、Nginx的核心架构解析二、Nginx的典型应用场景三、Nginx的配置优化实践四、Nginx的常见缺陷与漏洞一、Nginx的核心架构解析事件驱动与非阻塞IO模型 Nginx采用基于epoll/kq等系统调用的事件驱动机制，通过异步非阻塞方式处理请求，…...

编程日记 2025/7/14 16:30:39

Ansys Zemax | 在 MATLAB 中使用 ZOS-API 的技巧

附件下载联系工作人员获取附件本文将介绍一些在MATLAB中使用 ZOS-API 的技巧，以提高您的工作效率并充分利用 ZOS-API 的功能。简介 OpticStudio开发了应用程序接口 (API) ，用户可以使用API与不同的脚本环境进行连接和交互。使用API，用…...

编程日记 2025/7/13 15:54:02

js 生成pdf 并上传文件

js 生成pdf 并上传文件使用 JsPDF html2Canvas 代码直接使用注意注释 import JsPDF from jspdf import html2Canvas from html2canvas // 上传文件的方法 import { handleUploadImage } from /utils/uploadQuillEditdownPDF() {// 要打印元素的idconst cloneDom document.…...

编程日记 2025/7/17 14:41:13

刷刷刷刷刷sql题

NSSCTF 【SWPUCTF 2021 新生赛】easy_sql 这题虽然之前做过，但为了学习sql，整理一下就再写一次打开以后是杰哥的界面注意到html网页标题的名称是 “参数是wllm” 那就传参数值试一试首先判断注入类型（数字型或字符型） 传1 …...

编程日记 2025/7/11 18:12:28

JavaScript 中的 this 及 this 指向的改变方法

在 JavaScript 的世界里，this是一个既强大又容易让人困惑的概念。它的指向在不同的函数调用场景下会动态变化，而call()、apply()和bind()这三个方法则为我们提供了精确控制this指向的能力。本文将从基础概念出发，结合具体案例，带大…...

编程日记 2025/6/29 9:32:58

安卓模拟器绕过检测全解析：雷电、MuMu、蓝叠、逍遥、夜神与WSA完整指南

安卓模拟器绕过检测全解析：雷电、MuMu、蓝叠、逍遥、夜神与WSA完整指南模拟器过检测合集雷电mumu蓝叠逍遥夜神WSA 转自风车2025 前言随着手机游戏和应用的普及，越来越多的用户选择在PC上通过模拟器来运行安卓应用。然而，许多应用和游戏为…...

编程日记 2025/7/17 13:14:55

VSCode中安装GitGraph

前提是先安装git，官方下载地址：Git - Downloads 1. 在VSCode中安装GitGraph插件 2. 文件->首选项->设置，打开设置界面，在设置界面搜索git path 3. 打开配置文件配置git安装路径： 4. 打开源代码管理，…...

编程日记 2025/7/9 1:28:02

StartAI「万物迁移」功能设计师实操教程：模特换衣场景应用

一、功能核心优势解析智能识别与场景融合基于迁移学习算法，精准定位服装轮廓（支持复杂材质如蕾丝、镂空设计），自动匹配目标场景的光影方向与色温。效率革命传统PS手动换衣需2-3小时，使用万物迁移可压缩至2-5分…...

编程日记 2025/6/29 10:25:10

【RK3588 嵌入式图形编程】-SDL2-扫雷游戏-放置标记

放置标记文章目录放置标记1、概述2、更新Globals.h3、放置标记4、渲染标记5、标记计数6、完整代码7、改进建议8、总结在本文中，我们实现标记放置和跟踪以完成的扫雷游戏项目。 1、概述在我们扫雷游戏文章系列的最后部分中，我们将添加玩家在可疑的地雷位置放置标记的功能。…...

编程日记 2025/7/12 1:51:45

【Python】Selenium切换网页的标签页的写法（全！！！）

在使用selenium做网站爬取测试的时候，我们经常会遇到一些需要点击的元素，才能点击到我们想要进入的页面， 于是我们就要模拟不断地点点点击鼠标的样子。这个时候网页上就会有很多的标签页，你的浏览器网页标签栏 be like: 那…...

编程日记 2025/7/16 22:38:01

Spring Boot多环境配置详解

一、为什么需要多环境配置在实际项目开发中，我们通常需要将应用部署到不同的环境中，比如： 开发环境（dev） - 开发人员本地开发调试使用测试环境（test） - 测试人员功能测试使用生产环境&#x…...

编程日记 2025/7/12 21:46:50

进阶篇第 6 篇：时间序列遇见机器学习与深度学习

进阶篇第 6 篇：时间序列遇见机器学习与深度学习 (图片来源: Tara Winstead on Pexels) 在上一篇中，我们探讨了如何通过精心的特征工程，将时间序列预测问题转化为机器学习可以处理的监督学习任务。我们学习了如何创建滞后特征、滚动统计特征…...

编程日记 2025/7/11 22:40:51

RHCE 作业二（密钥登录实验）

1.进入ssh主配置文件恢复配置： 2.vim进入ssh子文件夹查看配置 3.重启服务 /etc/ssh/ key结尾或者.pub结尾的文件全部都是密钥 sshd_confg.d目录是服务的子配置文件 ssh_confg.d目录是客户端你的子配置文件 ~/.ssh/ 是当前用户的配置文件 4.服务器和客户端分别…...

编程日记 2025/6/29 9:34:27

android contentProvider 踩坑日记

写此笔记原因学习《第一行代码》到第8章节实现provider时踩了一些坑，因此记录下来给后来人和自己一个提示，仅此而已。包含内容 Sqlite数据库CURD内容provider界面provider项目中书籍管理provider实现逻辑用adb shell确认providercontentResolver接收…...

编程日记 2025/6/29 9:32:56

K8s：概念、特点、核心组件与简单应用

一、引言在当今云计算和容器技术蓬勃发展的时代，Kubernetes（简称 K8s）已成为容器编排领域的事实标准。它为管理容器化应用提供了高效、可靠的解决方案，极大地简化了应用的部署、扩展和运维过程。无论是小型初创公司还是大型企业…...

编程日记 2025/7/11 1:04:55

基于表面肌电信号sEMG的手势识别——以Ninapro DB1数据集使用CNN网络识别为例

完整代码获取评论区或者私信留邮箱接论文辅导！中文核心辅导！SCI三四区辅导！ 可接模型改进任务描述表面肌电信号( sEMG ) 是一种生物电信号，存在于肌肉神经。当大脑下达肌肉动作指令，肌肉会产生控制信号&#xff…...

编程日记 2025/7/10 18:27:36

黑盒测试——等价类划分法实验

任务： 设某程序有两个输入：整数x1和整数x2，计算Yf(x1,x2)。x1和x2的取值范围为1< x1<500,1< x2<500。当x1在[1,200) 取值且x2在[1,300] 取值时，Yf(x1,x2) x1x2；当x1在[200,500] 取值且x2在[1,300] 取值时&…...

编程日记 2025/7/11 12:05:01

深度学习4月22笔记

1、过拟合与欠拟合在训练深层神经网络时，由于模型参数较多，在数据量不足时很容易过拟合。而正则化技术主要就是用于防止过拟合，提升模型的泛化能力(对新数据表现良好)和鲁棒性（对异常数据表现良好）。 1. 概念认知 …...

编程日记 2025/7/17 8:20:38

【MySQL数据库入门到精通-03 数据类型及案列】

文章目录一、三类数据类型二、数值类型三、字符串类型四、日期时间类型五、日期时间类型一、三类数据类型 MySQL中的数据类型有很多，主要分为三类：数值类型、字符串类型、日期时间类型。二、数值类型比如： 1). 年龄字段 – 不会出现负数…...

编程日记 2025/7/15 11:40:37

【机器学习】决策树算法中的 “黄金指标”：基尼系数深度剖析

一、基尼系数的基本概念基尼系数（Gini Impurity）在决策树分类算法中，是用于衡量数据纯度的重要指标，与信息熵有着相似的功能。在样本集合里，基尼系数代表随机选取一个样本时，该样本被分错的概率。假设一…...

编程日记 2025/7/16 18:40:15

植被参数遥感反演技术革命！AI+Python支持向量机/随机森林/神经网络/CNN/LSTM/迁移学习在植被参数反演中的实战应用与优化

在全球气候变化与生态环境监测的重要需求下，植被参数遥感反演作为定量评估植被生理状态、结构特征及生态功能的核心技术，正面临诸多挑战。随着遥感技术的发展，数据复杂度不断提升，模型精度的要求也越来越高。同时，多源…...

编程日记 2025/7/13 11:57:40

【AI】SpringAI 第四弹：接入本地大模型 Ollama

Ollama 是一个开源的大型语言模型服务工具。它的主要作用是帮助用户快速在本地运行大模型， 简化了在 Docker 容器内部署和管理大语言模型（LLM）的过程。 1. 确保Ollama 已经启动 # 查看帮助文档 ollama -h# 自动下载并启动 ollama run deeps…...

编程日记 2025/7/11 1:17:17

C# MP3 伴奏

使用建议： 参数调节指南： 低频人声残留：降低CenterFrequency(800-1500Hz) 高频人声残留：提高CenterFrequency(2500-3500Hz) 消除力度不足：提高EliminationStrength(0.9-1.0) 伴奏失真：降低EliminationSt…...

编程日记 2025/7/14 8:55:24

【springsecurity oauth2授权中心】将硬编码的参数提出来放到 application.yml 里 P3

在application.yml里添加配置 application.yml oauth2:client:id: clientsecret: secretauthentication-method: client_secret_basicgrant-types: authorization_code,refresh_tokenredirect-uris:- http://localhost:8081/login/oauth2/code/client- http://localhost:8081…...

编程日记 2025/7/10 19:29:37