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

算法与数据结构之链表<一>(Java)

目录

1、链表的定义

2、链表的特点

3、为何要使用链表

4、数组与链表的区别

5、链表的增删查

5.1、在头部插入链表

5.2、在中间插入链表

5.3、删除头节点

5.4、删除中间节点

5.5、查询某个值

6、链表的应用

6.1 如何设计一个LRU缓存算法?

6.2 约瑟夫问题


1、链表的定义

链表通过指针将一组零散的内存块串联在一起。其中,我们把内存块称为”结点“。为了将所有的结点串起来,每个链表的结点除了存储数据之外,还需要记录链上的下一个结点的地址。

2、链表的特点

(1)不需要连续的内存空间
(2)有指针引用
(3)三种常见的链表结构:单链表、双链表、循环链表、(跳表:不常见但是功能强大,用到的地方也很多,比如redis,可以了解一下)
单链表: 第一个结点和最后一个结点分别为头结点和尾结点。头结点用来记录链表的基地址,有了它,我们就可以遍历得到整条链表。而尾结点的特殊地方是:指针不是指向下一个结点,而是指向一个空地址NULL,表示这是链表上的最后一个结点。
双向链表: 单向链表只有一个方向,结点只有一个后继指针next指向后面的结点。双向链表,顾名思义,它支持两个方向,每个结点不止有一个后继指针next指向后面的结点,还有一个前驱指针prev指向前面的结点。双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。缺点:如果存储同样多的数据,双向链表要比单链表占用更多的内存空间。优点:可以支持双向遍历,操作灵活(特别是对于范围查询有明显的优势、大于、小于)。实际应用:如 B+Tree(MySQL索引的叶子节点,采用的就是双向链表结构)
循环链表: 循环链表就是一种特殊的单链表。实际上,循环链表与单链表的唯一区别就是尾节点。单链表的尾节点指针指向空地址,表示这就是最后的结点了,而循环链表的尾结点指针是指向链表的头结点,形成一个环一样首尾相连的链表,所以"循环"链表。(约瑟夫问题)

3、为何要使用链表

稀疏数组:一般是针对多维数组
 1 2  4 -1
-1 3  5 -1
-1 1 -1 -1
a[3][4]:这是一个二维数组,-1表示存储的数据为空,已开空间大小3*4=12,稀疏数组就是真正存的数据远远小于我们开的空间,为了节省空间,往往会用链表代替。

4、数组与链表的区别

重要区别:
(1)数组简单易用,在实现上使用的是连续的内存空间,可以借助CPU的缓存机制(缓存行、缓存局部性),预读数组中的数据,所以访问效率更高。
(2)链表在内存中并不是连续存储,所以对CPU缓存不友好,没办法有效预读。
(3)数组的缺点就是大小固定,一经声明就要占用整块连续内存空间。如果声明的数组过大,系统可能没有足够的连续内存空间分配给它,导致"内存不足(Out Of Memory)"。如果声明的数组过小,则可能出现不够用的情况。
(4)动态扩容:数组需再申请一个更大的内存空间,把原数组拷贝过去,非常费时。链表本身没有大小限制,天然支持动态扩容。(但是链表不断的扩容会把内存撑爆,使用时需要注意)

5、链表的增删查

单向链表结构:头结点,指针(指向下一节点),value(存储的值),size已存储值的数量
    public class MyLinkedList {private int size;ListNode head;class ListNode { //定义链表结构int value;ListNode next;ListNode(int value) { //构造函数,用于构造一个结点this.value = value;this.next = null;head = null;}}}

5.1、在头部插入链表

    private void insertHead(int data) {//时间复杂度O(1)ListNode newData = new ListNode(data);//构造一个结点newData.next = head; //栈内存的引用head = newData;size++;}

5.2、在中间插入链表

 private void insertNth(int data, int position) {//插入链表的中间,假设定义在第N个插入,O(n)if (position == 0){//这里表示插入在头部insertHead(data);} else {ListNode newData = new ListNode(data);ListNode curr = head;for (int i=0; i< position; i++){curr = curr.next;//一直往后遍历,找到要插入的位置,c/c++的 p=p->next;}//确保链表不会断裂丢失数据newData.next = curr.next;//先将新加的结点指向后面,保证不断链curr.next = newData;//把当前的点指向新加的点}size++;}

5.3、删除头节点

    private void deleteHead(int data) {//O(1)head = head.next;size--;}

5.4、删除中间节点

   private void deleteNth(int data, int position) {//O(1)if (position == 0){deleteHead(data);} else {ListNode curr = head;for (int i=0; i< position; i++){curr = curr.next;}curr.next = curr.next.next;//curr.next 表示的是删除的点}size--;}

5.5、查询某个值

    public void find(int data){//O(n)ListNode cur = head;while(cur != null){//判断不是尾结点if(cur.value == data) break;//找到后退出循环cur = cur.next;//遍历下一个结点}}

6、链表的应用

6.1 如何设计一个LRU缓存算法?

LRU(Least Recently Used:最近最少使用,它主要思想是当缓存空间占满时,移除最近最少使用的缓存对象)
    /*** 1、先判断链表中是否已存在该data,如果已存在则抛弃旧的值,然后在head插入新的值* 2、如果不存在改data,则直接在head插入该data,保证head为最新访问的值* 这里实现的是简单的lru,深层次的lru可使用哈希表+双向链表实现(可参考力扣的题目)* @param data*/private void lru (int data) {ListNode newData = new ListNode(data);ListNode curr = head;while (curr.next != null) {if (curr.value == data){//删除该结点curr.next = curr.next.next;break;}curr = curr.next;}//插入链表头部head = newData.next;}

6.2 约瑟夫问题

读者可以先思考此问题的实现,该问题的求解过程小编会在另一篇博文解答,敬请期待!!

相关文章:

算法与数据结构之链表<一>(Java)

目录 1、链表的定义 2、链表的特点 3、为何要使用链表 4、数组与链表的区别 5、链表的增删查 5.1、在头部插入链表 5.2、在中间插入链表 5.3、删除头节点 5.4、删除中间节点 5.5、查询某个值 6、链表的应用 6.1 如何设计一个LRU缓存算法&#xff1f; 6.2 约瑟夫问题 1、链表的定…...

目标检测COCO数据集与评价体系mAP

1.mAP 2.IoU IoU也就是交并比&#xff0c;也称为 Jaccard 指数&#xff0c;用于计算真实边界框与预测边界框之间的重叠程度。它是真值框与预测边界框的交集和并集之间的比值。Ground Truth边界框是测试集中手工标记的边界框&#xff0c;用于指定对象图像的位置以及预测的边界框…...

2024最全面且有知识深度的web3开发工具、web3学习项目资源平台

在Web3技术迅速发展的时代&#xff0c;寻找一个综合且深入的Web3开发工具和学习项目资源平台变得至关重要。今天&#xff0c;我将向大家介绍一个非常有价值的网站&#xff0c;它就是https://web3x.world 。 Web3X是一个全面而深入的Web3开发者社区&#xff0c;为开发者们提供了…...

Golang - defer关键字 深入剖析

defer关键字 defer和go一样都是Go语言提供的关键字。defer用于资源的释放&#xff0c;会在函数返回之前进行调用。一般采用如下模式&#xff1a; f,err : os.Open(filename) if err ! nil {panic(err) } defer f.Close()如果有多个defer表达式&#xff0c;调用顺序类似于栈&a…...

如何在Spring Boot中使用@Scheduled写定时任务判断数据量是否过大,过大则进行分表操作,多张表使用临时视图查询

当数据量过大&#xff0c;在定时任务中执行分表操作 1、复制表结构及数据 在xml中编写复制表结构及数据&#xff08;newTableName为新表名、originalTableName为原始表名&#xff09; 只复制表结构&#xff1a; CREATE TABLE ${newTableName} AS SELECT * FROM ${originalTa…...

使用jieba库进行中文分词和去除停用词

jieba.lcut jieba.lcut()和jieba.lcut_for_search()是jieba库中的两个分词函数&#xff0c;它们的功能和参数略有不同。 jieba.lcut()方法接受三个参数&#xff1a;需要分词的字符串&#xff0c;是否使用全模式&#xff08;默认为False&#xff09;以及是否使用HMM模型&…...

C语言之分支与循环【附6个练习】

文章目录 前言一、什么是语句&#xff1f;1.1 表达式语句1.2 函数调用语句1.3 控制语句1.4 复合语句1.5 空语句 二、分支语句&#xff08;选择结构&#xff09;2.1 if语句2.1.1 悬空else2.1.2 练习&#xff08;1. 判断一个数是否为奇数 2. 输出1-100之间的奇数&#xff09; 2.2…...

使用通用MCU实现无人机飞行任务的快速二次开发

使用通用MCU实现无人机飞行任务的快速二次开发 ---TIDronePilot外部控制offboard模式介绍 无名小哥 2024年1月1日 传统飞控二次开发方法和主要存在的问题简介 通过对前面几讲中《零基础竞赛无人机积木式编程指南》系列开发教程的学习可知&#xff0c;在以往TI电赛真题的学习…...

什么是Selinux

官网地址&#xff1a;What is SELinux? 欢迎关注留言&#xff0c;我是收集整理小能手&#xff0c;工具翻译&#xff0c;仅供参考&#xff0c;笔芯笔芯. 概述 安全增强型 Linux (SELinux) 是Linux 系统的安全架构&#xff0c;允许管理员更好地控制谁可以访问系统。它最初是由美…...

计算机网络知识点

1. URI 和 URL 统一资源定位符&#xff08;Uniform Resource Locator&#xff0c;缩写&#xff1a;URL&#xff09;&#xff0c;是对资源的引用和访问该资源的方法。俗称网址&#xff0c;就是浏览器地址栏里面的内容。 URL 语法为&#xff1a;protocol://userInfohost:port/p…...

Qt 连接 Mysql

Linux下安装mysql及qt连接_liunx下安装mysql及qt链接-CSDN博客...

HarmonyOS4.0系统性深入开发14AbilityStage组件容器

AbilityStage组件容器 AbilityStage是一个Module级别的组件容器&#xff0c;应用的HAP在首次加载时会创建一个AbilityStage实例&#xff0c;可以对该Module进行初始化等操作。 AbilityStage与Module一一对应&#xff0c;即一个Module拥有一个AbilityStage。 DevEco Studio默…...

客服系统接入FastGPT

接入FastGPT 点击【应用】【外部使用】【API访问】【新建】新建一个KEY&#xff0c;同时也可以看到我们的API根地址 这个根地址和Key可以填入任何支持OpenAI接口的应用里&#xff0c;这个接口是兼容OpenAI格式。 在客服系统【知识库AI配置】里填上接口地址和接口密钥。这样我…...

Hi5 2.0 虚拟手与追踪器(Tracker)的位置修正

问题描述 使用环境与工具&#xff1a;Unity 2022.3.4fc1&#xff0c;steam VR(2.7.3)&#xff0c;steamvrSDK&#xff08;1.14.15&#xff09;&#xff0c;HTC vive pro专业版&#xff0c;Hi5 2.0数据手套 首先按照Hi5 2.0的使用说明&#xff08;可参考&#xff1a;HI5 2.0 交…...

广播及代码实现

广播&#xff08;Broadcast&#xff09;是一种网络通信方式&#xff0c;它允许一台设备向网络中的所有其他设备发送消息。广播通常用于在网络上传递一些信息&#xff0c;让所有设备都能接收并处理。在广播中&#xff0c;通信的目标是整个网络而不是特定的单个设备。 向子网中…...

QT应用篇 三、QML自定义显示SpinBox的加减按键图片及显示值效果

QT应用篇 一、QT上位机串口编程 二、QML用Image组件实现Progress Bar 的效果 三、QML自定义显示SpinBox的加减按键图片及显示值效果 文章目录 QT应用篇前言一、qml需求二、使用组件1.SpinBox组件2.SpinBox中QML的使用 总结 前言 记录自己学习QML的一些小技巧方便日后查找 QT的…...

2022年全国职业院校技能大赛网络安全竞赛试题1-10-B模块总结

前言 结尾有对22年国赛题型总结 试题1模块B 网络安全事件响应、数字取证调查和应用安全 B-1任务一&#xff1a;主机发现与信息收集 *任务说明&#xff1a;仅能获取Server1的IP地址 1.通过渗透机Kali2.0对靶机场景进行TCP同步扫描 (使用Nmap工具)&#xff0c;并将该操作使用…...

20231228在Firefly的AIO-3399J开发板的Android11的Firefly的AIO-3399J开发板的DTS配置单前置摄像头ov13850

20231228在Firefly的AIO-3399J开发板的Android11的Firefly的AIO-3399J开发板的DTS配置单前置摄像头ov13850 2023/12/28 12:30 开发板&#xff1a;Firefly的AIO-3399J【RK3399】 SDK&#xff1a;rk3399-android-11-r20211216.tar.xz【Android11】 Android11.0.tar.bz2.aa【ToyBr…...

php-fpm运行一段时间,内存不足

目录 一&#xff1a;原因分析 二&#xff1a;解决 三:观察系统情况 php-fpm运行一段时间&#xff0c;内存不足&#xff0c;是什么原因呢。 一&#xff1a;原因分析 1:首先php-fpm的配置 &#xff08;1&#xff09;启动的进程数 启动的进程数越多,占用内存越高; 2:其次…...

基于轻量级GhostNet模型开发构建生活场景下生活垃圾图像识别系统

轻量级识别模型在我们前面的博文中已经有过很多实践了&#xff0c;感兴趣的话可以自行移步阅读&#xff1a; 《移动端轻量级模型开发谁更胜一筹&#xff0c;efficientnet、mobilenetv2、mobilenetv3、ghostnet、mnasnet、shufflenetv2驾驶危险行为识别模型对比开发测试》 《基…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

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

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

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...