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

【4】单链表(有虚拟头节点)

【4】单链表(有虚拟头节点)

  • 1、虚拟头节点
  • 2、构造方法
  • 3、node(int index) 返回索引位置的节点
  • 4、添加
  • 5、删除
  • 6、ArrayList 复杂度分析
    • (1) 复杂度分析
    • (2) 数组的随机访问
    • (3) 动态数组 add(E element) 复杂度分析
    • (4) 动态数组的缩容
    • (5) 复杂度震荡
  • 7、单链表复杂度分析
  • 8、完整代码

1、虚拟头节点

📕 为了让代码更精简,统一所有节点的处理逻辑,可以在最前面增加一个虚拟头节点

🖊 头指针指向的永远是虚拟头节点
🖊 虚拟头节点不存储数据

在这里插入图片描述

2、构造方法

📕 在 单链表 代码的基础上需要进行修改

🖊 头指针 first 永远指向虚拟头节点,所以在 VirtualHeadLinkedList 的构造方法中要让 first 指针虚拟头节点

    public VirtualHeadLinkedList() {// 头指针指向虚拟头节点// 虚拟头节点的next默认指向nullfirst = new Node<>(null, null);}

3、node(int index) 返回索引位置的节点

🖊 该方法会返回索引位置的节点,它原本的实现思路是:若需要 index 位置的节点,则从 first 头指针指向的头节点开始 next index

🖊 加入了虚拟头节点后,就不能从 first 头指针指向的头节点开始 next index 次了,而是从虚拟头节点next 指向的节点开始 next

    /*** 返回index索引处的节点*/private Node<E> node(int index) {checkIndex(index);// first头指针指向的是虚拟头节点// first.next就是具体存储数据的第一个节点Node<E> node = first.next;for (int i = 0; i < index; i++) {node = node.next;}return node;}

4、添加

🖊 之前的添加逻辑:
① 假如是往头节点位置添加元素:first 指向新节点,新节点的 next 指向之前的头节点
② 若不是往头节点位置添加元素:找到 index-1 索引处的节点 prev,然后新节点的 next 指向 prev.next,然后 prev.next 指向新节点

🖊 增加虚拟头节点后: 如果 index == 0prev 就是虚拟头节点(first)

    /*** 往索引位置添加元素*/@Overridepublic void add(int index, E element) {checkIndex4Add(index);// 如果index==0, prev是虚拟头节点Node<E> prev = (index == 0) ? first : node(index - 1);prev.next = new Node<>(element, prev.next);size++;}

5、删除

🖊 假如删除的是 index == 0 位置的节点,则 prev 就是虚拟头节点

    /*** 删除索引位置的元素** @return 被删除的元素*/@Overridepublic E remove(int index) {checkIndex(index);Node<E> prev = (index == 0) ? first : node(index - 1);Node<E> node = prev.next;prev.next = node.next;size--;return node.element;}

6、ArrayList 复杂度分析

(1) 复杂度分析

最好情况复杂度
最坏情况复杂度
平均情况复杂度

方法复杂度
getO(1)
setO(1)
add① 最好:O(1)
② 最坏:O(n)
③ 平均:O(n)
remove① 最好:O(1)
② 最坏:O(n)
③ 平均:O(n)

📕 add
🖊 假如 index == size(往最后面添加元素):无需挪动元素(时间复杂度是 O(1)最好时间复杂度
🖊 假如 index == 0:整个数组需要往后挪动(时间复杂度是 O(n)最坏时间复杂度
🖊 平均时间复杂度:(1 + 2 + ... + n) / n = n/2挪动1次、2次、...、 n次

(2) 数组的随机访问

在这里插入图片描述

🖊 数组的随机访问速度非常快
🖊 elements[n] 的效率与 n 是多少无关

📕 假设存放的是 int 类型的元素(每个元素的地址相差四个字节):
🖊 地址值 = index * 4 + 数组首元素的地址

(3) 动态数组 add(E element) 复杂度分析

◼ 最好:O(1)
◼ 最坏:O(n)
◼ 平均:O(1)
◼ 均摊:O(1)

🖊 add(E element) 永远是往数组的最后面添加元素,可能会有扩容的情况产生
🖊 扩容的时间复杂度是 O(n)在这里插入图片描述
🖊 但是该方法大部分情况下的时间复杂度都是 O(1),只有极少数情况是O(n)【均摊复杂度】

📕 什么情况下适合使用均摊复杂度❓
🖊经过连续的多次复杂度比较低的情况后,出现个别复杂度比较高的情况

在这里插入图片描述

(4) 动态数组的缩容

📕 如果内存使用比较紧张,动态数组有比较多的剩余空间,可以考虑进行缩容操作
🖊 比如剩余空间占总容量的一半时,就进行缩容

  /*** 缩容*/private void trim() {// 当前容量:elements数组最多可以存储的元素个数int curCap = elements.length;int newCap = curCap >> 1;if (size >= newCap || newCap <= DEFAULT_CAPACITY) return; // 不缩容E[] newElements = (E[]) new Object[newCap];// 把旧数组元素复制到新数组中for (int i = 0; i < size; i++) {newElements[i] = elements[i];}elements = newElements;System.out.println("🖊缩容:" + curCap + "→" + newCap);}

(5) 复杂度震荡

📕 如果扩容倍数、缩容时机设计不得当,有可能会导致复杂度震荡
在这里插入图片描述

🖊 上图假如一直执行增、删、增、删、增、删…操作的话,就会出现扩容、缩容、扩容、缩容、扩容、缩容…的情况
🖊 出现此情况是因为:扩容为2倍(2)和剩余空间大于等于总容量一半(1/2)的时候缩容【扩容倍数和缩容时机的乘积不要等于1】

7、单链表复杂度分析

方法复杂度
get① 最好:O(1)
② 最坏:O(n)
③ 平均:O(n)
set① 最好:O(1)
② 最坏:O(n)
③ 平均:O(n)
add① 最好:O(1)
② 最坏:O(n)
③ 平均:O(n)
remove① 最好:O(1)
② 最坏:O(n)
③ 平均:O(n)

🖊 单链表效率比较低主要是因为 node(int index) 方法,它有 for 循环(数据规模可能是 n

在这里插入图片描述

在这里插入图片描述

🖊 有的资料说链表添加和删除的复杂度是O(1),这说的是添加和删除的 “哪一刻”,但找到 prev 的时间复杂度可能是 O(n)
在这里插入图片描述
在这里插入图片描述

8、完整代码

🖊 带有虚拟头节点的单链表完整代码

相关文章:

【4】单链表(有虚拟头节点)

【4】单链表&#xff08;有虚拟头节点&#xff09; 1、虚拟头节点2、构造方法3、node(int index) 返回索引位置的节点4、添加5、删除6、ArrayList 复杂度分析(1) 复杂度分析(2) 数组的随机访问(3) 动态数组 add(E element) 复杂度分析(4) 动态数组的缩容(5) 复杂度震荡 7、单链…...

html第二次作业

骨架 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdevice-width, initi…...

Android客户端自动化UI自动化airtest从0到1搭建macos+脚本设计demo演示+全网最全最详细保姆级有步骤有图

iOS客户端自动化UI自动化airtest从0到1搭建macosdemo演示-CSDN博客 一、基础环境 1. 安装jdk 选择jdk8 如果下载高版本 可能不匹配会失败 下载.dmg文件 苹果电脑 &#xff5c; macOS &#xff5c; jdk1.8 &#xff5c; 环境变量配置_jdk1.8 mac-CSDN博客 Java Downloads …...

基于单片机的自动浇灌系统的设计

本文设计了一款由单片机控制的自动浇灌系统。本设计的硬件电路采用AT89C51单片机作为主控芯片,采用YL-69土壤湿度传感器检测植物的湿度。通过单片机将采集湿度值与设定值分析处理后,控制报警电路和水泵浇灌电路的开启,从而实现植物的自动浇灌。 1 设计目的 随着生活水平的…...

WebStorm 与 VSCode 对比分析

WebStorm 与 VSCode 对比分析 1. 引言 简述WebStorm和VSCode的普及和重要性 WebStorm和Visual Studio Code(VSCode)是当前最受欢迎的代码编辑器之一,它们在现代软件开发中扮演着至关重要的角色。WebStorm,由JetBrains开发,是一个强大的IDE,特别受JavaScript开发者的欢…...

git命令-项目使用

项目中用到的git命令&#xff0c;记录下来&#xff0c;后续项目可以直接用 配置命令 一次性设置&#xff1a; git config --global user.name "Your Name" git config --global user.email "youremailaddress.com"git config --global alias.pl "pu…...

python安装删除以及pip的使用

目录 你无法想象新手到底会在什么地方出问题——十二个小时的血泪之言&#xff01; 问题引入 python modify setup 隐藏文件夹 环境变量的配置 彻底删除python 其他零碎发现 管理员终端 删不掉的windous应用商店apps 发现问题 总结 你无法想象新手到底会在什么地方…...

7、鸿蒙学习-共享包概述

HarmonyOS提供了两种共享包&#xff0c;HAR&#xff08;Harmony Archive&#xff09;静态共享包&#xff0c;和HSP&#xff08;Harmony Shared Package&#xff09;动态共享包。 HAR与HSR都是为了实现代码和资源的共享&#xff0c;都可以包含代码、C库、资源和配置文件&#xf…...

亚马逊测评新策略:解决底层环境防关联,提升下单成功率

对于做测评的环境系统&#xff0c;确保稳定性和成功率是非常重要的。市面上有各种环境方案&#xff0c;如虚拟机、模拟机、gcs、云手机、VPS等。然而&#xff0c;这些方案不仅成本高&#xff0c;而且成功率很低。因此&#xff0c;一个好的环境系统是成功的基础。 亚马逊平台的…...

容器和注解开发

1.创建容器的两种方式 //1.加载类路径下的配置文件//ApplicationContext ctx new ClassPathXmlApplicationContext("applicationContext.xml"); //2.从文件系统下加载配置文件(绝对路径) ApplicationContext ctx new FileSystemXmlApplicationContex…...

有趣且重要的JS知识合集(21)浏览器内置对象讲解之Dom篇

1、Dom 1.1、概念 Document Object Model&#xff08;文档对象模型&#xff09;, 整个WEB页面, 所有的Dom元素都在Document整个文档里。DOM就是把整个文档页面当做一个对象进行操作, document 下 包含了 根据 html 创建 的 Dom 对象, 这个DOM对象, 以树形结构展示, 即DOM树 …...

3.两数相加 - 链表

文章目录 题目简介题目解答代码&#xff1a; 题目链接 大家好&#xff0c;我是晓星航。今天为大家带来的是 两数相加 相关的讲解&#xff01;&#x1f600; 题目简介 题目解答 通过题目给的第一个示例来解析 图解如下&#xff1a; l1的2和l2的5首先相加变为7 这里相加结果为7…...

iptables 与 firewalld 防火墙

iptables iptables 是一款基于命令行的防火墙策略管理工具 四种防火墙策略&#xff1a; ACCEPT&#xff08;允许流量通过&#xff09; 流量发送方会看到响应超时的提醒&#xff0c;但是流量发送方无法判断流量是被拒绝&#xff0c;还是接收方主机当前不在线 REJECT&#xff08…...

Taskflow:异步任务(Asynchronous Tasking)

简单使用 tf::Executor 提供了异步执行Task的操作tf::Executor::async&#xff0c;并返回Future&#xff0c;用于保留该函数调用的结果。 #include <taskflow/taskflow.hpp>void print_str(char const* str) {std::cout << str << std::endl; }int main() …...

学习鸿蒙基础(9)

目录 一、鸿蒙国际化配置 二、鸿蒙常用组件介绍 三、鸿蒙像素单位介绍 四、鸿蒙布局介绍 1、Row与Column线性布局 2、层叠布局-Stack 3、弹性布局 4、栅格布局 5、网格布局 一、鸿蒙国际化配置 base目录下为默认的string。en_US对应美国的。zh_CN对应中国的。新增一个s…...

spring boot的小数位丢失.00 或者.0

1、背景 在使用spring boot时&#xff0c;前端的界面展示的数据是2 &#xff0c;在数据库中存储的是小数。但是导出Excel的时候数据是 2.00 。奇了怪了为啥会不一样&#xff0c;数据都是一样的没有做过处理。 2、排查问题 经过层层的debug 发现数据库返回的数据是2.00&#x…...

nginx如何清理页面缓存

在 Nginx 中&#xff0c;清理页面缓存通常涉及配置缓存头以控制缓存行为&#xff0c;或者使用外部工具或机制来清除缓存。以下是一些建议来管理和清理 Nginx 的页面缓存&#xff1a; 配置缓存头&#xff1a; Nginx 本身不直接提供缓存机制&#xff0c;但可以通过配置 proxy_cac…...

深度学习pytorch——经典卷积网络之ResNet(持续更新)

错误率前五的神经网络&#xff08;图-1&#xff09;&#xff1a; 图-1 可以很直观的看到&#xff0c;随着层数的增加Error也在逐渐降低&#xff0c;因此深度是非常重要的&#xff0c;但是学习更好的网络模型和堆叠层数一样简单吗&#xff1f;通过实现表明&#xff08;图-2&…...

react 面试题(2024 最新版)

1. 对 React 的理解、特性 React 是靠数据驱动视图改变的一种框架&#xff0c;它的核心驱动方法就是用其提供的 setState 方法设置 state 中的数据从而驱动存放在内存中的虚拟 DOM 树的更新 更新方法就是通过 React 的 Diff 算法比较旧虚拟 DOM 树和新虚拟 DOM 树之间的 Chan…...

JVM(三)——字节码技术

三、字节码技术 1、类文件结构 一个简单的 HelloWorld.java package com.mysite.jvm.t5; // HelloWorld 示例 public class HelloWorld {public static void main(String[] args) {System.out.println("hello world");} }执行 javac -parameters -d . HellowWorld.…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...