数组学习

约 1755 字大约 6 分钟

数据结构

2025-03-04

本文作者：程序员飞云
本站地址：https://www.flycode.icu

数组的概念

数组是使用一组连续的内存空间，来存储具有相同类型的数据集合。

数组的特点

存储相同类型的数据
存储元素的内存地址是连续的
获取指定位置的元素时间复杂度是O(1)
数组无法删除元素，只能覆盖元素
数组下标从0开始

数组的操作

1. 数组的创建

int[] nums = {1, 2, 3, 4, 5};

2. 查找元素

这里展示一个简单的方法

public static int findByElement(int[] arr, int key) {
    int size = arr.length;
    // 遍历数组
    for (int i = 0; i < size; i++) {
        if (arr[i] == key) {
            return i;
        }
    }
    return -1;
}

3. 添加元素

由于数组内部的内存地址是连续的，所以我们不能像链表一样插入元素，我们必须要将指定位置的后面的元素后往后移动，扩大数组的长度，然后将数据插入。

我们这边设置这个数组是递增的。

    /**
     * @param arr
     * @param size    数组已经存储的元素数量，从1开始编号
     * @param element 待插入的元素
     * @return
     */
    public static int addByElementSequence(int[] arr, int size, int element) {
        // 1. 判断size和数组元素长度
        if (size >= arr.length) {
            return -1;
        }
        // 2.找到要插入的位置
        int index = size;
        for (int i = 0; i < size; i++) {
            if (element < arr[i]) {
                index = i;
                break;
            }
        }
        // 3.元素后移
        for (int j = size; j > index; j--) {
            arr[j] = arr[j - 1];
        }
        // 4. 插入元素
        arr[index] = element;
        return index;
    }

解释：

size >= arr.length是用于判断当前的数组空间是否满了，如果满了，就无法插入元素
int index = size;因为我们的条件是数组是有序的，比如{1,3,5}，现在我们需要插入9，如果index是0，就变成了{9,1,3,5}不符合要求，如果是index=size-1，就变成了{1,3,9,5}

4. 删除元素

这个方法和增加元素一样，该方法同样要求删除序列最前、中间、最后和不存在的元素都能有效。

    /**
     * 从数组中删除元素key
     *
     * @param arr  数组
     * @param size 数组中的元素个数，从1开始
     * @param key  删除的目标值
     */
    public static int removeByElement(int[] arr, int size, int key) {
        int index = -1;

        for (int i = 0; i < size; i++) {
            if (arr[i] == key) {
                index = i;
                break;
            }
        }

        if (index != -1) {
            for (int i = index + 1; i < size; i++) {
                arr[i - 1] = arr[i];
            }
            size--;
        }
        return size;
    }

模拟ArrayList

来自bugstack虫洞栈

1. 基本设计

由于ArrayList是一个可以自动扩充容量的数据列表，所以我们需要以下几个额外的属性。

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

ArrayList在初始化的时候，如果不指定大小，会默认初始化一个空元素，但是此时是没有默认长度的
只有第一个元素添加的时候，需要判断容量，此时需要扩容，也就是我们的默认初始容量
当初始容量不够的时候，需要进行扩容。

2. 添加元素

@Override
public boolean add(E e) {
    int minCapacity = size + 1;
    // 如果 elementData 是默认的空数组，将 minCapacity 设置为 DEFAULT_CAPACITY 或 minCapacity 和 DEFAULT_CAPACITY 的较大者
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 如果 minCapacity 大于当前数组的长度，进行扩容
    if (minCapacity > elementData.length) {
        // 计算新的容量，为当前容量的 1.5 倍
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果新容量仍然小于 minCapacity，将容量设置为 minCapacity
        if (newCapacity - minCapacity < 0) {
            newCapacity = minCapacity;
        }
        // 进行数组拷贝，将 elementData 扩容到新的容量
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    // 将元素添加到数组中，并增加 size
    elementData[size++] = e;
    return true;
}

判断当前容量和初始化容量，找出最大的一个容量。
判断当前进入的元素容量和当前数组容量的大小，如果数组容量小，就需要执行扩容，扩容到之前的1.5倍
然后将之前的数组内容拷贝到新长度的数组里面去
然后在新的数组立案插入对应的元素

3. 删除元素

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;
    // 返回删除的元素
    return oldValue;
}

确定元素后，使用System.arrayCopy拷贝数据的方式来移动数据，将需要删除的元素覆盖掉。
已经删除元素后，将这个元素设置为null，一方面是避免数据存在，另一方面是便于GC

4. 获取元素

public E get(int index) {
    return (E) elementData[index];
}

完整代码

public class ArrayList<E> implements List<E> {

    /**
     * 默认初始化容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 空元素
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * ArrayList数据缓冲区
     */
    transient Object[] elementData;

    /**
     * List集合元素的数量
     */
    private int size;

    public ArrayList() {
        // 默认给个空的元素，当开始添加元素的时候在初始化长度
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    @Override
    public boolean add(E e) {
        int minCapacity = size + 1;
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // 存在扩容
        if (minCapacity > elementData.length) {
            //
            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;
    }

    @Override
    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;
        // 返回删除的元素
        return oldValue;
    }

    @Override
    public E get(int index) {
        return (E) elementData[index];
    }

    @Override
    public String toString() {
        return "ArrayList{" +
                "elementData=" + Arrays.toString(elementData) +
                ", size=" + size +
                '}';
    }
}

/**
 * 自定义List
 * @param <E>
 */
public interface List<E> {

    boolean add(E e);

    E remove(int index);

    E get(int index);

}

测试结果：

能够实现部分ArrayList功能。

常见面试题

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

数组，链表，队列，堆栈，散列表

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

删除元素：O（N），因为从删除的元素后面的元素都需要往前移动一位

获取元素：O（1），可以通过下标来访问对应的元素

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

private static final int DEFAULT_CAPACITY = 10;

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

为之前的1.5倍

 int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1