構(gòu)建一個(gè)動(dòng)態(tài)數(shù)組

時(shí)間復(fù)雜度
隨機(jī)訪問(wèn)：O(1)
插入刪除：O(n)
動(dòng)態(tài)的實(shí)現(xiàn)是通過(guò)對(duì)容量size和數(shù)組長(zhǎng)度進(jìn)行判斷，需要擴(kuò)容時(shí)或減少容量時(shí)，通過(guò)resize（）方法將舊數(shù)組中的數(shù)據(jù)放入新數(shù)組中。

動(dòng)態(tài)數(shù)組.PNG

java代碼

public class Array<E>  {
    private E[] data;
    private int size;
    //構(gòu)造函數(shù)，傳入數(shù)組的容量capacity構(gòu)造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");
        }*/  //用于判斷是否超過(guò)數(shù)組容量
        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++;
    }

    //用于動(dòng)態(tài)數(shù)組擴(kuò)容
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0 ; i <size ; i++){
            newData[i] = data[i];
        }
        data = newData;
    }

    //根據(jù)索引修改元素
    public void set(int index,E e){
        if (index <0 || index >size) {
            throw new IllegalArgumentException("Set is fail ,Index is illegl");
        }
        data[index]=e;
    }
    //根據(jù)索引獲取元素
    public E get(int index){
        if (index <0 || index >size) {
            throw new IllegalArgumentException("Get is fail ,Index is illegal");
        }
        return data[index];
    }

    //根據(jù)元素找到索引（返回-1時(shí)輸入元素不存在數(shù)組內(nèi)）
    public int find(E e){
        for (int i=0 ; i < size ; i++){
            if(data[i].equals(e))
                return i;
            }
            return -1;
    }

    //從數(shù)組中刪除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();
    }
}