1 手写ArrayList核心源码

九路
• 阅读 1352

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

点赞
收藏
评论区
推荐文章
技术小男生 技术小男生
4个月前
linux环境jdk环境变量配置
1:编辑系统配置文件vi/etc/profile2:按字母键i进入编辑模式,在最底部添加内容:JAVAHOME/opt/jdk1.8.0152CLASSPATH.:$JAVAHOME/lib/dt.jar:$JAVAHOME/lib/tools.jarPATH$JAVAHOME/bin:$PATH3:生效配置
光头强的博客 光头强的博客
4个月前
Java面向对象试题
1、请创建一个Animal动物类,要求有方法eat()方法,方法输出一条语句“吃东西”。创建一个接口A,接口里有一个抽象方法fly()。创建一个Bird类继承Animal类并实现接口A里的方法输出一条有语句“鸟儿飞翔”,重写eat()方法输出一条语句“鸟儿吃虫”。在Test类中向上转型创建b对象,调用eat方法。然后向下转型调用eat()方
刚刚好 刚刚好
4个月前
css问题
1、在IOS中图片不显示(给图片加了圆角或者img没有父级)<div<imgsrc""/</divdiv{width:20px;height:20px;borderradius:20px;overflow:h
blmius blmius
1年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
小森森 小森森
4个月前
校园表白墙微信小程序V1.0 SayLove -基于微信云开发-一键快速搭建,开箱即用
后续会继续更新,敬请期待2.0全新版本欢迎添加左边的微信一起探讨!项目地址:(https://www.aliyun.com/activity/daily/bestoffer?userCodesskuuw5n)\2.Bug修复更新日历2.情侣脸功能大家不要使用了,现在阿里云的接口已经要收费了(土豪请随意),\\和注意
艾木酱 艾木酱
3个月前
快速入门|使用MemFire Cloud构建React Native应用程序
MemFireCloud是一款提供云数据库,用户可以创建云数据库,并对数据库进行管理,还可以对数据库进行备份操作。它还提供后端即服务,用户可以在1分钟内新建一个应用,使用自动生成的API和SDK,访问云数据库、对象存储、用户认证与授权等功能,可专
helloworld_28799839 helloworld_28799839
4个月前
常用知识整理
Javascript判断对象是否为空jsObject.keys(myObject).length0经常使用的三元运算我们经常遇到处理表格列状态字段如status的时候可以用到vue
3A网络 3A网络
3个月前
手写 ArrayList 核心源码
手写ArrayList核心源码手写ArrayList核心源码ArrayList是Java中常用的数据结构,不光有ArrayList,还有LinkedList,HashMap,LinkedHashMap,HashSet
NVIDIA安培架构下MIG技术分析
关键词:NVIDIA、MIG、安培一什么是MIG2020年5月,NVIDIA发布了最新的GPU架构:安培,以及基于安培架构的最新的GPU:A100。安培提供了许多新的特性,MIG是其中一项非常重要的新特性。MIG的全名是MultiInstanceGPU。NVIDIA安培架构中的MIG模式可以在A100GPU上并行运行七个作业。多实
密钥管理系统-为你的天翼云资产上把“锁
本文关键词:数据安全,密码机,密钥管理一、你的云上资产真的安全么?1.2021年1月,巴西的一个数据库30TB数据被破坏,泄露的数据包含有1.04亿辆汽车和约4000万家公司的详细信息,受影响的人员数量可能有2.2亿;2.2021年2月,广受欢迎的音频聊天室应用Clubhouse的用户数据被恶意黑客或间谍窃取。据悉,一位身份不明的用户能够将Clubho