线性结构--数组(Array)

数组是最为常见也是最简单的数据结构之一，本文通过2次封装来一步一步实现数组的功能，来了解与熟悉这个最基本的数据结构

初始化

public class Array<E> {
    private int size;
    private E[] data;

    // 构造函数，传入数组的容量capacity构造Array
    public Array(int capacity){
        data = (E[]) new Object[capacity];
        size = 0;
    }
    // 无参数的构造函数，默认数组的容量capacity=10
    public Array(){
        this(10);
    }

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

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

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

添加元素

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

    // 在index索引的位置插入一个新元素e
    public void add(int index,E e){
        if(size == data.length)
            throw new IllegalArgumentException("Add 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++;
    }

• 在add函数中通过for循环，将数据从最后一个开始一个一个往后挪一位，这样做的目的是讲index这个位置空出来最终插入需要添加的元素

• 这里我们的数组只能实现固定的长度，当添加超过规定长度时会抛出异常，不用担心接下来会实现动态扩容和缩减功能

获取和修改元素

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

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

包含，搜索和删除

    public  E removeFirst(){
        return remove(0);
    }
    // 从数组中删除最后一个元素, 返回删除的元素
    public E removeLast(){
        return remove(size-1);
    }
    // 从数组中删除index位置的元素, 返回删除的元素
    public E remove(int index){
        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");

        E e = data[index];
        for (int i = index; i <=data.length; i++) {
            data[i] = data[i+1];
        }
        size--;
        data[size] = null;
        return e;
    }

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

    // 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
    public int find(E e){
        for (int i = 0; i < data.length; i++) {
            if (data[i].equals(e)) {
                return I;
            }
        }
        return -1;
    }
    // 查找数组中是否有元素e
    public boolean contain(E e){
        for (E datum : data) {
            if (datum.equals(e)) {
                return true;
            }
        }
        return false;
    }

• 注意remove中最后将data[size]设为null

动态数组(动态扩容和缩容)与复杂度震荡

   // 在index索引的位置插入一个新元素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)
            resetData(size*2);

        for (int i = 0; i < data.length; i++) {
            data[index + 1] = data[I];
        }

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

    // 从数组中删除index位置的元素, 返回删除的元素
    public E remove(int index){
        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");

        E e = data[index];
        for (int i = index; i < data.length; i++) {
            data[i] = data[i+1];
        }
        size--;
        if (size==data.length/4) {
            resetData(data.length/2);
        }
        return e;
    }

    // 将数组空间的容量变成newCapacity大小
    public void resetData(int newCapacity){
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < sze; i++) {
            newData[i] = data[I];
        }
        data = newData;
    }

• resetData方法传入需要的容量，并新建数组newData，通过循环将之前data的数据复制到newData中。最后将data地址指到新建的newData。而老数组由于没有了指向，最终会被jvm回收

• add函数中，当size达到容量界限时扩容到现在的2倍。而remove中，当size为容量的¼时,可能同学们都有疑问这里缩容条件为什么不是½呢？这里就涉及到一个效率问题，举例：假设缩容条件为½

Aarry array = new Array(5);
array.addLast(1);
array.addLast(2);
array.addLast(3);

size为3，容量为5，当我们再次添加数据：

array.addLast(4);

此时该操作方法的时间复杂度时O(1),然而当我们再次array.addLast时由于有了扩容操作resetData,此时时间复杂度为O(n)容量变为10。如果此时进行一个removeLast，由于满足了缩容条件½,会再次调用resetData此操作又是一个时间复杂度为O(n)的操作。如果一个操作反复在这个条件之间操作，就会极大的降低操作效率，这种一个时间复杂度O(1)的操作变为O(n)的操作又叫做--复杂度震荡。如果此时缩容条件为四分之一则可以有效的避免这种情况