ArrayList 实现与思考

自定义ArrayList

1. List 接口 (PS:考虑到ArrayList的应用场景自定义的接口与JDK中有所区别, 如contains方法并不适合用该数据结构故不自此定义与实现)

public interface List<E> {

    boolean isEmpty();

    int capacity();

    E get(int index);

    void remove(E e);

    E removeAt(int index);

    void add(E e);

    int size();
}

2. ArrayList 实现

public class ArrayList<E> implements List<E> {

    private E[] data;
    private int size;

    public ArrayList() {
        this(8);
    }

    public ArrayList(int capacity) {
        if (capacity <= 0)
            throw new IllegalArgumentException("capacity must be > 0");

        data = (E[]) new Object[capacity];
        size = 0;
    }

    @Override
    public int capacity() {
        return data.length;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    public void set(int index, E e) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("index out of bound : " + index);
        data[index] = e;
    }

    @Override
    public E get(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("index out of bound : " + index);

        return data[index];
    }

    @Override
    public void remove(E e) {
        int index = 0;
        while (index < size) {
            if (e.equals(data[index]))
                removeAt(index);
            else
                index++;
        }
    }

    @Override
    public E removeAt(int index) {

        if (index < 0 || index >= size)
            throw new IllegalArgumentException("index out of bound : " + index);

        E ret = data[index];
        for (int i = index; i < size; i++) {
            if (i + 1 < size)
                data[i] = data[i + 1];
            data[i + 1] = null;
        }
        size--;

        reduceIfNecessary(size);

        return ret;
    }
    // 必要的时候缩容为原来的 1/2
    private void reduceIfNecessary(int size) {
        // 此处的 1/3是为了防止复杂度震荡, 只要不是且小于1/2就可以了
        if (size <= data.length / 3) {
            E[] newData = (E[]) new Object[data.length >> 1];
            for (int i = 0; i < this.size; i++) {
                newData[i] = data[i];
            }
            data = newData;
        }
    }

    @Override
    public void add(E e) {
        growIfNecessary(size + 1);
        data[size] = e;
        size++;
    }
    // 必要时扩容为原来的 2 倍
    private void growIfNecessary(int newCapacity) {
        if (newCapacity < data.length) {
            return;
        }
        // capacity grow
        E[] newData = (E[]) new Object[data.length << 1];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < size; i++) {
            builder.append(data[i]).append(" -> ");
        }
        builder.append("| element size is : ").append(size);
        builder.append(" , and capacity is : ").append(data.length);
        return builder.toString();
    }
}

JDK ArrayList Demo的思考

先添加100个元素,在删除前90个元素观察容量的变化

public class ListMain {
    public static void main(String[] args) throws Exception {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            list.add(i);
            System.out.println("添加元素: " + i + ", 数组容量:" + getListCapacity(list));
        }

        for (int i = 0; i < 90; i++) {
            // 传入对象Integer 删除的是对应的对象, 如果传入的是 int 删除的是对应的index的数据
            list.remove(Integer.valueOf(i));
            System.out.println("删除元素: " + i + ", 数组容量:" + getListCapacity(list) + ", 剩余元素个数: " + list.size());
        }
    }

    /**
     * 获取容量
     */
    private static int getListCapacity(ArrayList<Integer> list) throws NoSuchFieldException, IllegalAccessException {
        Field elementData = list.getClass().getDeclaredField("elementData");
        elementData.setAccessible(true);
        Object[] elements = (Object[]) elementData.get(list);
        return elements.length;
    }
}

运行结果:

添加元素: 0, 数组容量:10

...

添加元素: 10, 数组容量:15

...

添加元素: 16, 数组容量:22

... ...

添加元素: 99, 数组容量:109

删除元素: 0, 数组容量:109, 剩余元素个数: 99

...

删除元素: 89, 数组容量:109, 剩余元素个数: 10

JDK ListDemo 运行结果表明(JDK 版本 1.8.0_171)

1. List 的remove()方法不会引起容量的变化(不会缩容), 类似于demo中的操作可能造成空间的浪费(PS:可能没有这么无聊的场景,但确实是个问题)
2. remove(Object e), 方法是比较坑die的,原因在于该方法有一个重载方法remove(int index),如果List中存入的是Integer类型时,调用的时候需要小心, 在我的demo中如果去掉Integer.valueOf()回报异常: java.lang.IndexOutOfBoundsException: Index: 50, Size: 50