数据结构数组 Array 手写实现,扩容原理

数组数据结构

数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型数据的集合。

数组的特点:

  1. 数组是相同数据类型的元素集合(int 不能存放 double)
  2. 数组中各元素的存储是有先后顺序的,它们在内存中按照这个顺序连续存放到一起。内存地址连续。
  3. 数组获取元素的时间复杂度为O(1)

1. 一维数组

维数组是最常用的数组,其他很多数据结构的变种也都是从一维数组来的。例如 HashMap 的拉链寻址结构,ThreadLocal 的开放寻址结构,都是从一维数组上实现的。

2. 二维数组

二维以及多维数组,在开发场景中使用到的到是不多,不过在一些算法逻辑,数学计算中到是可以使用。

✍️手写实现数组列表

在 Java 的源码中,数组是一个非常常用的数据结构,很多其他数据结构也都有数组的影子。在一些数据存放和使用的场景中,基本也都是使用 ArrayList 而不是 LinkedList

需要实现的方法

public interface PjpList<E> {// 添加boolean add(E e);// 删除E remove(int index);// 获取E get(int index);}

实现类

public class PjpArrayList<E> implements PjpList<E> {}

1. 📐基本设计

数组是一个固定的、连续的、线性的数据结构,那么想把它作为一个自动扩展容量的数组列表,则需要做一些扩展。

/*** 默认初始化空间*/
private static final int DEFAULT_CAPACITY = 10;/*** 空元素*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};/*** ArrayList 元素数组缓存区*/
transient Object[] elementData;/*** List 集合元素数量*/
private int size;

2. 初始化

初始化分指定大小、不指定大小

public PjpArrayList() {// 初始化 ArrayList 阶段,如果不指定大小,默认给个空的元素,当开始添加元素的时候在初始化长度this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}public PjpArrayList(int initialCapacity) {
if (initialCapacity > 0) {// 如果给定长度大于0,那么直接创建一个数组this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
} else {throw new IllegalArgumentException("Illegal Capacity: " +initialCapacity);
}
}
  1. 初始化 ArrayList 阶段,如果不指定大小,默认会初始化一个空的元素。这个时候是没有默认长度的。
  2. 那么什么时候给初始化的长度呢?是在首次添加元素的时候,因为所有的添加元素操作,也都是需要判断容量,以及是否扩容的。那么在 add 添加元素时统一完成这个事情,还是比较好处理的。
  3. 之后就是随着元素的添加,容量是会不足的。当容量不足的是,需要进行扩容操作。同时还得需要把旧数据迁移到新的数组上。所以数据的迁移算是一个比较耗时的操作

3. 添加元素

@Override
public boolean add(E e) {
int minCapacity = size + 1;
// 判断当前容量与初始化容量,使用 Math.max 函数取最大值最为最小初始化空间
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
if (minCapacity - elementData.length > 0) {int oldCapacity = elementData.length;// 扩为原来的1.5倍int newCapacity = oldCapacity + (oldCapacity >> 1);// 如果是第一次扩容,扩容至初始化空间大小if (newCapacity - minCapacity < 0) {newCapacity = minCapacity;}elementData = Arrays.copyOf(elementData, newCapacity);
}
elementData[size++] = e;
return true;
}
  1. 判断当前容量与初始化容量,使用 Math.max 函数取最大值最为最小初始化空间。
  2. 接下来是判断 minCapacity 和元素的数量,是否达到了扩容。首次创建 ArrayList 是一定会扩容的,也就是初始化 DEFAULT_CAPACITY = 10 的容量。
  3. Arrays.copyOf 实际上是创建一个新的空间数组,之后调用的 System.arraycopy 迁移到新创建的数组上。这样后续所有的扩容操作,也就都保持统一了。
  4. ArrayList 扩容完成后,就是使用 elementData[size++] = e; 添加元素操作了。

4. 移除元素

ArrayList 的重点离不开对 System.arraycopy 的使用,它是一个本地方法,可以让你从原数组的特定位置,迁移到新数组的指定位置和迁移数量。

public static native void arraycopy(Object src,  int  srcPos,Object dest, int destPos,int length);

arraycopy 各个参数的含义

src:     原数组
srcPos: 原数组起始位置(从这个位置开始复制)
dest:   目标数组
destPos:目标数组粘贴的起始位置
length: 复制的个数

元素删除

public E remove(int index) {
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0) {System.arraycopy(elementData, index + 1, elementData, index, numMoved);
}
elementData[--size] = null; // 为了GC和我们不会再读到
return oldValue;
}

  • ArrayList 的元素删除,就是在确定出元素位置后,使用 System.arraycopy 拷贝数据方式移动数据,把需要删除的元素位置覆盖掉。
  • 此外它还会把已经删除的元素设置为 null 一方面让我们不会在读取到这个元素,另外一方面也是为了 GC

5. 获取元素

@Override
public E get(int index) {
return (E) elementData[index];
}@Override
public String toString() {return "PjpArrayList{" +"elementData=" + Arrays.toString(elementData) +", size=" + size +'}';
}
  • 获取元素就比较简单了,直接从 elementData 使用索引直接获取即可。这个是一个 O(1) 操作。也正因为搜索元素的便捷性,才让 ArrayList 使用的那么广泛。

测试

public class test {public static void main(String[] args) {PjpList<String> num =new  PjpArrayList<>();num.add("a");num.add("b");num.add("c");num.remove(0);System.out.println(num.get(1));System.out.println(num);num.add("d");num.add("e");num.add("f");num.add("g");num.add("h");num.add("i");num.add("j");num.add("k");num.add("l");System.out.println("扩容");System.out.println(num);}
}

测试结果

⚠️注意:在添加第 11 个元素的时候,数组进行了扩容长度扩为原来的 1.5 倍(10 ->15)

c
PjpArrayList{elementData=[b, c, null, null, null, null, null, null, null, null], size=2}
扩容
PjpArrayList{elementData=[b, c, d, e, f, g, h, i, j, k, l, null, null, null, null], size=11}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

(免费领源码)php#mysql红色旅游网站99214-计算机毕业设计项目选题推荐

摘 要 21世纪时信息化的时代&#xff0c;几乎任何一个行业都离不开计算机&#xff0c;将计算机运用于旅游服务管理也是十分常见的。过去使用手工的管理方式对旅游服务进行管理&#xff0c;造成了管理繁琐、难以维护等问题&#xff0c;如今使用计算机对旅游服务的各项基本信息进…

2023年10月24日程序员节

这里写自定义目录标题 欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题&#xff0c;有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants 创建一个自定义列表如何创建一个…

Coreldraw2020最新64位电脑完整版本下载教程

安装之前所有的杀毒软件都要退出。无论是360&#xff0c;腾讯管家&#xff0c;或者电脑自带的安全中心&#xff0c;要不然会阻止安装。 CorelDRAW2020版win下载如下:https://wm.makeding.com/iclk/?zoneid55678 CorelDRAW2020版mac下载如下:https://wm.makeding.com/iclk/?…

linux下安装配置maven

一. 下载maven安装包 安装 maven 环境前&#xff0c;需要先安装 java 环境&#xff0c;笔者这里已经成功安装 java 环境&#xff0c;如果没有安装 java 环境&#xff0c;可以参考&#xff1a;https://blog.csdn.net/qq_44936392/article/details/133931321?spm1001.2014.3001.…

.net6部署到linux上(CentOS Linux 7)

目录 一、先在linux上配置.net环境 添加 Microsoft 包存储库 安装 SDK 安装运行时 检查 SDK 版本可使用终端查看当前安装的 .NET SDK 版本。 打开终端并运行以下命令。 二、创建.net6 mvc项目 并发布 创建项目 修改默认端口 打包发布到文件夹 运行打包项目查看项目是否…

redis 数据结构

一、为什么要扒一下底层技术 首先我是一个解决方案工程师&#xff0c;为什么要看redis底层的设计呢&#xff1f;总结下来分几点&#xff1a; 1. 让系统跑起来更放心 2. 面试中可以对跟对面的牛马侃大山、吹&#x1f42e; 3. 虚一点&#xff0c;举一反三&#xff0c;学习一下…

SocketBase类库

SocketBase类库主要是方便创建Socket客户端和Socket服务端的基础实现。 抽象基类&#xff1a;主要实现创建Socket public abstract class NetworkBase{} 通用基类&#xff1a;指定了消息的解析规则&#xff0c;指定了数据转换的规则 的基本实现 /// <summary>/// 支持长…

Kotlin函数作为参数指向不同逻辑(二)

Kotlin函数作为参数指向不同逻辑&#xff08;二&#xff09; fun sum(): (Int, Int) -> Int {return { a, b -> (a b) } }fun multiplication(): (Int, Int) -> Int {return { a, b -> (a * b) } }fun math(a: Int, b: Int, foo: (Int, Int) -> Int): Int {ret…

基于OpenAPI、freemarker动态生成swagger文档

前言 spring项目中可以使用springfox或者springdoc&#xff0c;通过写注解的方式生成swagger文档&#xff0c;下面介绍一种不写注解&#xff0c;动态生成swagger文档的方式&#xff0c;在某些场景会适用&#xff0c;例如接口是动态生成的&#xff0c;此时swagger就不能通过注解…

Xshell+screen解决ssh连接 服务器掉线的问题

Linux screen命令解决SSH远程服务器训练代码断开连接后运行中断_linux screen ssh-CSDN博客 Linux命令之screen命令_linux screen_恒悦sunsite的博客-CSDN博客 使用教程&#xff1a; 这里粗略介绍一下 &#xff08;1&#xff09;xshell xftp&#xff08;xshell点这个&#…

解救Kubernetes混乱:Descheduler快速实现资源平衡

By default, Kubernetes doesn’t recompute and rebalance workloads. You could have a cluster with fewer overutilized nodes and others with a handful of pods How can you fix this? 关注【云原生百宝箱】公众号&#xff0c;快速掌握云原生 默认情况下&#xff0c;Ku…

Linux_API_系列-整体概览

总论 Linux下API编程不像Windows一样&#xff0c;对每种设备和不同功能都有统一的API&#xff0c;所以有了《Windows核心编程》这种导论一类的大而全的书籍&#xff0c;整本书厚的像一块砖头。 Linux下贯彻了一贯的“一切皆文件”的宗旨&#xff0c;所以对于系统编程而言&…

RabbitMQ相关的其他知识点

RabbitMQ相关的其他知识点 一、幂等性1.1 概念1.2 消息重复消费1.3 消费端的幂等性保障 二、优先队列2.1 应用场景2.2 实现原理2.3 代码实现 三、惰性队列3.1 定义3.2 应用场景3.3 两种设置模式3.4 内存开销对比 一、幂等性 1.1 概念 用户对于同一操作发起的一次请求或者多次请…

初识JAVA,带你入门

本章重点&#xff1a; 1. Java语言简介、发展概述、语言优势、与C/C区别 2. 初识Java程序入口之main方法 3. 注释、标识符、关键字 1. Java语言概述 1.1 Java是什么&#xff1f; Java是一种优秀的程序设计语言&#xff0c;它具有令人赏心悦目的语法和易于理解的语义…

操作系统学习笔记7-IO管理

文章目录 1、IO管理学什么(学习逻辑图)2、IO管理硬件知识-IO设备的分类(硬件分类)3、IO管理硬件知识-IO控制方式的发展过程4、IO管理硬件知识-IO控制方式-程序直接控制方式5、IO管理硬件知识-IO控制方式-中断控制方式6、IO管理硬件知识-IO控制方式-DMA控制方式7、IO管理硬件知识…

中心胖AP(AD9430DN)+远端管理单元RU(R240D)+出口网关,实现组网

适用于&#xff1a;V200R008至V200R019C00版本的万兆中心胖AP&#xff08;AD9431DN-24X&#xff09;。 组网规划 RU管理&#xff1a;VLAN 100&#xff0c;网段为192.168.100.0/24。 无线业务&#xff1a;VLAN 3&#xff0c;SSID为“wlan-net”&#xff0c;密码为“88888888”…

安卓富文本部分高亮及点击事件

安卓富文本部分高亮及点击事件 前言一、富文本是什么&#xff1f;二、实现方法1.使用html2.使用SpannableString 总结 前言 富文本其实不是很常用&#xff0c;但有遇到了过后使用很方便的场景&#xff0c;例如免责声明。这时候就很重要了&#xff0c;前段时间遇到了&#xff0…

软件测试(概念篇)

前言 从这篇博客开始&#xff0c;我们将开始正式学习测试&#xff0c;在开始第一次软件测试之前&#xff0c;我们需要先了解软件测试的一些基本概念。 这些基本概念将帮助我们更加明确工作的目标&#xff0c;以便于更快的融入到测试团队中去   在这里我们将回答以下问题&…

vue v-for

目录 前言&#xff1a;Vue.js 中的 v-for 指令 详解&#xff1a;v-for 指令的基本概念 用法&#xff1a;v-for 指令的实际应用 1. 列表渲染 2. 动态组件 3. 表单选项 4. 嵌套循环 5. 键值对遍历 解析&#xff1a;v-for 指令的优势和局限性 优势&#xff1a; 局限性&a…

希捷推出Exos系列24TB硬盘:配备增强型缓存 性能提高三倍

希捷推出了全新的Exos 24TB硬盘。其基于传统的CMR构建&#xff0c;为3.5英寸规格&#xff0c;转速为7200 RPM。 同时&#xff0c;Exos系列24TB硬盘拥有10片磁盘&#xff0c;每片磁盘的容量为2.4TB&#xff0c;是希捷存储密度最高的硬盘&#xff0c;适用于超大规模企业和数据中心…