实现数组_3_动态数组

之前1和2都是静态数组，我们创造动态数组

package com.company;

/**
* @program: Array
* @description: 数组
* @author: Gu
* @create: 2019-04-10 22:03
**/

public class Array<E> {

   private E[] data;
   private int size;

   //初始化
   public Array(int capacity) {
       data = (E[])new Object[capacity];
       size = 0;
   }

   //无参构造函数默认最大容量为10
   public Array() {
       this(10);
   }

   //数组长度
   public int length() {
       return data.length;
   }

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

   //数组是否为空
   public boolean isEmpty() {
       return size == 0;
   }
   //向数组指定位置中添加元素
   public void add(int index, E element) {
       if (index >= data.length || index < 0) {
           throw new IllegalArgumentException("[数组索引非法]");
       }

       if (size == data.length) {
           //throw new IndexOutOfBoundsException("[数组已达到最大容量]");
           //动态数组，数组容量到达最大值时，要扩容，我们暂定为扩容2倍（与java动态数组倍数不同）
           int newCapacity = data.length * 2;
           resize(newCapacity);
       }

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

   //向数组第一个索引添加元素
   public void addFirst(E element) {
       add(0, element);
   }

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

   //根据index查找指定元素
   public E get(int index) {
       if (index < 0 || index >= size) {
           throw new IllegalArgumentException("[数组索引非法]");
       }
       return data[index];
   }

   //查找数组是否包含指定元素
   public boolean contains(E element) {
       for (E value : data) {
           if (value.equals(element)) {
               return true;
           }
       }
       return false;
   }

   //返回指定元素的索引
   public int find(E element) {
       for (int i = 0; i < size; i++) {
           if (data[i].equals(element)) {
               return i;
           }
       }
       return -1;
   }


   //修改数组元素
   public void set(int index, E element) {
       if (index < 0 || index >= size) {
           throw new IllegalArgumentException("[数组索引非法]");
       }
       data[index] = element;
   }

   //删除指定元素
   public void delete(E element) {
       int index = find(element);
       if (index == -1) {
           throw new IllegalArgumentException("[数组没有该元素]");
       }
       remove(index);
   }

   //根据索引删除元素
   public E remove(int index) {
       if (index < 0 || index >= size) {
           throw new IllegalArgumentException("[数组索引非法]");
       }
       E res = data[index];
       for (int i = index + 1; i < size; i++) {
           data[i - 1] = data[i];
       }
       size = size - 1;
       //删除内容后，我们希望向数组扩容一样，数组容量也会减少，我们假定size为1/2时，容量减半
       if (size == data.length / 4 && data.length / 2 != 0) {
           int newCapacity = data.length / 2;
           resize(newCapacity);
       }
       return res;
   }
   
   private void resize(int capacity) {
       E[] temp = (E[])new Object[capacity];
       for (int i = 0; i < size; i++) {
           temp[i] = data[i];
       }
       data = temp;
   }

   //删除第一个
   public E removeFirst() {
       return remove(0);
   }

   //删除最后一个
   public E removeLast() {
       return remove(size - 1);
   }

   //打印数组相关信息
   @Override
   public String toString() {
       StringBuffer stringBuffer = new StringBuffer();
       stringBuffer.append(String.format("数组的size : %d, 数组的capacity : %d \n", size, data.length));
       stringBuffer.append("[");
       for (int i = 0; i < size; i++) {
           stringBuffer.append(data[i]);
           if (i == size - 1) {
               stringBuffer.append("]");
               break;
           }
           stringBuffer.append(",");
       }
       return stringBuffer.toString();
   }

}

主要是增加数据和减少数据时，修改了数组容量。
测试类

package com.company;

public class Main {

    public static void main(String[] args) {

    //add()
    Array<Integer> array = new Array<>(10);
    for (int i = 0; i < 10; i++) {
        array.add(i, i + 1);
    }
    System.out.println(array);
    //[1,2,3,4,5,6,7,8,9,10]

    //addFirst()
    array.addFirst(0);
    System.out.println(array);
    //[0,1,2,3,4,5,6,7,8,9,10]

    //removeFirst
    array.removeFirst();
    System.out.println(array);
    }
}

这里使用均摊分析简单说明下扩容或者减半时的时间复杂度。
假如数组capacity = 4， size = 4， 这时我们增加数据时，会触发resize（）操作，使得capacity = 8，并且把老数组的数据复制到新数组。
此时我们统计下操作步骤：5次add操作 + 4次复制操作 = 9
我们均摊下时间复杂度： 9 / n = 2; 此时n = 4；是常数O（1）；
数组容量减半也是如此。

---

还有复杂度的震荡问题
我们可以看一张图：

复杂度的震荡

数组capacity = 10, size = 10，我们增加一个元素 ，此时capacity = 20。 接着 我们减去一个元素，capacity = 10，这些都符合逻辑。但是此时我们发现每做一次操作的时间复杂度为O（n）。
上述现象就是复杂度震荡问题。
产生问题的原因在于，每次size = capacity / 2 时，我们都会减半capacity。 现在我们采取新的策略，只有增加时才会扩容，减少size = capacity / 2 时我们不急于减半，只有当size = capacity / 4，我们才将capacity = capacity/2；修改后的代码如下

//根据索引删除元素
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("[数组索引非法]");
        }
        E res = data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size = size - 1;
        //删除内容后，我们希望向数组扩容一样，数组容量也会减少，我们假定size为1/2时，容量减半
        if (size == data.length / 4 && data.length / 2 != 0) {
            int newCapacity = data.length / 2;
            E[] temp = (E[])new Object[newCapacity];
            for (int i = 0; i < size - 1; i++) {
                temp[i] = data[i];
            }
            data = temp;
        }
        return res;
    }