1 手写ArrayList核心源码

九路 等级 862 1 1

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

收藏
评论区

相关推荐

List集合
Java的List集合 一、ArrayList 1.插入 java / 在元素序列尾部插入 / public boolean add(E e) { // 1. 检测是否需要扩容 ensureCapacityInternal(size 1); // Increments modCount // 2. 将新元素插入序列尾
[C#]ArrayList、string、string[]之间的转换
1、ArrarList 转换为 string\[\] :  ArrayList list new ArrayList();  list.Add("aaa");  list.Add("bbb");  string\[\] arrString (string\[\])list.ToArray(typeof( string)) ;2、string\[\] 转换
我丢,去面试初级Java开发岗位,被问到泛型?
1、泛型的基础概念 1.1 为什么需要泛型 c List list new ArrayList();//默认类型是Object list.add("A123"); list.add("B234"); list.add("C345"); System.out.println(list);
JDK1.8stream根据对象的某一字段去重
1 List list = new ArrayList<>(); 2 List listByName = list.stream().filter(distinctByName(item -> item.getName())).collect(Collectors.toList()); 3 private static <T>
JSON的使用
一.json常用转换方法 ============ 1.list ====== List list = new ArrayList(); list.add("first"); list.add("second"); JSONArray jsonArray2 = JSONArray.fromObject(list);
Java 并发数据结构
\[TOCM\] 因为Java提供了一些非线程安全的数据结构如HashMap,ArrayList,HashSet等。所有在多线程环境中需要使用支持并发访问操作的数据结构。 #### 并发List Vector,CopyOnWriteArrayList 是线程安全的List。ArrayList是线程不安全的。如果一定要使用,需要: `Collection
Java 笔记
*  动态数组 ArrayList<String> List = new ArrayList<String>(); //定义动态数组 List.add(temp); //添加字符串 List<Integer> ret = new ArrayList<Integer>(); ret.add(i+1);
Java 集合框架
![](https://oscimg.oschina.net/oscnet/d7eef0099a6d647cbc108bb7d3406f1e1d5.jpg) **List 不唯一、有序;Set 唯一、无序。** Vector 也实现了 List 接口,实现了 ArrayList 的所有操作。主要区别:Vector 线程安全操作相对较慢,ArrayList
Java入门第五篇:Java集合框架的Collection、List、Set、Map接口
【java的集合框架】  Collection:       1.List         ①ArrayList         ②LinkedList       2.set         ①HashSet         ②LinkedHashSet         ③TreeSet Map:        1.HashMap  
Java集合面试题
**Collection** Set和hashCode以及equals方法的联系 Set内存放的元素为什么不可以重复,内部是如何保证和实现的? List 和 Set 区别 List 和 Map 区别 Arraylist 与 LinkedList 区别 ArrayList 与 Vector 区别 Arraylist与LinkedList默认空间是
java集合框架
### ArrayList简介 ArrayList是list接口的**可变数组**的实现。与一般数组不同的是,它的容量可以动态增长。 ArrayList继承了AbstractList抽象类,实现了List,RandomAccess, Cloneable, java.io.Serializable接口,根据实现的接口看,它支持随机访问,支持克隆,支持序列化
ArrayList源码解读(jdk1.8)
### **概要** 上一章,我们学习了Collection的架构。这一章开始,我们对Collection的具体实现类进行讲解;首先,讲解List,而List中ArrayList又最为常用。因此,本章我们讲解ArrayList。先对ArrayList有个整体认识,再学习它的源码,最后再通过例子来学习如何使用它。内容包括: 第1部分 ArrayList简
BAT面试笔试33题:JavaList、Java Map等经典面试题!
JavaList面试题汇总 ============= 1、List集合:ArrayList、LinkedList、Vector等。 2、Vector是List接口下线程安全的集合。 3、List是有序的。 4、ArrayList和LinkedList数据结构不一样,前者用在查询较多的场合,后者适用于插入较多的场合。 5、ArrayList使用的是
List接口(动态数组)
List接口(动态数组) ============ List集合类中元素_**有序且可重复**_ ArrayList(重要) ------------- * 作为List接口的主要实现类 * 线程不安全的,效率高 * 底层使用Object\[\] elementData数组存储 ### ArrayList的源码分析 #### jdk7
Stream的去重排序
1.List<Integer>排序 List<Integer> list = new ArrayList<>();list.add(50);list.add(25);list.add(25);list.add(98);list.add(32);List<Integer> collect = list.stream().distinct().sort