数组：动态数组

构建一个动态数组

时间复杂度
随机访问：O(1)
插入删除：O(n)
动态的实现是通过对容量size和数组长度进行判断，需要扩容时或减少容量时，通过resize（）方法将旧数组中的数据放入新数组中。

动态数组.PNG

java代码

public class Array<E>  {
    private E[] data;
    private int size;
    //构造函数，传入数组的容量capacity构造Arra
    public Array(int capacity){
        data = (E[]) new Object[capacity];
        size = 0;
    }

    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 addFrist(E e){
        add(0, e);
    }

    public void add(int index,E e){
        /* if (size == data.length){
            throw new IllegalArgumentException("Array is full");
        }*/  //用于判断是否超过数组容量
        if(size == data.length)
        {
            resize(2 * data.length);
        }
       
        if (index < 0 || index > size){
            throw new IllegalArgumentException("Array is full");
        }
        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 void set(int index,E e){
        if (index <0 || index >size) {
            throw new IllegalArgumentException("Set is fail ,Index is illegl");
        }
        data[index]=e;
    }
    //根据索引获取元素
    public E get(int index){
        if (index <0 || index >size) {
            throw new IllegalArgumentException("Get is fail ,Index is illegal");
        }
        return data[index];
    }

    //根据元素找到索引（返回-1时输入元素不存在数组内）
    public int find(E e){
        for (int i=0 ; i < size ; i++){
            if(data[i].equals(e))
                return i;
            }
            return -1;
    }

    //从数组中删除index位置的元素，返回删除的元素
    public E remove(int index){
        if (index <0 || index >size) {
            throw new IllegalArgumentException("Remove is fail ,Index is illegal");
        }
            E ret = data[index];
            for(int i = index+1 ; i < size ; i++){
                data[i-1] = data[i];
            }
            size--;
            data[size] = null;// loitering objects != memory leak
            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 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();
    }
}