自助网站建设方案,家在深圳歌词,深圳app开发公司,邯郸市商标设计品牌策划公司一、前言数组是数据结构还是数据类型#xff1f;数组只是个名称#xff0c;它可以描述一组操作#xff0c;也可以命名这组操作。数组的数据操作#xff0c;是通过 idx-val 的方式来处理。它不是具体要求内存上要存储着连续的数据才叫数组#xff0c;而是说#xff0c…一、前言数组是数据结构还是数据类型数组只是个名称它可以描述一组操作也可以命名这组操作。数组的数据操作是通过 idx-val 的方式来处理。它不是具体要求内存上要存储着连续的数据才叫数组而是说通过连续的索引 idx也可以线性访问相邻的数据。那么当你定义了数据的存储方式也就定义了数据结构。所以它也是被归类为数据结构。二、数组数据结构数组Array是一种线性表数据结构。它用一组连续的内存空间来存储一组具有相同类型数据的集合数组的特点数组是相同数据类型的元素集合int 不能存放 double数组中各元素的存储是有先后顺序的它们在内存中按照这个顺序连续存放到一起。内存地址连续。数组获取元素的时间复杂度为O(1)1. 一维数组一维数组是最常用的数组其他很多数据结构的变种也都是从一维数组来的。例如 HashMap 的拉链寻址结构ThreadLocal 的开放寻址结构都是从一维数组上实现的。2. 二维数组二维以及多维数组在开发场景中使用到的到是不多不过在一些算法逻辑数学计算中到是可以使用。三、实现数组列表1. 基本设计数组是一个固定的、连续的、线性的数据结构那么想把它作为一个自动扩展容量的数组列表则需要做一些扩展。 /*** 默认初始化空间*/
private static final int DEFAULT_CAPACITY 10;
/*** 空元素*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};
/*** ArrayList 元素数组缓存区*/
transient Object[] elementData;
初始化 ArrayList 阶段如果不指定大小默认会初始化一个空的元素。这个时候是没有默认长度的。那么什么时候给初始化的长度呢是在首次添加元素的时候因为所有的添加元素操作也都是需要判断容量以及是否扩容的。那么在 add 添加元素时统一完成这个事情还是比较好处理的。之后就是随着元素的添加容量是会不足的。当容量不足的是需要进行扩容操作。同时还得需要把旧数据迁移到新的数组上。所以数据的迁移算是一个比较耗时的操作2. 添加元素这是一份简化后的 ArrayList#add 操作判断当前容量与初始化容量使用 Math.max 函数取最大值最为最小初始化空间。接下来是判断 minCapacity 和元素的数量是否达到了扩容。首次创建 ArrayList 是一定会扩容的也就是初始化 DEFAULT_CAPACITY 10 的容量。Arrays.copyOf 实际上是创建一个新的空间数组之后调用的 System.arraycopy 迁移到新创建的数组上。这样后续所有的扩容操作也就都保持统一了。ArrayList 扩容完成后就是使用 elementData[size] e; 添加元素操作了。小贴士若是不懂System.arraycopy可以看我的另一篇文章https://blog.csdn.net/qq_63815371/article/details/129200269?spm1001.2014.3001.55013. 移除元素ArrayList 的重点离不开对 System.arraycopy 的使用它是一个本地方法可以让你从原数组的特定位置迁移到新数组的指定位置和迁移数量。如图 2-5 所示数据迁移 测试代码在 java-algorithms删除元素public E remove(int index) {E oldValue (E) elementData[index];int numMoved size - index - 1;if (numMoved 0) {// 从原始数组的某个位置拷贝到目标对象的某个位置开始后n个元素System.arraycopy(elementData, index 1, elementData, index, numMoved);}elementData[--size] null; // clear to let GC do its workreturn oldValue;
}
ArrayList 的元素删除就是在确定出元素位置后使用 System.arraycopy 拷贝数据方式移动数据把需要删除的元素位置覆盖掉。此外它还会把已经删除的元素设置为 null 一方面让我们不会在读取到这个元素另外一方面也是为了 GC4. 获取元素public E get(int index) {return (E) elementData[index];
}
Override
public String toString() {return ArrayList{ elementData Arrays.toString(elementData) , size size };
}
获取元素就比较简单了直接从 elementData 使用索引直接获取即可。这个是一个 O(1) 操作。也正因为搜索元素的便捷性才让 ArrayList 使用的那么广泛。同时为了兼容可以通过元素来获取数据而不是直接通过下标引出了 HashMap 使用哈希值计算下标的计算方式也引出了斐波那契散列。它们的设计都是在尽可能减少元素碰撞的情况下尽可能使用贴近 O(1) 的时间复杂度获取数据。 四、数组列表测试Test
public void test_array_list() {cn.bugstack.algorithms.data.array.ListString list new ArrayList();list.add(01);list.add(02);list.add(03);list.add(04);list.add(05);list.add(06);list.add(07);list.add(08);list.add(09);list.add(10);list.add(11);list.add(12);System.out.println(list);list.remove(9);System.out.println(list);
}
测试结果ArrayList{elementData[01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, null, null, null], size12}
ArrayList{elementData[01, 02, 03, 04, 05, 06, 07, 08, 09, 11, 12, null, null, null, null], size11}Process finished with exit code 0
测试案例中包括了在我们自己实现的 ArrayList 中顺序添加元素逐步测试扩容迁移元素以及删除元素后数据的迁移。最终的测试结果可以看到一共有12个元素其中idx9的元素被删除前后元素的迁移变化。五、常见面试问题数据结构中有哪些是线性表数据结构数组的元素删除和获取时间复杂度是多少ArrayList 中默认的初始化长度是多少ArrayList 中扩容的范围是多大一次ArrayList 是如何完成扩容的System.arraycopy 各个入参的作用是什么
