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

[数据结构] 链表

news 来源：原创 2025/5/26 7:44:25

1.链表的基本概念

2.链表的实现 -- 节点的构造和链接

节点如何构造?

如何将链表关联起来?

3.链表的方法(功能)

1).display() -- 链表的遍历

2).size() -- 求链表的长度

3).addFirst(int val) -- 头插法

4).addLast(int val) -- 尾插法

5).addIndex -- 在任意位置插入

6).contains(int val) -- 链表中是否包含某个元素

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

8).removeAll(int val) -- 删除所有出现的关键字的节点

9).clear() -- 清空

回收对象,防止浪费 : head == null;

1.链表的基本概念

链表（Linked List）是一种常见的基础数据结构，它由一系列节点（Node）组成，每个节点包含两部分：一部分存放数据元素，另一部分存放指向下一个节点的指针.

2.链表的实现 -- 节点的构造和链接

节点如何构造?

在 Java 中，通常通过定义一个类来表示链表中的节点。每个节点通常包含两个部分：数据域和指针域。对于单向链表，每个节点的指针域指向下一个节点.

public class LinkedList {// 定义链表节点static class ListNode {int val; // 数据域ListNode next; // 指针域ListNode(int x) {this.val = x;this.next = null;}}public ListNode head;
}

如何将链表关联起来?

通过访问node1的指针域next,将其赋值为下一个节点的地址,以此类推,最后让头节点head指向第一个节点node1.

        node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;

3.链表的方法(功能)

1).display() -- 链表的遍历

首先，我们创建一个名为 cur 的局部变量，它是一个指向 ListNode 类型的引用。将链表的头节点（head）赋值给 cur，这样我们就有了一个可以用来遍历整个链表的起始点.使用 while 循环来遍历链表。只要 cur不是 null（即还没有到达链表的末尾），就继续执行循环体内的代码。如果 cur 是 null，则说明已经到了链表的末尾，循环结束。在循环体内，我们使用 System.out.print 来打印当前节点的数据。这里用 + " -> " 格式化输出，以箭头分隔各个数据项，直观地表示出它们之间的链接关系。更新 cur指针，使其指向下一个节点（通过 cur.next 获取）。这一步非常重要，因为它确保了我们在下一次迭代时能够访问链表中的下一个节点。当循环结束后，我们额外打印一个 null，表示链表的终止。这是为了更清晰地展示链表结构，表明没有更多的节点了。

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

2).size() -- 求链表的长度

定义count变量,记录cur向后走的次数,每走一步,count++

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

3).addFirst(int val) -- 头插法

1. 将head头节点的地址传给node.next 2. 然后让head指向node

注意: 这里两步的顺序不可以交换 , 否则就是自己指向自己了

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

4).addLast(int val) -- 尾插法

1.为了避免head == null 报错, 先进行判断,若head == null , 则 head = node,然后return掉.

2.若head != null , 则这通过循环找到 cur.next == null ,最后让cur.next = node.

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

5).addIndex -- 在任意位置插入

1.判断index的合法性: (1). 定义一个 checkIndex(int index) 方法用来检查 index 的合法性

2.index == 0 || index == size();前者相当于是头插，直接调用 addFirst(),后者相当于是尾插，直接调用 addLast()

3.找到 index 的前一个位置,创建一个 findIndexSubOne(int index) 方法,创建一个节点 cur 来接收调用方法的返回值, 最后 cur 就是 index 位置的前一个节点了

4.进行连接,实例化一个所带数据为 val 的节点 node,

node.next = cur.next;

cur.next = node;

public void addIndex(int index,int val) {// 1.判断index的合法性try {checkIndex(index);} catch(IndexNotLegalException e) {e.printStackTrace();}// index == 0 || index == size()if(index == 0) {addFirst(val);return;} else if(index == size()) {addLast(val);return;}// 3.找到index前一个位置ListNode cur = findIndexSubOne(index);// 4.进行连接ListNode node = new ListNode(val);node.next = cur.next;cur.next = node;}public ListNode findIndexSubOne(int index) {ListNode cur = head;for (int i = 0; i < index - 1; i++) {cur = cur.next;}return cur;}public void checkIndex(int index) {if(index < 0 || index >size()) {throw new IndexNotLegalException("index位置不合法");}}public class IndexNotLegalException extends RuntimeException {public IndexNotLegalException() {}public IndexNotLegalException(String message) {super(message);}}

6).contains(int val) -- 链表中是否包含某个元素

遍历链表,如果能在链表中找到val,则返回true,否则,返回false

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

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

1.首先判断链表是否为空

2.循环遍历 : cur.next != null

3.找到val值的前一个节点cur : 当cur.next.val = val 时,找到目标

4.进行删除

public void remove(int key) {// 如果链表为空if(head == null) {return;}// 如果第一个元素就为val时if(head.val == key) {head = head.next;return;}ListNode cur = head;while(cur.next != null) {if(cur.next.val == key) {cur.next = cur.next.next;return;}cur = cur.next;}}

8).removeAll(int val) -- 删除所有出现的关键字的节点

定义两个引用变量
cur 代表当前需要删除的节点
prev 代表当前需要删除节点的前驱

若 cur.val == val
prev.next = cur.next
cur = cur.next
否则：
prev = cur
cur = cur.next
处理头节点

public void removeAll(int key) {if(head == null) {return;}ListNode prev = head;ListNode cur = head.next;while(cur != null) {if(cur.val == key) {prev.next = cur.next;cur = cur.next;} else {prev = cur;cur = cur.next;}}// 除了头节点都删除完成if(head.val == key) {head = head.next;}}

9).clear() -- 清空

回收对象,防止浪费 : head == null;

public void clear() {this.head = null;}

[数据结构] 链表

目录 1.链表的基本概念 2.链表的实现 -- 节点的构造和链接节点如何构造? 如何将链表关联起来? 3.链表的方法(功能) 1).display() -- 链表的遍历 2).size() -- 求链表的长度 3).addFirst(int val) -- 头插法 4).addLast(int val) -- 尾插法 5).addIndex -- 在任意位置…...

编程日记 2025/5/26 7:44:25

WPF DataTemplate 数据模板

DataTemplate 顾名思义，数据模板，在 wpf 中使用非常频繁。它一般用在带有 DataTemplate 依赖属性的控件中，如 ContentControl、集合控件 ListBox、ItemsControl 、TabControls 等。 1. 非集合控件中使用 <UserControl.Resources>&l…...

编程日记 2025/5/25 9:53:09

本地计算机上的MySQL服务启动后停止（connection refused: connect）解决一系列数据库连接不上的问题

推荐其他可能可以解决的博客： 【完美解决】mysql启动不了:本地计算机上的MySQL服务启动后停止-CSDN博客 1. 查看自己的mysql服务是否启动了，如果启动后又关闭了就使用下面这种方法我是使用重新安装 MySQL 服务解决的如果服务依然启动失败&#xf…...

编程日记 2025/5/26 7:38:57

前端使用 Konva 实现可视化设计器（20）- 性能优化、UI 美化

这一章主要分享一下使用 Konva 遇到的性能优化问题，并且介绍一下 UI 美化的思路。至少有 2 位小伙伴积极反馈，发现本示例有明显的性能问题，一是内存溢出问题，二是卡顿的问题，在这里感谢大家的提醒。请大家动动小手&a…...

编程日记 2025/5/26 5:40:25

ECharts平行坐标系-营养结构(平行坐标)-3，附视频讲解与代码下载

引言： 平行坐标系（Parallel Coordinates）是可视化高维几何和分析多元数据的常用方法。它通过在n维空间中显示一组点，绘制由n条平行线组成的背景（通常是垂直且等距的），并将描述不同变量的各点连…...

编程日记 2025/5/26 2:06:17

蓝桥杯刷题——day8

蓝桥杯刷题——day8 题目一题干解题思路代码题目二题干解题思路代码题目一题干 N 架飞机准备降落到某个只有一条跑道的机场。其中第i架飞机在 Ti时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 Di个单位时间，即它最早可以于 Ti时刻开始降落&am…...

编程日记 2025/5/23 8:58:13

WPF ControlTemplate 控件模板

区别于 DataTemplate 数据模板，ControlTemplate 是控件模板，是为自定义控件的 Template 属性服务的，Template 属性类型就是 ControlTemplate。演示， 自定义一个控件 MyControl，包含一个字符串类型的依赖属性。 pub…...

编程日记 2025/5/19 0:55:27

【Git 常用操作：pull push】

Git 基本概念 Git 是一个先进的开源的分布式版本控制系统，常用于管理工作内容、项目代码等功能。 Git 工作流程图片来源：https://www.runoob.com/git/git-basic-operations.html 说明： workspace：工作区staging area&#xff…...

编程日记 2025/5/22 14:21:13

初学stm32 --- 系统时钟配置

众所周知，时钟系统是 CPU 的脉搏，就像人的心跳一样。所以时钟系统的重要性就不言而喻了。 STM32 的时钟系统比较复杂，不像简单的 51 单片机一个系统时钟就可以解决一切。于是有人要问，采用一个系统时钟不是很简单吗？为…...

编程日记 2025/5/23 10:30:28

基于SpringBoot的图书管理系统（源码+数据库+报告）

一、项目介绍 358基于SpringBoot的图书管理系统，系统包含两种角色：管理员、用户,系统分为前台和后台两大模块二、项目技术编程语言：Java 数据库：MySQL 项目管理工具：Maven 前端技术：Vue 后端技术&#x…...

编程日记 2025/5/25 8:14:00

物理信息神经网络（PINN）八课时教案

物理信息神经网络（PINN）八课时教案第一课：物理信息神经网络概述 1.1 PINN的定义与背景物理信息神经网络（Physics-Informed Neural Networks，简称PINN）是一种将物理定律融入神经网络训练过程中的先进方…...

编程日记 2025/5/25 14:46:13

APM32F411使用IIS外设驱动es8388实现自录自播

前言： 从零开始学习I2s外设，配置Es8288寄存器实现录音播放。本文章使用主控芯片是APM32F411系类。音频相关的概念比较多，就不再次做过多的介绍，本文章只是简单实现边录边播功能。APM系类兼容st的芯片，所以用st的hal库来…...

编程日记 2025/5/25 7:30:03

flink SQL实现mysql source sink

接上文：一文说清flink从编码到部署上线环境说明：MySQL：5.7；flink：1.14.0；hadoop：3.0.0；操作系统：CentOS 7.6；JDK：1.8.0_401。 1.代码实现 1.1 E…...

编程日记 2025/5/19 7:10:11

【C#】实现Json转Lua (Json2Lua)

关键词: C#、JsonToLua、Json2Lua、对象序列化Lua 前提需引入NewtonsofJson，引入方法可先在Visual Studio 2019 将Newtonsoft.Json.dll文件导入Unity的Plugins下。 Json格式字符串转Lua格式字符串，效果如下： json字符串 {"1": &q…...

编程日记 2025/5/24 9:14:02

使用 Vue3 实现摄像头拍照功能

参考资料:MediaDevices.getUserMedia() - Web API | MDN 重要: navigator.mediaDevices.getUserMedia 需要在安全的上下文中运行。现代浏览器要求摄像头和麦克风的访问必须通过 HTTPS 或 localhost（被视为安全的本地环境）进行,如果上传服务器地址是http…...

编程日记 2025/5/22 7:28:43

ARM学习（38）多进程多线程之间的通信方式

ARM学习（38）ARM学习（38）多进程多线程之间的通信方式一、问题背景笔者在调试模拟器的时候，碰到进程间通信的问题，一个进程在等另外一个进程ready的时候，迟迟等不到，然后通过调试发现，另外一个进程变量已经变化了，但是当前进程变量没变化，需要了解进程间通信的方式…...

编程日记 2025/5/25 18:15:24

CEF127 编译指南 MacOS 篇 - 拉取 CEF 源码(五)

1. 引言在完成了所有必要工具的安装和配置后，我们进入到获取 CEF 源码的阶段。对于 macOS 平台，CEF 的源码获取过程需要特别注意不同芯片架构（Intel 和 Apple Silicon）的区别以及版本管理。本文将详细介绍如何在 macOS 系统上获…...

编程日记 2025/5/24 0:37:59

网络安全笔记

#### 网络各层安全协议链路层：链路隧道协议、加密技术网络层：包过滤机制、NAT、IPsec协议、 VPN 传输层/会话层 ：SSL/TLS 协议应用层：SHTTP、HTTPS、PGP、S/MIME等 ### 网络安全技术第二代安全技术 - 保护 - 响应 - 检测…...

编程日记 2025/5/20 10:26:23

0.准备文章目录 0.准备1.nginx2.mysql2.1 mysql82.2 mysql5.7 3.php4.测试php访问mysql5.部署 Discuz6.其他 yum源： # 没有wget，用这个 # curl -o /etc/yum.repos.d/CentOS-Base.repo https://mirrors.aliyun.com/repo/Centos-7.repo[rootlocalhost ~]#…...

编程日记 2025/5/23 22:52:38

python 曲线拟合，曲线拟合交点

目录效果图：源代码：效果图：源代码： import json import os import shutilimport cv2 import numpy as npfrom numpy.polynomial.polynomial import Polynomialdef calculate_distance(x1, y1, x2, y2):return np.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)def get_new_g…...

编程日记 2025/5/14 8:58:32

【2025最新计算机毕业设计】基于SSM框架的宠物领养系统【提供源码+答辩PPT+文档+项目部署】

作者简介：✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流。✌ 主要内容：🌟Java项目、Python项目、前端项目、PHP、ASP.NET、人工智能…...

编程日记 2025/5/22 20:12:55

C语言经典100例

文章目录前言123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525355565859606162636465 前言以下题目大部分来自于C语言经典100例 1 题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的…...

编程日记 2025/5/24 14:09:55

利用 Jsoup 进行高效 Web 抓取与 HTML 处理

Jsoup 是一款 Java 的 HTML 解析器，可直接解析某个 URL 地址、HTML 文本内容。它提供了一套非常省力的 API，可通过 DOM，CSS 以及类似于 JQuery 的操作方法来取出和操作数据。官网：https://jsoup.org/ 中文文档：Jsou…...

编程日记 2025/5/22 16:45:47

线上问题——频繁 Full GC 问题的排查思路

文章目录一、查看 GC 日志二、分析内存泄漏三、检查对象生命周期四、优化代码五、调整垃圾回收策略六、使用监控工具一、查看 GC 日志启用 GC 日志在 Java 应用中，需要在启动参数中添加适当的参数来启用 GC 日志记录。可以使用-XX:PrintGCDetails、-XX:PrintGCD…...

编程日记 2025/5/22 3:40:59

ParrotOS，一个与kali类似的渗透测试操作系统

介绍 Parrot Security（ParrotOS，Parrot）是一个基于 Debian Stable 的免费开源 GNU/Linux 发行版，专为安全专家、开发人员和注重隐私的人设计。它包括一个完整的便携式武器库，用于 IT 安全和数字取证操作。它还包括开…...

编程日记 2025/5/22 20:21:07

网络视频监控平台/安防监控/视频综合管理Liveweb视频汇聚平台解决方案

一、当前现状分析当前视频资源面临以下问题： 1）不同单位在视频平台建设中以所属领域为单位，设备品牌众多，存在的标准不一，各系统之间也没有统一标准； 2）各单位视频平台建设分散、统筹性差&am…...

编程日记 2025/5/22 8:29:54

《Java核心技术I》Swing选择组件中的复选框

选择组件除了输入，也需要选择组件，接下来介绍，复选框、单选按钮、选项列表以及滑块。复选框需要紧邻标签来说明其用途。 bold new JCheckBox("Bold"); 调用setSelected方法来选中或取消复选框 bold.setSelected(true); isSelec…...

编程日记 2025/5/25 8:29:18

ES6学习Generator 函数（生成器）(八)

这里写目录标题一、基本概念二、代码三、Generator 函数的异步应用三级目录一、基本概念 Generator 函数是 ES6 提供的一种异步编程解决方案，语法行为与传统函数完全不同，Generator 函数有多种理解角度。语法上，首先可以把它理解成&#x…...

编程日记 2025/5/26 5:08:23

练习题最小栈

最小栈最小栈 class MinStack {private Stack<Integer> stack;private Stack<Integer> minstack;public MinStack() {stacknew Stack<>();minstacknew Stack<>();}public void push(int val) {stack.push(val);if(minstack.empty()){minstack.push(…...

编程日记 2025/5/21 17:23:11

windows环境下pytorch安装踩坑

目录 1 前言2 安装Anaconda3 安装CUDA4 创建Python3.9环境5 安装Pytorch环境5.1 conda方式5.2 pip方式 6 验证是否安装成功7 注意事项7.1 no module named torch问题7.12 torch.cuda.is_available()返回False问题 8 最佳实践9 总结 1 前言这两天由于要使用Genesis，…...

编程日记 2025/5/25 12:33:13

从图纸泄密到全面安全防护 —— 域智盾软件在设计公司的应用

从图纸泄密到全面安全防护 —— 域智盾软件在设计公司的应用作为一家设计公司的老板，我深知设计图纸对公司来说有多么重要。每一份设计图纸不仅凝聚着我们团队的智慧和辛勤劳动，也代表着公司的技术创新和核心竞争力。然而，前段时间的一次…...

编程日记 2025/5/24 14:23:59

【ELK】Filebeat采集Docker容器日志

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录介绍filebeat是如何工作的使用部署filebeat 介绍 Filebeat 是一个用于转发和集中日志数据的轻量级传送器。 Filebeat 作为agent安装在服务器上，监视指…...

编程日记 2025/5/22 10:06:55

基于java web在线商城购物系统源码+论文

一、环境信息开发语言：JAVA JDK版本：JDK8及以上数据库：MySql5.6及以上 Maven版本：任意版本操作系统：Windows、macOS 开发工具：Idea、Eclipse、MyEclipse 开发框架：SpringbootHTMLjQueryMysq…...

编程日记 2025/5/22 13:33:03

MONI后台管理系统-swagger3(springdoc-openapi)集成

springdoc-openapi Java 库有助于使用 Spring Boot 项目自动生成 API 文档。springdoc-openapi 通过在运行时检查应用程序来根据 Spring 配置、类结构和各种注释推断 API 语义。该库会自动生成 JSON/YAML 和 HTML 格式的页面文档。生成的文档可以使用swagger-api注释进行补充。…...

编程日记 2025/5/21 23:51:02

常见八股文04

63.索引的优缺点优点 1.提高了查询性能 2.支持唯一性约束，避免插入重复数据 3.支持唯一性约束：在多表连接时，索引能够减少连接所需的时间和资源缺点 1.占用额外存储空间:特别是在大型数据表中，索引可能会占用大量的空间 …...

编程日记 2025/5/21 8:05:05

php各个版本的特性以及绕过方式

一.php各个版本的特性二.绕过正则匹配的常见方式 1.绕过空格 a.空变量$ l$s b.环境变量IFS（默认情况下IFS为空格、制表符和换行符） l${IFS}s c.重定向符（<,>） cat < file.txt //把file.txt的内容给cat命令&…...

编程日记 2025/5/26 6:04:07

允许某段网络访问Linux服务器上的MariaDB

在Linux服务器上安装了MariaDB，默认情况下，只允许本机访问。在某些特殊的情况下，要允许外部访问。具体操作流程如下： 1 修改服务器配置 vi /etc/my.cnf.d/server.cnf取消下面的注释，以便允许外来的主机访问。 bind-…...

编程日记 2025/5/25 1:46:50

【C语言】信号

【C语言】信号信号1. 信号状态2. 信号处理方式3. 信号注册相关函数4. 信号集相关函数信号 1. 信号状态信号有三种状态：产生、未决和递达信号产生方式： 按键产生，ctrlc 产生中断信号SIGINT，ctrl \ 产生退出信号 SIGQUIT并…...

编程日记 2025/5/24 10:41:01

2023年下半年软考信息安全工程师案例分析及答案解析

试题一（16分）回答问题1至问题6，将解答填入答题纸对应的解答栏内。问题1（4分）已知DES算法S盒如下，请补全S盒空缺的数据（1）、（2）、（3）、（4）。【参考答案】3、13、15、0 问题2（2分）已知S盒的输入为110011，请计算经过S盒变换之后的二进制输出。【参考…...

编程日记 2025/5/22 16:23:02

攻防世界easyphp

<?php highlight_file(__FILE__); $key1 0; $key2 0;$a $_GET[a]; $b $_GET[b];if(isset($a) && intval($a) > 6000000 && strlen($a) < 3){if(isset($b) && 8b184b substr(md5($b),-6,6)){$key1 1;}else{die("Emmm...再想想&quo…...

编程日记 2025/5/25 4:41:35

【WRF教程第3.6期】预处理系统 WPS 详解：以4.5版本为例

预处理系统 WPS 详解：以4.5版本为例 Geogrid/Metgrid 插值选项详解1. 插值方法的工作机制2. 插值方法的详细说明2.1 四点双线性插值（four_pt）2.2 十六点重叠抛物线插值（sixteen_pt）2.3 简单四点平均插值（av…...

编程日记 2025/5/26 4:30:30

图解HTTP-HTTP协议

HTTP HTTP是一种不保存状态，即无状态的协议。HTTP协议自身不对请求和响应之间的通信进行保存。为了保存状态因此后面也有一些技术产生比如Cookies技术。 HTTP是通过URI定位网上的资源，理论上将URI可以访问互联网上的任意资源。如果不是访问特定的资源…...

编程日记 2025/5/22 13:34:59

Linux基本命令

Linux基本命令一条Linux命令由：命令本身 [可选项] [参数] ls 展示 ls命令的选项: -a 选项，可以展示出隐藏的内容以 . 开头的文件或文件夹默认被隐藏，需要-a才能显示出来 **-l **选项,以列表的形式展示内容,并展示更多细节-h 选项&…...

编程日记 2025/5/23 19:34:07

【win10+RAGFlow+Ollama】搭建本地大模型助手（教程+源码）

一、RAGFlow简介 RAGFlow是一个基于对文档深入理解的开源RAG（Retrieval-augmented Generation，检索增强生成）引擎。主要作用： 让用户创建自有知识库，根据设定的参数对知识库中的文件进行切块处理，用户向大…...

编程日记 2025/5/22 10:29:11

.ejs 后缀文件 - 嵌入式JavaScript模板

嵌入式JavaScript模板（Embedded JavaScript templates）文件是以.ejs 后缀。它是一种模板引擎，它允许你在你的HTML文件中直接嵌入JavaScript代码。EJS模板可以包含HTML代码、JavaScript表达式、控制结构（如if语句和循环&#xff09…...

编程日记 2025/5/24 1:59:09