线性数据结构：数组 Array

忘是亡心i 2024-03-26 13:39 27阅读 0赞

### 一、前言 ###

数组是数据结构还是数据类型？

数组只是个名称，它可以描述一组操作，也可以命名这组操作。数组的数据操作，是通过 idx->val 的方式来处理。它不是具体要求内存上要存储着连续的数据才叫数组，而是说，通过连续的索引 idx，也可以线性访问相邻的数据。

那么当你定义了数据的存储方式，也就定义了数据结构。所以它也是被归类为数据结构。

### 二、数组数据结构 ###

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

![3b2d7bd96bdf4fdc28c1d3aab0ae8603.png][]

数组的特点：

1.  数组是相同数据类型的元素集合（int 不能存放 double）

1.  数组中各元素的存储是有先后顺序的，它们在内存中按照这个顺序连续存放到一起。内存地址连续。

1.  数组获取元素的时间复杂度为O(1)

#### 1. 一维数组 ####

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

#### 2. 二维数组 ####

![73b09468a139718d0b866950d6dfe970.png][]

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

### 三、实现数组列表 ###

#### 1. 基本设计 ####

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

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

1.  初始化 ArrayList 阶段，如果不指定大小，默认会初始化一个空的元素。这个时候是没有默认长度的。

1.  那么什么时候给初始化的长度呢？是在首次添加元素的时候，因为所有的添加元素操作，也都是需要判断容量，以及是否扩容的。那么在 add 添加元素时统一完成这个事情，还是比较好处理的。

1.  之后就是随着元素的添加，容量是会不足的。当容量不足的是，需要进行扩容操作。同时还得需要把旧数据迁移到新的数组上。*所以数据的迁移算是一个比较耗时的操作*

#### 2. 添加元素 ####

![da7b3713dc6249a004865f12f77004b0.png][]

**这是一份简化后的 ArrayList\#add 操作**

1.  判断当前容量与初始化容量，使用 Math.max 函数取最大值最为最小初始化空间。

1.  接下来是判断 minCapacity 和元素的数量，是否达到了扩容。首次创建 ArrayList 是一定会扩容的，也就是初始化 DEFAULT\_CAPACITY = 10 的容量。

1.  Arrays.copyOf 实际上是创建一个新的空间数组，之后调用的 System.arraycopy 迁移到新创建的数组上。这样后续所有的扩容操作，也就都保持统一了。

1.  ArrayList 扩容完成后，就是使用 elementData\[size++\] = e; 添加元素操作了。

小贴士：若是不懂System.arraycopy可以看我的另一篇文章

[https://blog.csdn.net/qq\_63815371/article/details/129200269?spm=1001.2014.3001.5501][https_blog.csdn.net_qq_63815371_article_details_129200269_spm_1001.2014.3001.5501]

#### 3. 移除元素 ####

ArrayList 的重点离不开对 System.arraycopy 的使用，它是一个本地方法，可以让你从原数组的特定位置，迁移到新数组的指定位置和迁移数量。如图 2-5 所示，数据迁移 *测试代码在 java-algorithms*

![5ea19b115448c0f2f73aee93a37b1a86.png][]

**删除元素**

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 work
        return oldValue;
    }

*  ArrayList 的元素删除，就是在确定出元素位置后，使用 System.arraycopy 拷贝数据方式移动数据，把需要删除的元素位置覆盖掉。

*  此外它还会把已经删除的元素设置为 null 一方面让我们不会在读取到这个元素，另外一方面也是为了 GC

#### 4. 获取元素 ####

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.List<String> 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);
    }

**测试结果**

![dd7603af0776d6da265f8e5ea4e457dd.png][]

ArrayList{elementData=[01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, null, null, null], size=12}
    ArrayList{elementData=[01, 02, 03, 04, 05, 06, 07, 08, 09, 11, 12, null, null, null, null], size=11}
    
    Process finished with exit code 0

*  测试案例中包括了在我们自己实现的 ArrayList 中顺序添加元素，逐步测试扩容迁移元素，以及删除元素后数据的迁移。

*  最终的测试结果可以看到，一共有12个元素，其中idx=9的元素被删除前后，元素的迁移变化。

### 五、常见面试问题 ###

1.  数据结构中有哪些是线性表数据结构？

1.  数组的元素删除和获取，时间复杂度是多少？

1.  ArrayList 中默认的初始化长度是多少？

1.  ArrayList 中扩容的范围是多大一次？

1.  ArrayList 是如何完成扩容的，System.arraycopy 各个入参的作用是什么？

[3b2d7bd96bdf4fdc28c1d3aab0ae8603.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/0d93ff8714ad4ae7a8702b537952ddde.png
[73b09468a139718d0b866950d6dfe970.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/12b83b26dbbe44c0b849f5c07d3e6930.png
[da7b3713dc6249a004865f12f77004b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/fee9a7a9f1f6480ea660250ae2f10e24.png
[https_blog.csdn.net_qq_63815371_article_details_129200269_spm_1001.2014.3001.5501]: https://blog.csdn.net/qq_63815371/article/details/129200269?spm=1001.2014.3001.5501
[5ea19b115448c0f2f73aee93a37b1a86.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/16bc9643eb6d4030976e626b45f17b43.png
[dd7603af0776d6da265f8e5ea4e457dd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/051f1e1993fd4fa5b8d86caea91d5e59.png