1.前言数组是数据结构还是数据类型？数组只是一个名字，它可以描述一组操作，也可以命名一组操作。数组的数据操作由idx->val处理。并没有特别要求在内存中存放连续的数据才叫数据，但是相邻的数据也可以通过连续的索引idx线性访问。然后，当您定义数据的存储方式时，您还定义了数据结构。所以也归类为数据结构。2.数组数据结构数组（Array）是一种线性表数据结构。它使用一组连续的内存空间来存储一组相同类型的数据。数组的特点：数组是相同数据类型元素的集合（int不能存储double）。数组中每个元素的存储是有顺序的，它们按照这个顺序一起存储在内存中。内存地址是连续的。从数组中获取元素的时间复杂度是O(1)1。一维数组一维数组是最常用的数组，许多其他数据结构变体也是从一维数组派生出来的。比如HashMap的拉链寻址结构，ThreadLocal的开放式寻址结构，都是从一维数组来实现的。2.二维数组二维和多维数组在开发场景中并不少用，但是在一些算法逻辑和数学计算中可以用到。3、实现数组列表在Java源码中，数组是一种非常常用的数据结构，其他很多数据结构也有数组的影子。在一些数据存储和使用场景中，基本都是用ArrayList代替LinkedList。具体的性能分析可以参考：LinkedList插入速度比ArrayList快？你确定吗？那么在本章中，我们将通过学习数组结构来实现一个简单的ArrayList，让使用Java的读者既能理解数据结构，又能理解Java源码实现。源码地址：https://github.com/fuzhengwei/java-algorithms-Java算法与数据结构本章源码：https://github.com/fuzhengwei/java-algorithms/blob/main/data-structures/src/main/java/cn/bugstack/algorithms/data/array/ArrayList.java1.基本设计数组是一个固定的、连续的、线性的数据结构，所以如果想把它作为一个自动扩容的数组链表来使用，就需要做一些扩展。/***默认初始化空间*/privatestaticfinalintDEFAULT_CAPACITY=10;/***空元素*/privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};/***ArrayList元素数组缓存*/transientObject[]元素数据；在初始化ArrayList阶段，如果不指定size，默认会初始化一个空元素。此时，没有默认长度。那么什么时候给初始化长度呢？是第一次添加元素的时候，因为所有添加元素的操作还需要判断容量和是否扩容。那么add添加元素的时候统一处理这个事情就比较容易了。之后随着元素的加入，容量就会不足。当容量不足时，需要扩容。同时，需要将旧数据迁移到新阵列中。所以数据迁移是一个耗时的操作2.添加元素publicbooleanadd(Ee){//保证内部容量intminCapacity=size+1;如果(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){minCapacity=Math.max(DEFAULT_CAPACITY,minCapacity);}//判断扩容操作if(minCapacity-elementData.length>0){intoldCapacity=elementData.length;intnewCapacity=oldCapacity+(oldCapacity>>1);如果(newCapacity-minCapacity<0){newCapacity=minCapacity;}elementData=Arrays.copyOf(elementData,newCapacity);}//添加元素elementData[size++]=e;returntrue;}这是一个简化的ArrayList#add操作，判断当前容量和初始容量，使用Math.max函数取最大值作为最小初始化空间。接下来判断minCapacity和元素个数是否达到扩容。第一次创建ArrayList，肯定会扩容，即初始化DEFAULT_CAPACITY=10的容量。Arrays.copyOf实际上创建了一个新的空间数组，然后调用System.arraycopy迁移到新创建的数组。这样一来，后续所有的扩容操作都会保持统一。ArrayList展开完成后，使用elementData[size++]=e;添加元素。3、移除元素ArrayList的关键点离不开System.arraycopy的使用，它是一个本地方法，可以让你从原数组中的特定位置迁移到新数组中的指定位置和迁移量。如图2-5所示，数据迁移测试代码在java-algorithms中删除元素publicEremove(intindex){EoldValue=(E)elementData[index];intnumMoved=大小-索引-1;if(numMoved>0){//从原数组的某个位置开始，从目标对象的某个位置开始后复制n个元素System.arraycopy(elementData,index+1,elementData,index,numMoved);}elementData[--size]=null;//明确让GC干活returnoldValue;}ArrayList的元素删除是用System.此外，它还会将删除的元素设置为空。一方面，我们不会再读这个元素。另一方面，它也适用于GC4。获取元素publicEget(intindex){return(E)elementData[index];}@OverridepublicStringtoString(){return"ArrayList{"+"elementData="+Arrays.toString(elementData)+",size="+size+'}';}直接从elementData中获取元素比较简单，可以直接使用索引获取。这是一个O(1)操作。正是因为查找元素的方便，ArrayList才被如此广泛地使用。同时为了兼容，可以通过元素而不是直接通过下标获取数据，这就导致了HashMap的计算方式是使用哈希值计算下标，也导致了斐波那契哈希。它们都是为了获取时间复杂度尽可能接近O(1)的数据，同时尽可能减少元素碰撞。学习这些内容，可以阅读小傅的《Java面经手册》，也可以随着本系列章节内容的铺垫，逐步覆盖算法进行学习。4.数组列表测试@Testpublicvoidtest_array_list(){cn.bugstack.algorithms.data.array.List
