（一）数据结构之数组

简介

  在计算机科学中，数组数据结构（英语：array data structure），简称数组（英语：Array），是由相同类型的元素（element）的集合所组成的数据结构，分配一块连续的内存来存储。利用元素的索引（index）可以计算出该元素对应的存储地址。(维基百科)

  从以上概念可以看到数组具有：线性的、索引值、元素、长度等特点，我们也可以思维扩散一下，数组应该可以 CRUD（增删改查）元素，也可以更改数组长度（所占内存大小）。

设计思路

  若要自己实现一个数组，我们考虑一些问题即可：

• 数组的容量大小应该给多少？
  • 提供默认值或者允许初始化时指定？
• 如何知道数组中元素的存储情况？
  • 如何获取数组中的元素个数？
  • 如何知道数组中的元素个数是否为空？
  • 是否需要提供一个变量代表元素个数？
  • 在往数组中增删元素时是否需要与元素个数进行同步？
  • 如何理解数组元素个数和容量大小的关系？
• 在数组中执行获取元素操作是否需要提供一些特殊的处理方法？
  • 比如获取指定索引位置的元素？
  • 比如获取指定元素的索引下标位置？有则返回，无则返回特殊值？
  • 比如判断某个元素在数组中是否存在？
• 在数组中执行增删元素操作时能否根据位置提供一些特殊的处理方法？
  • 比如在数组的第一个索引位置增加删除元素？
  • 比如在数组的最后一个索引位置增加删除元素？
  • 比如在数组的指定索引位置增加删除元素？若插入或删除到已有两元素之间数组元素是否需要进行移动？
• 在数组中执行增删元素操作时进行一些额外的处理？
  • 比如增加元素时数组容量不够时是否需要进行扩容处理？扩容操作时应当设置为原容量的什么数量级比较合适？
  • 比如删除元素时数组容量较大时是否需要进行缩容处理？缩容操作时应当设置为原容量的什么数量级比较合适？
  • 比如删除元素时返回一个结果？成功失败或删除的值？
• 支持泛型数组？
• 支持对数组索引元素的排序？自定义排序规则？
• 支持与不同数据结构的混合搭配使用？链表数组？红黑树数组？

  在实现时，我们不需要一开始那么多问题，可以先考虑一个基础版，后续慢慢优化即可。

代码实现

  代码实现时分几个版本实现即可：

• v1：基础版的单类型数组
• v2：支持存储多种类型的泛型数组
• v3：支持扩容的动态数组

v1：单类型数组

  在 v1 版本中，我们实现一个单类型的基础版本的 int 型数组即可：

public class Array {
    private int[] array;
    private int size;// 数组元素个数,也可代表数组当前索引

    /**
     * 无参时初始数组容量为 10
     */
    public Array() {
        this(10);
    }

    /**
     * @param capaCity  数组容量
     */
    public Array(int capaCity) {
        this.array = new int[capaCity];
    }


    // 获取数组中的元素个数
    public int size() {
        return size;
    }

    // 获取数组容量
    public int getCapaCity() {
        return array.length;
    }

    // 判空
    public boolean isEmpty() {
        return size == 0;
    }

    // 在指定位置增加元素
    public void add(int index, int e) {
        // 数组元素是否已满
        if (size == array.length) {
            throw new IllegalArgumentException("Add faild,Array is null");
        }
        // 参数越界(不能为负数，也不能大于 size，因为数组元素是连续的，不能跳过空位置插入)
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add faild,Require index >= 0 and indx < size");
        }
        for (int i = size - 1; i >= index; i--) {
            array[i + 1] = array[i];
        }
        array[index] = e;
        size++;
    }

    // 在最后一个位置增加元素
    public void addLast(int e) {
        add(size, e);
    }

    // 在第一个位置增加元素
    public void addFirst(int e) {
        add(0, e);
    }

    // 获得 index 位置的元素
    public int get(int index){
        if(index < 0 || index >= size){
            throw new  IllegalArgumentException("Get failed,Index is illegal");
        }
        return array[index];
    }
    
    // 修改 index 位置的元素
    public int set(int index,int e){
        if(index < 0 || index >= size){
            throw new  IllegalArgumentException("Set failed,Index is illegal");
        }
       return array[index] = e;
    }

    // 查找数组中含有 e 元素的索引，没有该元素返回 -1
    public int find(int e){
        for (int i = 0; i < size; i++) {
            if(e == array[i]){
                return i;
            }
        }
        return -1;
    }

    // 是否含有指定元素
    public boolean contains(int e){
        for (int i = 0; i < size; i++) {
            if(array[i] == e){
                return true;
            }
        }
        return false;
    }

    // 删除指定位置的元素,返回删除的元素
    public int remove(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("delete failed,Require index >= 0 and indx < size");
        }
        int ret = array[index];
        for (int i = index + 1; i < size; i++) {
            array[i - 1] = array[i];
        }
        size--;
        return ret;

    }

    // 删除第一个位置的元素,返回删除的元素
    public int removeFirst() {
        return remove(0);
    }

    // 删除最后一个位置的元素,返回删除的元素
    public int removeLast() {
        return remove(size - 1);
    }

    // 删除数组中含有的元素
    public void removeElement(int e) {
        int index = find(e);
        if(index!=-1){
            remove(index);
        }
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array size = %d ,capacity = %d\n",size,array.length));
        res.append('[');
        for (int i = 0; i < size; i++) {
            res.append(array[i]);
            if(i != size - 1){
                res.append(',');
            }
        }
        res.append(']');
        return res.toString();
    }

v2：泛型数组

  v1 版本的数组仅仅局限于 Int 型，而 Java 语言支持泛型，那么可以进行一些改造：

public class GenericsArray<E> {
    private E[] array;
    private int size;// 数组元素个数,也可代表数组当前索引

    /**
     * 无参时初始数组容量为 10
     */
    public GenericsArray() {
        this(10);
    }

    /**
     * @param capaCity  数组容量
     */
    public GenericsArray(int capaCity) {
        this.array = (E[])new Object[capaCity];
    }


    // 获取数组中的元素个数
    public int size() {
        return size;
    }

    // 获取数组容量
    public int getCapaCity() {
        return array.length;
    }

    // 判空
    public boolean isEmpty() {
        return size == 0;
    }

    // 在指定位置增加元素
    public void add(int index, E e) {
        // 数组元素是否已满
        if (size == array.length) {
            throw new IllegalArgumentException("Add faild,Array is null");
        }
        // 参数越界
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add faild,Require index >= 0 and indx < size");
        }
        for (int i = size - 1; i >= index; i--) {
            array[i + 1] = array[i];
        }
        array[index] = e;
        size++;
    }

    // 在最后一个位置增加元素
    public void addLast(E e) {
        add(size, e);
    }

    // 在第一个位置增加元素
    public void addFirst(E e) {
        add(0, e);
    }

    // 获得 index 位置的元素
    public E get(int index){
        if(index < 0 || index >= size){
            throw new  IllegalArgumentException("Get failed,Index is illegal");
        }
        return array[index];
    }

    // 修改 index 位置的元素
    public E set(int index,E e){
        if(index < 0 || index >= size){
            throw new  IllegalArgumentException("Set failed,Index is illegal");
        }
        return array[index] = e;
    }

    // 查找数组中含有 e 元素的索引，没有该元素返回 -1
    public int find(E e){
        for (int i = 0; i < size; i++) {
            if(e.equals(array[i])){
                return i;
            }
        }
        return -1;
    }

    // 是否含有指定元素
    public boolean contains(E e){
        for (int i = 0; i < size; i++) {
            if(e.equals(array[i])){
                return true;
            }
        }
        return false;
    }

    // 删除指定位置的元素，返回删除的元素
    public E remove(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("delete failed,Require index >= 0 and indx < size");
        }
        E ret = array[index];
        for (int i = index + 1; i < size; i++) {
            array[i - 1] = array[i];
        }
        size--;
        return ret;

    }

    // 删除第一个位置的元素，返回删除的元素
    public E removeFirst() {
        return remove(0);
    }

    // 删除最后一个位置的元素，返回删除的元素
    public E removeLast() {
        return remove(size - 1);
    }

    // 删除数组中含有的元素
    public void removeElement(E e) {
        int index = find(e);
        if(index != -1){
            remove(index);
        }
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(String.format("Array size = %d ,capacity = %d\n",size,array.length));
        stringBuilder.append('[');
        for (int i = 0; i < size; i++) {
            stringBuilder.append(array[i]);
            if(i != size - 1){
                stringBuilder.append(',');
            }
        }
        stringBuilder.append(']');
        return stringBuilder.toString();
    }
}

v3：动态数组

  v1、v2 版本的数组一旦初始化容量就固定了，在实现业务的使用过程中可能会存储比较大的数据，那数组能否支持动态扩容呢？

  当然可以，我们只需要改动一点点代码，新增一个持动态扩容方法:

// 将数组指向一个新的数组（新数组长度取决于参数）
private void resize(int newCapacity) {
    E[] newArray = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        newArray[i] = array[i];
    }
    array = newArray;
}

  再将部分代码改动一下:

// 在指定位置增加元素
public void add(int index, E e) {
    // 数组元素已满将旧数组指向一个新数组（容量为旧数组2倍）
    if (size == array.length) {
        resize(2 * array.length);
    }
    // 参数越界
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("Add faild,Require index >= 0 and indx < size");
    }
    for (int i = size - 1; i >= index; i--) {
        array[i + 1] = array[i];
    }
    array[index] = e;
    size++;
}

// 删除指定位置的元素,返回删除的元素
public E remove(int index) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("delete failed,Require index >= 0 and indx < size");
    }
    E ret = array[index];
    for (int i = index + 1; i < size; i++) {
        array[i - 1] = array[i];
    }
    size--;
     // 如果数组元素个数为容量的四分之一（考虑到复杂度震荡）
     // 将该数组指向一个新的数组（容量为旧数组一半）
    if (size == array.length / 4 && array.length / 2 != 0) {
        resize(array.length / 2);
    }
    return ret;

}

时间复杂度

添加

方法	时间复杂度
addLast(e)	O(1)
addFirst(e)	O(n)
add(index,e)	O(n/2) = O(n)

  综合上面三种，则最坏情况下添加操作的时间复杂度为O(n)；还有resize操作的时间复杂度为O(n)

删除

方法	时间复杂度
removeLast(e)	O(1)
removeFirst(e)	O(n)
remove(index,e)	O(n/2)=O(n)

  综合上面三种，则最坏情况下删除操作的时间复杂度为O(n)；还有resize操作的时间复杂度为O(n)

修改

方法	时间复杂度
set(index,e)	O(1)

查询

方法	时间复杂度
get(index)	O(1)
contains(e)	O(n)
find(e)	O(n)

对比

操作	时间复杂度
增	O(n)
删	O(n)
改	已知索引 O(1)；未知索引 O(n)
查	已知索引 O(1)；未知索引 O(n)

小结

  通过本文，我们首先了解了数组的一些基本概念，其次，在我们需要自定义实现数组时，思考了一些需要注意的问题，最后，我们进行了一个具体的代码实现，并分析了不同方法执行时的时间复杂度情况。

文章信息

时间	说明
2018-12-01	初稿
2023-08-19	部分重构