【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默认指向null
        first = 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)

    /**
     * 往索引位置添加元素
     */
    @Override
    public 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 被删除的元素
     */
    @Override
    public 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、完整代码

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/506126.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Linux 10】环境变量

文章目录 &#x1f308; Ⅰ 命令行参数⭐ 1. main 函数的参数⭐ 2. main 函数参数的意义⭐ 3. 查看 argv 数组的内容⭐ 4. 命令行参数结论⭐ 5. 为什么要有命令行参数⭐ 6. 命令行参数传递由谁执行 &#x1f308; Ⅱ 环境变量基本概念⭐ 1. 常见环境变量 &#x1f308; Ⅲ 查看…

LeetCode_876(链表的中间结点)

//双指针//时间复杂度O(n) 空间复杂度O(1)public ListNode middleNode(ListNode head) {ListNode slowhead,fast head;while (fast!null && fast.next!null){slow slow.next;fast fast.next.next;}return slow;} 1->2->3->4->5->null 快指针移动两个…

9款免费云服务器,最长永久免费使用

随着云计算技术的快速发展&#xff0c;越来越多的企业和个人开始选择使用云服务器。云服务器提供了灵活、可扩展且易于管理的资源&#xff0c;使得用户可以根据需求随时调整计算能力。本文将分享9款免费云服务器&#xff0c;其中最长可永久免费使用&#xff0c;为用户提供了更多…

flutter官方案例context_menus

1&#xff1a;根据项目中的案例进行部署 2&#xff1a;运行查看有什么用&#xff0c;可不可以直接复制粘贴 案例地址 https://github.com/flutter/samples/tree/main/context_menus案例展示方法 直接把这个文件夹中的文件复制到lib文件夹中 3&#xff0c;19&#xff0c;4的fl…

HTML常用的图片标签和超链接标签

目录 一.常用的图片标签和超链接标签&#xff1a; 1.超链接标签&#xff1a; 前言: 超链接的使用&#xff1a; target属性: 1)鼠标样式&#xff1a; 2)颜色及下划线: 总结: 2.图片标签&#xff1a; 前言: img的使用: 设置图片&#xff1a; 1.设置宽度和高度: 2.HTM…

内网渗透之黄金票据的制作

1、黄金票据是用来留后门的也叫做未知权限&#xff0c;前提条件是你已经拿到了域控的最高权限 一、开始之前我们先来了解一下kerberos Kerberos是一种由MIT&#xff08;麻省理工大学&#xff09;提出的一种网络身份验证协议。它旨在通过使用密钥加密技术为客户端/服务器应…

基于muduo网络库实现的集群聊天服务器

目录 项目内容开发环境安装说明技术介绍项目目录数据库设计项目介绍启动服务器启动客户端注册账号登录成功一对一聊天业务创建群聊业务加入群聊业务群聊业务添加好友业务离线消息存储业务 特殊说明 &#xff01;&#xff01;&#xff01;项目是照着腾讯课堂施磊老师的视频学习&…

【QT+QGIS跨平台编译】054:【exiv2lib_int+Qt跨平台编译】(一套代码、一套框架,跨平台编译)

点击查看专栏目录 文章目录 一、exiv2lib_int介绍二、文件下载三、文件分析四、pro文件五、编译实践一、exiv2lib_int介绍 exiv2lib_int是 exiv2 这个开源的图像元数据库中的一个组件。 Exiv2是一个开源的C++库,用于读取、编辑和写入图片和视频文件的元数据。它可以处理各种类…

01-XML-04XML处理

XML处理 DOM DOM解析要求解析器将整个XML文件全部加载到内存中&#xff0c;生成一个Document对象。 优点&#xff1a;元素和元素之间保留结构&#xff0c;关系&#xff0c;可以针对元素进行增删改查操作。 缺点&#xff1a;如果XML文件过大&#xff0c;可能会导致内存溢出。SA…

【Linux】寿司线程池{单例模式之懒汉模式下的线程池}

文章目录 回顾单例模式0.多线程下的单例模式的意义1.什么是单例模式1.0设计模式1.1C单例模式的介绍及原理1.2拷贝构造和赋值重载的处理1.3if (nullptr ptr)&#xff0c;nullptr放在比较运算符的前面?1.4实现单例模式的方式 2.实现懒汉方式的单例模式2.1单线程的单例模式2.2多…

Go 源码之 gin 框架

Go 源码之 gin 框架 go源码之gin - Jxy 博客 一、总结 gin.New()初始化一个实例&#xff1a;gin.engine&#xff0c;该实例实现了http.Handler接口。实现了ServeHTTP方法 注册路由、注册中间件&#xff0c;调用addRoute将路由和中间件注册到 methodTree 前缀树&#xff08;节…

AR-Net网络(图像篡改检测)

AR-Net网络 摘要AbstractAR-Net1. 文献摘要2. 研究背景3. 创新点4. AR-Net 网络架构5. 实验6. 结论总结 摘要 AR-Net使用自适应注意力机制来融合位置和通道维度的特征&#xff0c;使网络能够充分利用不同维度的被篡改特征&#xff0c;此外&#xff0c;AR-Net 改进了预测掩模&a…

【Web and HTTP,HTTP概况,HTTP连接,持久HTTP,用户-服务器状态:cookie】

文章目录 Web and HTTPHTTP概况HTTP:超文本传输协议使用TCP&#xff1a;HTTP是无状态的 HTTP连接非持久HTTP持久HTTP响应时间模型 持久HTTP非持久HTTP的缺点&#xff1a;持久HTTP提交表单输入 用户-服务器状态&#xff1a;cookie Web and HTTP Web页&#xff1a;由一些对象组成…

智慧校园管理系统

一、项目介绍 1.1 项目简介 智慧校园管理系统&#xff1a;主要是以年级、班级为单位&#xff0c;进行老师和学生信息记录和统计功能。项目采用前后端分离架构思想&#xff0c;前端采用HTMLCSSVUE来实现页面效果展示&#xff0c;后端采用SpringBootMybatisPlus框架实现数据存储…

v3-admin-vite 改造自动路由,view页面自解释Meta

需求 v3-admin-vite是一款不错的后端管理模板&#xff0c;主要是pany一直都在维护&#xff0c;最近将后台管理也进行了升级&#xff0c;顺便完成一直没时间解决的小痛痒&#xff1a; 在不使用后端动态管理的情况下。我不希望单独维护一份路由定义&#xff0c;我希望页面是自解…

鸿蒙手机cordova-plugin-camera不能拍照和图片不显示问题

鸿蒙手机cordova-plugin-camera不能拍照和图片不显示问题 一、运行环境 1、硬件 手机型号&#xff1a;NOVA 7 系统&#xff1a;HarmonyOS版本 4.0.0 2、软件 android SDK platforms&#xff1a;14.0(API Level 34)、13.0&#xff08;API Level 33&#xff09; SDK Build-T…

【踩坑】荣耀系统Android8.0 system目录Read-only file system

本来以为直接把Charles证书改成系统证书格式&#xff0c;然后通过mt管理器root之后移动到系统证书目录就行了&#xff0c;结果访问baidu仍然显示网络错误&#xff0c;折腾一晚上。后来直接安装为用户证书&#xff0c;与系统证书冲突。 手机型号&#xff1a;荣耀v10 EMUI&…

win10 安装kubectl,配置config连接k8s集群

安装kubectl 按照官方文档安装&#xff1a;https://kubernetes.io/docs/tasks/tools/install-kubectl-windows/ curl安装 &#xff08;1&#xff09;下载curl安装压缩包: curl for Windows &#xff08;2&#xff09;配置环境变量&#xff1a; 用户变量&#xff1a; Path变…

牛客NC92 最长公共子序列(二)【中等 动态规划 Java,Go,PHP】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/6d29638c85bb4ffd80c020fe244baf11 思路 https://blog.csdn.net/qq_36544411/article/details/120021203 思路 动态规划法&#xff0c; 我们以dp[i][j]表示在s1中以第i个元素结尾&#xff0c;s2中以第j个元素结…

CCF-CSP26<2022-06>-第1/2/3题

202206-1 归一化处理 题目&#xff1a;202206-1 题目分析&#xff1a; 给出了数学上归一化的数学公式&#xff0c;直接按照要求完成即可。 AC代码&#xff1a; #include <bits/stdc.h> using namespace std; int main() {int n;cin >> n;double a[n];double s…