链表(LinkedList) 1
上期内容我们讲述了顺序表,知道了顺序表的底层是一段连续的空间进行存储(数组),在插入元素或者删除元素需要将顺序表中的元素整体移动,时间复杂度是O(n),效率比较低。因此,在Java的集合结构中又引入了链表来解决这一问题。
1、链表
如上图所示是单向链表节点的两个元素:其中value存储着节点的值,next存储着下一个节点的地址。因此,一个单向链表可以表示为下图所示:

注意 :
1、从上图可以看出,链式结构在逻辑上是连续的,但在物理上(即在计算机的内存里面)不一定连续。
2、 现实中的节点一般是从堆上申请出来的。
3、从堆上申请的空间,是按照一定策略来分配的,两次申请的空间可能连续,也可能不连续。
2、链表结构
链表组合起来的结构一共有8种,通过以下情况进行排列组合:
2.1 单向或者双向
单向
双向

双向链表在next域的基础上增加了prev域,使得通过链表的一个节点不仅能访问后继元素,也能访问前驱元素 。
2.2 带头或者不带头
带头

注意:这里的头并没有实际的值,主要用它链接后续的节点,因此,head指向第一个元素的地址。
不带头

2.3 循环或者非循环
循环
非循环
这里我们重点讲单向不带头非循环链表和双向不带头非循环链表。
3、无头单向非循环链表实现
3.1 节点的实现
链表的节点主要通过静态内部类进行实现。代码如下:
static class ListNode{public int val;//节点的值域public ListNode next;//下一个节点的地址public ListNode() {}public ListNode(int val) {this.val = val;}}public ListNode head;//表示当前链表的头结点
这里可能有人会有疑问:为什么不把头结点的声明放入内部类中呢?
其实,从逻辑上想,不难想明白:头结点是属于整个链表的头结点,而非结点的头结点。
3.2 creatNode方法
本方法用于初始化一个链表。
public void creatNode(){ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(34);ListNode node4 = new ListNode(45);ListNode node5 = new ListNode(56);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}
3.3 头插法
故名思义:就是在链表的头部插入。这里有个点需要注意:先插入的数据会最后输出,后插入的最先输出。
在头部插入一个元素,我们需要先绑定元素后面的信息,再让我们的头结点指向我们要插入的元素。代码如下:
//头插法public void addFirst(int data){ListNode node = new ListNode(data);//一般建议在插入的时候先绑定后面的节点信息node.next = head;this.head = node;}
3.4 尾插法
在尾部插入一个元素,需要先绑定前面的元素的信息,即让最后一个元素的next指向要插入的元素。
注意:如果链表中没有元素,则直接让头结点指向要插入的元素。
//尾插法public void addLast(int data){ListNode cur = head;ListNode node = new ListNode(data);if(cur == null){//如果链表中没有元素,那么让头结点指向nodehead = node;return;}//当cur.next == null的时候,那么该节点就是尾巴节点//当cur == null证明该链表已经被遍历完了while (cur.next != null){cur = cur.next;}cur.next = node;}
3.5 任意位置插入,第一个数据节点为0号下标
在任意位置插入,首先,我们要判定下标是否合法,若不合法则抛出异常。第二步,如果插入的下标为0,则直接调用前面写的头插法函数,如果下标等于链表的长度,则调用尾插法函数。第三步,如果插入的地方是在中间,则需要先找到要插入结点的前一个结点,绑定后面的信息后再进行插入。
//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){if(index < 0 || index > size()){throw new IndexErrorException("下标不合法");}if(index == 0){addFirst(data);return;}else if (index == size()){addLast(data);return;}//1、定义cur走index-1步//2、进行插入ListNode node = new ListNode(data);ListNode cur = head;int count = 0;while(count != index-1){cur = cur.next;count++;}node.next = cur.next;cur.next = node;}
3.6 查找关键字key是否在单链表当中
查找关键字key只需要遍历链表,看结点的value是否等于key就ok了。
//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur = head;while (cur != null){if(cur.val == key){return true;}cur = cur.next;}return false;}
3.7 删除第一次出现关键字key的元素
思路:删除一个结点(del),我们需要记录被删除结点的前一个结点(cur),再让前一个结点的next域(cur.next)指向被删除结点的下一个结点(del.next)。需要注意的是:在这个过程之前需要单独删除头结点。
//删除第一次出现关键字为key的节点public void remove(int key){if(head == null){return;}//单独删除头结点if(head.val == key){head = head.next;return;}//找到删除节点的前一个结点ListNode cur = head;while (cur.next != null){ListNode del = cur.next;if(del.val == key){//此时cur指向的节点就是要删除节点的前一个节点//cur.next = cur.next.nextcur.next = del.next;return;//删除之后返回}cur = cur.next;}if(cur==null){System.out.println("没有你要删除的数字");}}
3.8 删除所有值为key的节点
删除所有值为key的结点需要用到双指针的思想(ps:因为需要不断地记录被删除结点的前一个结点), prev指针用来找到被删除元素的前一个元素,cur指针则用来遍历链表和找到被删除元素。删除的过程就是直接让prev的next域直接指向cur指针的next域,再让cur指针向后走;若不是被删除的元素则直接让两个指针一起往后走。最后,我们需要单独删除头结点。(注意:这里我们在最后才删除头结点是因为前面的cur和prev指针需要使用到头结点)。
//删除所有值为key的节点
public void removeAllKey(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;}}
3.9 得到单链表长度
得到单链表的长度,我们需要定义一个计数器,然后遍历链表让count++就行了。
//得到单链表的长度public int size(){int count = 0;ListNode cur = head;while(cur != null){count++;cur = cur.next;}return count;}
3.10 清空链表
遍历链表将链表的每个结点置空即可。
//清空链表
public void clear() {ListNode cur = head;while (cur != null){cur = null;cur = cur.next;}}
3.11 打印链表
遍历链表,打印每个结点的value域即可。
//打印链表public void display() {ListNode cur = head;while (cur!= null){//如果cur==null证明把链表遍历完成了System.out.print(cur.val + " ");cur = cur.next;//cur每次都在向后走一步
}System.out.println();}
相关文章:
链表(LinkedList) 1
上期内容我们讲述了顺序表,知道了顺序表的底层是一段连续的空间进行存储(数组),在插入元素或者删除元素需要将顺序表中的元素整体移动,时间复杂度是O(n),效率比较低。因此,在Java的集合结构中又引入了链表来解决这一问…...
Qt:Qt Creator项目创建
目录 认识Qt Creator Qt Creator概览 使用Qt Creator新建项目 选择项目模板 选择项目路径 选择构建系统 填写类信息设置界面 选择语言和翻译文件 选择Qt套件 选择版本控制系统 最终效果 认识Qt Creator Qt Creator概览 从开始菜单或者快捷方式打开Qt Creator集成开…...
windows11上,使用pipx安装Poetry,Poetry的安装路径是什么?
当使用 pipx 安装 Poetry 时,pipx 会将 Poetry 安装到一个独立的虚拟环境中,并将其可执行文件链接到一个集中的目录中。以下是 pipx 安装 Poetry 时的路径信息: 1. Poetry 的安装路径 pipx 会为每个工具(如 Poetry)创…...
详解状态模式
引言 水有固态、液态、气态三种状态,在不同条件下这三种状态可以相互转化。同样在软件设计中,有些对象也有不同的状态,不同状态的行为不同,状态模式就是用来处理这种情况的。 1.概念 状态模式(State Pattern):允许一个…...
能否通过蓝牙建立TCP/IP连接来传输数据
前言: 最近在做一个项目时,产生了一个疑问:能否通过蓝牙建立TCP/IP连接来传输数据 查阅了一些文章,可以得出结论:不行 下面是我截取的两篇个人认可的文章的回答: 文章一: 蓝牙是一种短距离无…...
uniapp mqttjs 小程序开发
在UniApp中集成MQTT.js开发微信小程序时,需注意平台差异、协议兼容性及消息处理等问题。以下是关键步骤与注意事项的综合指南: 一、环境配置与依赖安装 安装MQTT.js 推荐使用兼容性较好的版本:mqtt4.1.0(H5和小程序兼容性最佳&…...
爬虫工程师分享:获取京东商品详情SKU数据的技术难点与攻破方法
在电商数据领域,京东商品详情页的SKU数据是许多爬虫工程师的目标。这些数据包含了商品的价格、库存、规格等关键信息,对于市场分析、价格监控等应用场景至关重要。然而,获取这些数据并非易事,京东作为国内电商巨头,其反…...
数据库操作与数据管理——Rust 与 SQLite 的集成
第六章:数据库操作与数据管理 第一节:Rust 与 SQLite 的集成 在本节中,我们将深入探讨如何在 Rust 中使用 SQLite 数据库,涵盖从基本的 CRUD 操作到事务处理、数据模型的构建、性能优化以及安全性考虑等方面。SQLite 是一个轻量…...
LeetCode 0063.不同路径 II:动态规划 - 原地使用地图数组,几乎无额外空间开销
【LetMeFly】63.不同路径 II:动态规划 - 原地使用地图数组,几乎无额外空间开销 力扣题目链接:https://leetcode.cn/problems/unique-paths-ii/ 给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角(即 grid[0][0]&#…...
elementui:el-table支持搜索、切换分页多选功能,以及数据回显
1、el-table相关代码,需注意:row-key"(row) > { return row.id }" 以及 :reserve-selection"true" <div class"boxList"><div class"search-form"><!-- 搜索表单 --><el-form :inline"true&q…...
深度整理总结MySQL——索引正确使用姿势
索引正确使用姿势 前言MySQL索引优缺点分析✅ 索引的优势⚠️ 索引的代价 如何合理建立索引?——关键原则总结重要的优化机制索引覆盖——通俗的方式讲解索引下推索引跳跃式扫描 前言 这篇文章是补充一些基本概念和实战的一些使用建议. MySQL索引优缺点分析 ✅ 索引的优势 …...
使用LLaMA Factory踩坑记录
前置条件:电脑显卡RTX 4080 问题:LLaMA-Factory在运行的时候,弹出未检测到CUDA的报错信息 结论:出现了以上的报错,主要可以归结于以下两个方面: 1、没有安装GPU版本的pytorch,下载的是CPU版本…...
亚博microros小车-原生ubuntu支持系列:25 二维码控制运动
二维码识别 安装依赖 pip3 install pyzbarsudo apt install libzbar-dev 在用小车识别之前,先用电脑的摄像头测试下基本的识别 import cv2 import rclpy from rclpy.node import Node import pyzbar.pyzbar as pyzbar import numpy as np from ament_index_pyth…...
基于深度学习的人工智能量化衰老模型构建与全流程应用研究
一、引言 1.1 研究背景与意义 1.1.1 人口老龄化现状与挑战 人口老龄化是当今全球面临的重要社会趋势之一,其发展态势迅猛且影响深远。根据联合国的相关数据,1980 年,全球 65 岁及以上人口数量仅为 2.6 亿,到 2021 年,这一数字已翻番,达到 7.61 亿,而预计到 2050 年,…...
【医院运营统计专题】2.运营统计:医院管理的“智慧大脑”
医院成本核算、绩效管理、运营统计、内部控制、管理会计专题索引 引言 在当今医疗行业快速发展的背景下,医院运营管理的科学性和有效性成为了决定医院竞争力和可持续发展能力的关键因素。运营统计作为医院管理的重要工具,通过对医院各类数据的收集、整理、分析和解读,为医…...
Spring Boot Actuator使用
说明:本文介绍Spring Boot Actuator的使用,关于Spring Boot Actuator介绍,下面这篇博客写得很好,珠玉在前,我就不多介绍了。 Spring Boot Actuator 简单使用 项目里引入下面这个依赖 <!--Spring Boot Actuator依…...
【AI应用】免费的文本转语音工具:微软 Edge TTS 和 开源版 ChatTTS 对比
【AI论文解读】【AI知识点】【AI小项目】【AI战略思考】【AI日记】【读书与思考】【AI应用】 我试用了下Edge TTS,感觉还不错,不过它不支持克隆声音(比如自己的声音) 微软 Edge TTS 和 开源版 ChatTTS 都是免费的 文本转语音&…...
如何在 Qt 中添加和使用系统托盘图标
在 Qt 中实现系统托盘图标是一个常见的需求,尤其是在桌面应用程序中。系统托盘图标可以让应用程序在后台运行时仍然具有可见性,同时避免占用过多的桌面空间。本文将详细介绍如何在 Qt 项目中添加托盘图标,并通过资源系统(.qrc 文件…...
【WB 深度学习实验管理】利用 Hugging Face 实现高效的自然语言处理实验跟踪与可视化
本文使用到的 Jupyter Notebook 可在GitHub仓库002文件夹找到,别忘了给仓库点个小心心~~~ https://github.com/LFF8888/FF-Studio-Resources 在自然语言处理领域,使用Hugging Face的Transformers库进行模型训练已经成为主流。然而,随着模型复…...
基础入门-网站协议身份鉴权OAuth2安全Token令牌JWT值Authirization标头
知识点: 1、网站协议-http/https安全差异(抓包) 2、身份鉴权-HTTP头&OAuth2&JWT&Token 一、演示案例-网站协议-http&https-安全测试差异性 1、加密方式 HTTP:使用明文传输,数据在传输过程中可以被…...
UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...


