1 手写ArrayList核心源码 4年前

手写ArrayList核心源码

ArrayList是Java中常用的数据结构，不光有ArrayList，还有LinkedList,HashMap,LinkedHashMap,HashSet,Queue，PriorityQueue等等，我们将手写这些常用的数据结构的核心源码，用尽量少的代码来揭示核心原理。

下面我们来手写ArrayList的核心源码

首先我们定义一个QArrayList，不要问为什么叫QArrayList，因为我之前写过Qt，仅此而已。源码 public class<T> QArrayList,Java中的ArrayList的底层就是用一个Object[] 结构来保存数据的。我们也要定义一个Object[] 属性。

而且我们还要定义一个默认的数据的大小，以便在调用默认构造函数的情况下使用。 private final int DEFAULT_LIST_SIZE = 8;

还要定义一个 int mSize 变量，mSize 默认为0，代表下一个可以存放数据的数组的索引，代表下一个可以存放数据的数组的索引，代表下一个可以存放数据的数组的索引 重要的事情说三遍

到现在为止我们的类如下：

copy
public class QList<T> {
    //默认的数组的大小
    private final int DEFAULT_LIST_SIZE = 8;

    //存放数据的地方
    private Object[] mData;

    //下一个可以存放数据的当前数组的索引
    private int mSize;

    ......
}

好了，存放数据的数组也有了，下一个可以存放数据的当前的数组的索引也有了 ArrayList 底层是用数组存放数据，那么会有一个问题，如果此时数组满了我们再往里面存放数据的时候，怎么办呢？ArrayList是再新建一个数组，新数组的大小是原来数组大小的2倍，那么我们也这样做。

此时，我们实现 add,get,remove,resize等这几个核心方法，QArrayList完整的代码如下 ：

copy
public class QArrayList<T> {
    //默认的数组的大小
    private final int DEFAULT_LIST_SIZE = 8;

    //存放数据的地方
    private Object[] mData;

    //下一个可以存放数据的当前数组的索引
    private int mSize;

    public QArrayList() {
        //new 一个数组，用来存放
        mData = new Object[DEFAULT_LIST_SIZE];

        //下一个可以存放数据的当前数组的索引为0
        mSize = 0;
    }

    public QArrayList(int capacity){
        if(capacity <= 0 || capacity > Integer.MAX_VALUE){
            throw new RuntimeException("invalid capacity");
        }

        mData = new Object[capacity];
        mSize = 0;
    }

    //返回当时数组的已经存放了多少个元素
    public int size() {
        return mSize;
    }

    //返回数组的总大小，其实这个接口没有必要对外提供，这里我们只是为了演示用
    public int capacity() {
        return mData.length;
    }

    //添加一个元素
    public void add(T e) {
        //规定不允许添加一个空元素
        if(e == null){
            return;
        }

        //如果当前数组已经满了，扩容为原来数组的2倍
        if (mSize >= mData.length) {

            //扩容
            resize();
        }

        //将添加的元素添加到数组中
        mData[mSize] = e;

        //同时 mSize++ 指向下一个可以存放数据的位置
        mSize++;
    }

    //获取指定位置的元素，如果position不合法，直接抛出异常
    //这样做是有必要的，我们提供的是一个库
    // 直接抛出异常让使用知道用错了，没有必要 return null
    // 因为这是个库，不是业务，就算return null，也是业务层的事
    public T get(int position) {
        if (position < 0 || position >= mData.length) {
            throw new RuntimeException("position is invalid");
        }

        // position 大于 mSize 也没有关系，因为也是返回null，证明没有获取到
        return (T) mData[position];
    }

    //删除指定位置的元素
    public T remove(int position) {
        //和上面一样，位置不合法直接抛出异常
        if (position < 0 || position >= mData.length) {
            throw new RuntimeException("position is invalid");
        }

        //把当前要删除的元素保存下来，最后返回要删除的元素
        T e = (T) mData[position];

        //删除后，把后面的所有元素都往前移位
        for (int i = position + 1; i < mData.length; i++) {
            mData[i - 1] = mData[i];
        }

        //别忘了 mSize 要 --
        mSize--;

        //返回删除的元素
        return e;
    }

    //删除指定的元素
    public boolean remove(T e) {
        //因为数组可能没有满，如果删除的是null，没有必要，我们不允许
        if (e == null) {
            return false;
        }

        //找到删除元素的位置
        int position = -1;
        for (int i = 0; i < mData.length; i++) {
            if (e == mData[i] || e.equals(mData[i])) {
                position = i;
                break;
            }
        }

        //没有找到就返回
        if (position == -1) {
            return false;
        }

        //删除
        return remove(position) != null;
    }

    //扩容,我们都以2倍的容量扩容
    private void resize() {
        Object[] old = mData;
        mData = new Object[mData.length * 2];
        for (int i = 0; i < old.length; i++) {
            mData[i] = old[i];
        }

        old = null;
    }
}

注释都有相关的解释 我们来测试,测试代码如下：

copy
public static void main(String[] args) {
        QArrayList<String> list = new QArrayList<>();
        list.add("tom");
        list.add("jim");
        list.add("lilei");
        list.add("hanmeimei");

        System.out.println("list.get(2)=" + list.get(2));
        System.out.println("list.size()=" + list.size());
        for (int i = 0; i < list.size(); i++) {
            System.out.println("list.get(" + i + ") = " + list.get(i));
        }

        System.out.println("=======================");
        System.out.println("演示删除操作");
        list.remove("jim");

        for (int i = 0; i < list.size(); i++) {
            System.out.println("list.get(" + i + ") = " + list.get(i));
        }
    }

输出如下： list.get(2)=lilei list.size()=4 list.get(0) = tom list.get(1) = jim list.get(2) = lilei list.get(3) = hanmeimei ============ 演示删除操作 list.get(0) = tom list.get(1) = lilei list.get(2) = hanmeimei

但是最重要的扩容功能还没有演示，下面是扩容演示的测试代码：

copy
public static void main(String[] args) {
        //新建一个只有2个元素的数组
        QArrayList<String> list = new QArrayList<>(2);

        //打印出扩容后的容量
        System.out.println("扩容前 ： list.capacity()=" + list.capacity());

        //我们添加了4个元素
        list.add("tom");
        list.add("jim");
        list.add("lilei");
        list.add("hanmeimei");

        //打印出扩容后的容量
        System.out.println("扩容后 ： list.capacity()=" + list.capacity());

        //打印
        for (int i = 0; i < list.size(); i++) {
            System.out.println("list.get(" + i + ") = " + list.get(i));
        }
    }

输出如下：

扩容前 ： list.capacity()=2 扩容后 ： list.capacity()=4 list.get(0) = tom list.get(1) = jim list.get(2) = lilei list.get(3) = hanmeimei

可以看到，我们新建了一个底层只有2个元素的数组，但是我们添加了4个元素，我们打印出扩容后的数组的容量是 4 ，可见我们的扩容机制是没有问题的。

以上就是QArrayList的核心原理，我们下节手写LinkedList的核心原理