数组是一组相关数据的集合，一个数组实际上就是一连串的变量，数组按照使用可以分为一维数组、二维数组、多维数组。

简单回顾下Java中的数组使用方法：

public class Main {
    public static void main(String[] args) {
        // 创建一个指定长度的数组
        int[] arr = new int[20];
        // 数组遍历
        for (int i = 0, len = arr.length; i < len; i++)
            arr[i] = i;

        // 创建数组并初始化
        int[] scores = new int[]{100, 99, 98};
        // 数组遍历
        for (int i = 0, len = scores.length; i < len; i++)
            System.out.println(scores[i]);

        // 数组遍历
        for (int score: scores)
            System.out.println(score);

        // 修改数组中的值
        scores[0] = 99;

        for (int score: scores)
            System.out.println(score);
    }
}

数组最大的优点是可以快速查询。我们可以通过索引直接访问数组中的元素。如将上述代码中的scores[0]的值设置成99.

下面我们来简单实现下数组中常用的方法，如增、删、改、查。

public class Array {
    private int[] data;
    // 存放数组中有多少个有效元素
    private int size;

    // 有参数的构造函数，用传入的capacity构造数组
    public Array(int capacity) {
        data = new int[capacity];
        size = 0;
    }

    // 无参数的构造函数，默认数组的容量capacity=10
    public Array() {
        this(10);
    }

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

    // 获取数组中的容量
    public int getCapacity() {
        return data.length;
    }

    // 数组是否为空
    public boolean isEmpty() {
        return size ==  0;
    }

    // 向数组末尾添加元素
    public void addLast(int e) {
        add(size, e);
    }

    public void addFirst(int e) {
        add(0, e);
    }

    // 在指定位置插入特定元素
    public void add(int index, int e) {
        if (size == data.length)
            throw new IllegalArgumentException("AddLast failed. Array is full.");

        if (index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");

        for (int i = size - 1; i >= index; i--)
            data[i + 1] = data[i];

        data[index] = e;
        size++;
    }

    public E remove(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        E res = data[index];
        for (int i = index + 1; i < size; i++)
            data[i - 1] = data[i];

        size--;
        data[size] = null;

        return res;
    }

    // 删除数组中的第一个元素
    public int removeFirst() {
        return remove(0);
    }

    // 删除数组中的最后一个元素
    public void removeLast() {
        remove(size - 1);
    }

    // 从数组中删除某个元素
    public void removeEle(int e) {
        int index = findIndex(e);

        if (index != -1)
            remove(index);
    }

    // 获取数组中指定位置的值
    public int get(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed. Index is illegal.");

        return data[index];
    }

    // 修改指定位置的值
    public void set(int index, int e) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed. Index is illegal.");

        data[index] = e;
    }

    // 数组中是否包含某个元素
    public boolean contains(int e) {
        for (int i = 0; i < size; i++)
            if (data[i] == e)
                return true;
        return false;
    }

    // 查找特定元素所在的索引
    public int findIndex(int e) {
        for (int i = 0; i < size; i++)
            if (data[i] == e)
                return i;
        return -1;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
        res.append("[");

        for (int i = 0; i < size; i++) {
            res.append(data[i]);
            if (i != size-1)
                res.append(",");
        }

        res.append("]");
        return res.toString();
    }
}

测试封装的数组方法：

public class Main {
    public static void main(String[] args) {
        Array arr = new Array(30);

        for (int i = 0; i < 10; i++)
            // 数组末尾依次添加
            arr.addLast(i);

        System.out.println(arr);
        /*
        输出
        Array: size = 10, capacity = 30
        [0,1,2,3,4,5,6,7,8,9]
        */

        // 向索引1的位置插入20
        arr.add(1, 20);
        System.out.println(arr);
        /*
        Array: size = 11, capacity = 30
        [0,20,1,2,3,4,5,6,7,8,9]
        */

        arr.addFirst(-1);
        System.out.println(arr);
        /*
        输出
        Array: size = 12, capacity = 30
        [-1,0,20,1,2,3,4,5,6,7,8,9]
        */

        arr.remove(2);
        System.out.println(arr);
        /*
        Array: size = 11, capacity = 30
        [-1,0,1,2,3,4,5,6,7,8,9]
        */

        arr.removeEle(-1);
        System.out.println(arr);
        /*
        Array: size = 10, capacity = 30
        [0,1,2,3,4,5,6,7,8,9]
        */

        arr.removeFirst();
        System.out.println(arr);
        /*
        Array: size = 9, capacity = 30
        [1,2,3,4,5,6,7,8,9]
        */
    }
}

泛型类

上面我们所实现的数组方法只适用于整型，然而实际开中数组中不仅仅只能存放整型还能存放其他类型，如字符串、bool、对象等等。下面我将上面封装的数组类进行修改，让它可以支持其他类型，这里我们需要使用到泛型，具体代码如下：

public class Array<E> {
    private E[] data;
    // 存放数组中有多少个有效元素
    private int size;

    // 有参数的构造函数，用传入的capacity构造数组
    public Array(int capacity) {
        //data = new E[capacity]; 不支持new一个泛型数组
        data = (E[])new Object[capacity];
        size = 0;
    }

    // 无参数的构造函数，默认数组的容量capacity=10
    public Array() {
        this(10);
    }

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

    // 获取数组中的容量
    public int getCapacity() {
        return data.length;
    }

    // 数组是否为空
    public boolean isEmpty() {
        return size ==  0;
    }

    // 向数组末尾添加元素
    public void addLast(E e) {
        add(size, e);
    }

    public void addFirst(E e) {
        add(0, e);
    }

    // 在指定位置插入特定元素
    public void add(int index, E e) {
        if (size == data.length)
            throw new IllegalArgumentException("AddLast failed. Array is full.");

        if (index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");

        for (int i = size - 1; i >= index; i--)
            data[i + 1] = data[i];

        data[index] = e;
        size++;
    }

    public E remove(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        E res = data[index];
        for (int i = index + 1; i < size; i++)
            data[i - 1] = data[i];

        size--;
        data[size] = null;

        return res;
    }

    // 删除数组中的第一个元素
    public E removeFirst() {
        return remove(0);
    }

    // 删除数组中的最后一个元素
    public E removeLast() {
        return remove(size - 1);
    }

    // 从数组中删除某个元素
    public void removeEle(E e) {
        int index = findIndex(e);

        if (index != -1)
            remove(index);
    }

    // 获取数组中指定位置的值
    public E get(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed. Index is illegal.");

        return data[index];
    }

    // 修改指定位置的值
    public void set(int index, E e) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed. Index is illegal.");

        data[index] = e;
    }

    // 数组中是否包含某个元素
    public boolean contains(E e) {
        for (int i = 0; i < size; i++)
            if (data[i].equals(e))
                return true;
        return false;
    }

    // 查找特定元素所在的索引
    public int findIndex(E e) {
        for (int i = 0; i < size; i++)
            if (data[i].equals(e))
                return i;
        return -1;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
        res.append("[");

        for (int i = 0; i < size; i++) {
            res.append(data[i]);
            if (i != size-1)
                res.append(",");
        }

        res.append("]");
        return res.toString();
    }
}

测试基本类型

public class Main {
    public static void main(String[] args) {
        Array<Integer> arr = new Array<Integer>(30);

        for (int i = 0; i < 10; i++)
            // 数组末尾依次添加
            arr.addLast(i);

        System.out.println(arr);
        /*
        输出
        Array: size = 10, capacity = 30
        [0,1,2,3,4,5,6,7,8,9]
        */
    }
}

测试引用类型

public class Student implements Comparable<Student>{
    private String name;
    private int score;

    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }

    @Override
    public  int compareTo(Student another) {
        return another.score - this.score;
    }

    @Override
    public boolean equals(Object student) {
        if (this == student)
            return true;
        if (student == null)
            return false;
        if (this.getClass() != student.getClass())
            return false;

        Student another = (Student) student;
        return this.score == another.score;
    }

    @Override
    public String toString() {
        return String.format("Student(name: %s, score: %d)", name, score);
    }

    public static void main(String[] args) {
        Array<Student> arr = new Array<Student>();

        arr.addLast(new Student("fang", 100));
        arr.addLast(new Student("fei", 100));
        arr.addLast(new Student("yue", 100));

        System.out.println(arr);
        /*
        输出
        Array: size = 3, capacity = 10
        [Student(name: fang, score: 100),Student(name: fei, score: 100),Student(name: yue, score: 100)]
        */
    }
}

动态数组

上面我们实现的Array类实际还是Java的一个静态数组，它的容量是有限的。当我们使用数组时一开始可能无法预估要使用多大的空间，如果容量开的太大就会浪费，如果开的太小的话空间有可能不够用。有没有容量可伸缩的

public class Array<E> {
    // ...

    // 在指定位置插入特定元素
    public void add(int index, E e) {
        if (index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");

        if (size == data.length)
            resize(2 * data.length);

        for (int i = size - 1; i >= index; i--)
            data[i + 1] = data[i];

        data[index] = e;
        size++;
    }

    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];

        for (int i = 0; i < size; i++)
            newData[i] = data[i];

        data = newData;
    }

    // ...
}

测试

public class Main {
    public static void main(String[] args) {
        Array<Integer> arr = new Array<Integer>();

        for (int i = 0; i < 10; i++)
            // 数组末尾依次添加
            arr.addLast(i);

        System.out.println(arr);
        arr.addLast(10);
        System.out.println(arr);
        /*
        输出 
        Array: size = 10, capacity = 10
        [0,1,2,3,4,5,6,7,8,9]

        Array: size = 11, capacity = 20
        [0,1,2,3,4,5,6,7,8,9,10]
         */
    }
}

缩容

public class Array<E> {
  // ...

  public E remove(int index) {
      if (index < 0 || index >= size)
          throw new IllegalArgumentException("Remove failed. Index is illegal.");

      E res = data[index];
      for (int i = index + 1; i < size; i++)
          data[i - 1] = data[i];

      size--;
      data[size] = null;

      if(size == data.length / 2)
          resize(data.length / 2);

      return res;
  }

  // ...
}

测试

public class Main {
    public static void main(String[] args) {
        Array<Integer> arr = new Array<Integer>(4);

        for (int i = 0; i < 4; i++)
            arr.addLast(i);

        System.out.println(arr);

        arr.removeLast();
        arr.removeLast();

        System.out.println(arr);

        /*
        输出：
        Array: size = 4, capacity = 4
        [0,1,2,3]

        Array: size = 2, capacity = 2
        [0,1]
        */
    }
}

复杂度分析

添加操作

addLast(e) -> O(1)

addFirst(e) -> O(n)

add(index, e) -> O(n)

添加操作综合来看是一个O(n)级别的操作，虽然addLast(e)是O(1)级别的，但是在算法复杂度分析时通常看最坏的情况的。

删除操作

removeLast(e) -> O(1)

removeFirst(e) -> O(n)

remove(index, e) -> 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)

增删如果只对最后一个操作时间复杂度应该是O(1)，这里说是O(n)，是因为有resize，resize是O(n)的

均摊时间复杂度

我们不可能每次添加元素的时候都触发resize操作，

假设当前capacity=8，并且每一次添加操作都使用addLast，当添加到第9个元素时数组才满，这个时候需要进行resize操作，要将之前的8个元素全部复制到新的数组中，然后再添加，这样前后总共进行了17次操作。平均来看相当于每次addLast操作进行了2次基本操作。

推而言之，假设capacity=n，要进行n+1次addLast才会触发一次resize，总共进行了2*n+1次基本操作。这样均摊计算removeLast和addLast的时间复杂度为O(1)

复杂度震荡

假设一个数组它的capacity为n，并且已经装满了元素，此时调用addLast操作就要扩容，之后马上进行removeLast操作，此时会触发缩容操作。这时我们又调用了一次addLast操作，此时又要扩容，之后又调用removeLast操作，此时又会缩容，如此反复。

出现问题的原因在于removeLast时resize过于着急

假设数组是满的，当调用addLast后会扩容，当调用removeLast时先不急着立马缩容，看看后续是否还有removeLast操作，当删除到数组的四分之一，此时我们再缩容，缩容只缩容数组的二分之一，这样当我们再添加元素时也不用立马触发扩容操作。

修改Array的remove方法如下

public class Array<E> {
  // ...
  public E remove(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        E res = data[index];
        for (int i = index + 1; i < size; i++)
            data[i - 1] = data[i];

        size--;
        data[size] = null;

        if(size == data.length / 4 && data.length / 2 != 0)
            resize(data.length / 2);

        return res;
    }
  // ...
}