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

链表(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

上期内容我们讲述了顺序表&#xff0c;知道了顺序表的底层是一段连续的空间进行存储(数组)&#xff0c;在插入元素或者删除元素需要将顺序表中的元素整体移动&#xff0c;时间复杂度是O(n)&#xff0c;效率比较低。因此&#xff0c;在Java的集合结构中又引入了链表来解决这一问…...

Qt:Qt Creator项目创建

目录 认识Qt Creator Qt Creator概览 使用Qt Creator新建项目 选择项目模板 选择项目路径 选择构建系统 填写类信息设置界面 选择语言和翻译文件 选择Qt套件 选择版本控制系统 最终效果 认识Qt Creator Qt Creator概览 从开始菜单或者快捷方式打开Qt Creator集成开…...

windows11上,使用pipx安装Poetry,Poetry的安装路径是什么?

当使用 pipx 安装 Poetry 时&#xff0c;pipx 会将 Poetry 安装到一个独立的虚拟环境中&#xff0c;并将其可执行文件链接到一个集中的目录中。以下是 pipx 安装 Poetry 时的路径信息&#xff1a; 1. Poetry 的安装路径 pipx 会为每个工具&#xff08;如 Poetry&#xff09;创…...

详解状态模式

引言 水有固态、液态、气态三种状态&#xff0c;在不同条件下这三种状态可以相互转化。同样在软件设计中&#xff0c;有些对象也有不同的状态&#xff0c;不同状态的行为不同&#xff0c;状态模式就是用来处理这种情况的。 1.概念 状态模式(State Pattern)&#xff1a;允许一个…...

能否通过蓝牙建立TCP/IP连接来传输数据

前言&#xff1a; 最近在做一个项目时&#xff0c;产生了一个疑问&#xff1a;能否通过蓝牙建立TCP/IP连接来传输数据 查阅了一些文章&#xff0c;可以得出结论&#xff1a;不行 下面是我截取的两篇个人认可的文章的回答&#xff1a; 文章一&#xff1a; 蓝牙是一种短距离无…...

uniapp mqttjs 小程序开发

在UniApp中集成MQTT.js开发微信小程序时&#xff0c;需注意平台差异、协议兼容性及消息处理等问题。以下是关键步骤与注意事项的综合指南&#xff1a; 一、环境配置与依赖安装 安装MQTT.js 推荐使用兼容性较好的版本&#xff1a;mqtt4.1.0&#xff08;H5和小程序兼容性最佳&…...

爬虫工程师分享:获取京东商品详情SKU数据的技术难点与攻破方法

在电商数据领域&#xff0c;京东商品详情页的SKU数据是许多爬虫工程师的目标。这些数据包含了商品的价格、库存、规格等关键信息&#xff0c;对于市场分析、价格监控等应用场景至关重要。然而&#xff0c;获取这些数据并非易事&#xff0c;京东作为国内电商巨头&#xff0c;其反…...

数据库操作与数据管理——Rust 与 SQLite 的集成

第六章&#xff1a;数据库操作与数据管理 第一节&#xff1a;Rust 与 SQLite 的集成 在本节中&#xff0c;我们将深入探讨如何在 Rust 中使用 SQLite 数据库&#xff0c;涵盖从基本的 CRUD 操作到事务处理、数据模型的构建、性能优化以及安全性考虑等方面。SQLite 是一个轻量…...

LeetCode 0063.不同路径 II:动态规划 - 原地使用地图数组,几乎无额外空间开销

【LetMeFly】63.不同路径 II&#xff1a;动态规划 - 原地使用地图数组&#xff0c;几乎无额外空间开销 力扣题目链接&#xff1a;https://leetcode.cn/problems/unique-paths-ii/ 给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角&#xff08;即 grid[0][0]&#…...

elementui:el-table支持搜索、切换分页多选功能,以及数据回显

1、el-table相关代码&#xff0c;需注意: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踩坑记录

前置条件&#xff1a;电脑显卡RTX 4080 问题&#xff1a;LLaMA-Factory在运行的时候&#xff0c;弹出未检测到CUDA的报错信息 结论&#xff1a;出现了以上的报错&#xff0c;主要可以归结于以下两个方面&#xff1a; 1、没有安装GPU版本的pytorch&#xff0c;下载的是CPU版本…...

亚博microros小车-原生ubuntu支持系列:25 二维码控制运动

二维码识别 安装依赖 pip3 install pyzbarsudo apt install libzbar-dev 在用小车识别之前&#xff0c;先用电脑的摄像头测试下基本的识别 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使用

说明&#xff1a;本文介绍Spring Boot Actuator的使用&#xff0c;关于Spring Boot Actuator介绍&#xff0c;下面这篇博客写得很好&#xff0c;珠玉在前&#xff0c;我就不多介绍了。 Spring Boot Actuator 简单使用 项目里引入下面这个依赖 <!--Spring Boot Actuator依…...

【AI应用】免费的文本转语音工具:微软 Edge TTS 和 开源版 ChatTTS 对比

【AI论文解读】【AI知识点】【AI小项目】【AI战略思考】【AI日记】【读书与思考】【AI应用】 我试用了下Edge TTS&#xff0c;感觉还不错&#xff0c;不过它不支持克隆声音&#xff08;比如自己的声音&#xff09; 微软 Edge TTS 和 开源版 ChatTTS 都是免费的 文本转语音&…...

如何在 Qt 中添加和使用系统托盘图标

在 Qt 中实现系统托盘图标是一个常见的需求&#xff0c;尤其是在桌面应用程序中。系统托盘图标可以让应用程序在后台运行时仍然具有可见性&#xff0c;同时避免占用过多的桌面空间。本文将详细介绍如何在 Qt 项目中添加托盘图标&#xff0c;并通过资源系统&#xff08;.qrc 文件…...

【WB 深度学习实验管理】利用 Hugging Face 实现高效的自然语言处理实验跟踪与可视化

本文使用到的 Jupyter Notebook 可在GitHub仓库002文件夹找到&#xff0c;别忘了给仓库点个小心心~~~ https://github.com/LFF8888/FF-Studio-Resources 在自然语言处理领域&#xff0c;使用Hugging Face的Transformers库进行模型训练已经成为主流。然而&#xff0c;随着模型复…...

基础入门-网站协议身份鉴权OAuth2安全Token令牌JWT值Authirization标头

知识点&#xff1a; 1、网站协议-http/https安全差异&#xff08;抓包&#xff09; 2、身份鉴权-HTTP头&OAuth2&JWT&Token 一、演示案例-网站协议-http&https-安全测试差异性 1、加密方式 HTTP&#xff1a;使用明文传输&#xff0c;数据在传输过程中可以被…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...