当前位置: 首页 > 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.…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...

什么是VR全景技术

VR全景技术&#xff0c;全称为虚拟现实全景技术&#xff0c;是通过计算机图像模拟生成三维空间中的虚拟世界&#xff0c;使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验&#xff0c;结合图文、3D、音视频等多媒体元素…...

ZYNQ学习记录FPGA(一)ZYNQ简介

一、知识准备 1.一些术语,缩写和概念&#xff1a; 1&#xff09;ZYNQ全称&#xff1a;ZYNQ7000 All Pgrammable SoC 2&#xff09;SoC:system on chips(片上系统)&#xff0c;对比集成电路的SoB&#xff08;system on board&#xff09; 3&#xff09;ARM&#xff1a;处理器…...