作者：小傅哥

博客：

沉淀、分享、成长，让自己和他人都能有所收获！

一、前言

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

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

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

二、数组数据结构

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

数组的特点：

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

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

2. 二维数组

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

三、实现数组列表

在 Java 的源码中，数组是一个非常常用的数据结构，很多其他数据结构也都有数组的影子。在一些数据存放和使用的场景中，基本也都是使用 ArrayList 而不是 LinkedList，具体性能分析参考：LinkedList插入速度比ArrayList快？你确定吗？

那么本章节我们就借着数组结构的学习，实现一个简单的 ArrayList，让使用 Java 的读者既能了解学习数据结构，也能了解到 Java 源码实现。

源码地址： - Java 算法与数据结构本章源码：1. 基本设计

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

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

public boolean add(E e) {    // 确保内部容量    int minCapacity = size + 1;    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);    }    // 判断扩容操作    if (minCapacity - elementData.length > 0) {        int oldCapacity = elementData.length;        int newCapacity = oldCapacity + (oldCapacity >> 1);        if (newCapacity - minCapacity < 0) {            newCapacity = minCapacity;        }        elementData = Arrays.copyOf(elementData, newCapacity);    }    // 添加元素    elementData[size++] = e;    return true;}

这是一份简化后的 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

删除元素

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;}

public E get(int index) {    return (E) elementData[index];}@Overridepublic String toString() {    return "ArrayList{" +            "elementData=" + Arrays.toString(elementData) +            ", size=" + size +            '}';}

@Testpublic 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);}

测试结果

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