动态数组扩容与缩容

想必大家都知道ArrayList的底层使用数组来实现的。今天我们就写个简易版的来实现这一功能。

首先我们使用泛型 E 标识元素类型,以容纳世间万物。

size 表示数组中的实际元素个数;
构造分为无参构造和一个传递容器大小的有参构造。无参构造调用另一构造,初始默认大小为10
这边需要注意的是:
------------ 泛型类的数组 我们不能直接初始化为 E data = new E[capacity],jdk不支持,需要使用一点特殊手段,
-------------- 那就是将Object数组强转成 E类型的数组 ,E data = ( E[] )new Object[capacity]
在这里插入图片描述

接下来我们需要几个基础的方法
isEmpty 判断容器是否为空
getCapacity 得到容器的体积
getSize 得到容器的实际元素数目
在这里插入图片描述
接下来 我们需要实现往数组中添加元素
往指定位置添加元素,如果index小于0 或者index 大于数组的实际数目(因为如果数组只有{1,2},size=2,index 为{0,1},我们不可能在index = 3的情况下插入元素),所以手动抛出异常。
如果我们插入的元素大于了这个数组初始化时的数组大小,那么我们需要进行扩容的操作。
之后在index后面的元素,整体向后挪 1个单位
在这里插入图片描述
扩容或者缩容我们需要使用 private 方法,因为我们不希望外部能进行改变。
在这里插入图片描述
那么在首末位置添加元素的方法也就出来了

在这里插入图片描述
在删除元素的时候,我们为了不浪费开辟出来的空间,所以我们往往也需要缩容的操作。
在这里插入图片描述
如果实际元素小于等于该容器体积的1/4 ,我们需要将其缩容为原来的1/2
但是前提是缩容成原先的1/2不能后数组体积不能为0
在这里插入图片描述

很多人有疑问,为什么这边是1/4呢,而不是1/2
因为我们可能会遇到这种操作,remove元素的时候触发缩容,然后add元素又进行了扩容,然后又去调remove方法,又触发缩容…往复循环,这样无疑是个很差的算法,所以我们使用1/4 就可以避免这一问题了。

下面贴下完整的代码:

package com.jodoll.mall.notify.collection;


/**
 * @program:com.jodoll.mall.notify.collection
 * @fileName:Array
 * @author:ccl
 * @createTime:2019-05-22:15:52
 */
public class Array<E> {
    E data[];
    private int  size;//实际元素个数

    public Array() {
        this(10);
    }

    public Array(int capacity) {
        data = (E[]) new Object[capacity];
    }

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

    public void addLast(E e) {
        addElement(size, e);
    }

    public void addElement(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("failed to add indexOutException");
        }

        // 进行扩容操作
        reSize(size);

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

    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("failed to remove indexOutException");
        }

        E element = data[index];
        for (int i = index; i < size -1;i++ ) {
            data[i] = data[i+1];
        }
        size--;
        reSize(size);
        return element;
    }

    public boolean isEmpty() {
        return size == 0;
    }
    // 获取容器体积
    public int getCapacity() {
        return data.length;
    }

    // 获取数组实际容积
    public int getSize() {
        return size;
    }

    private void reSize(int size) {
        //扩容
        if (size + 1 > data.length) {
            E newData[] = (E[]) new Object[2 * size];
            for (int i = 0; i < size; i++) {
                newData[i] = data[i];
            }
            data = newData;
        }
        // 缩容
        if (size <= data.length / 4 && data.length / 2 != 0) {
            E newData[] = (E[]) new Object[data.length / 2];
            for (int i = 0; i < size; i++) {
                newData[i] = data[i];
            }
            data = newData;
        }

    }
}

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐