1 手写ArrayList核心源码

九路 发表时间: 2020-11-02 10:33 阅读:45 收藏:0

手写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代表下一个可以存放数据的数组的索引代表下一个可以存放数据的数组的索引代表下一个可以存放数据的数组的索引 重要的事情说三遍

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

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完整的代码如下 :

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;
    }
}

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

    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

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

 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的核心原理

收藏
评论区
发表评论