专栏首页Java阿呆浅谈ArrayList

浅谈ArrayList

一、ArrayList的继承体系和特点

ArrayList总体继承体系图如下:

ArrayList的特点主要有以下几点:

  • ArrayList在内存中分配连续的存储空间,可理解为长度可变的数组。
  • ArrayList存储元素可以重复,存储顺序和添加顺序一致。
  • 遍历元素和随机访问元素的效率较高,因为和数组一样存在索引。
  • 添加、删除元素时需移动大量元素,按照内容查询时效率低。

二、ArrayList的用法

List<String> list = new ArrayList<String>();//使用多态创建ArrayList,泛型指定该ArrayList只能放String类型的元素
    for(int i=0;i<5;i++)
        list.add("a"+i);//架循环往ArrayList里添加元素
    System.out.println(list);//输出整个ArrayList
    list.add(3, "a0");//在指定索引处添加指定元素
    System.out.println(list);
    list.remove(2);//删除指定索引处的元素
    System.out.println(list);
    System.out.println(list.size());//获取ArrayList的长度并输出
    System.out.println(List.get(3));//拿到指定索引处的元素并输出
    list.removeAll(list);//删除所有元素    
    System.out.println(list);

输出结果:
[a0, a1, a2, a3, a4]
[a0, a1, a2, a0, a3, a4]
[a0, a1, a0, a3, a4]
5  a3
[]

ArrayList的一些其他常用方法:

toArray(T [] a):把ArrayList转换成数组放到指定数组a里

contains(Object o):判断ArrayList中是否包含指定元素,返回Boolean类型

isEmpty():判断ArrayList按是否为空,返回Boolean类型

三、ArrayList的自动扩容机制

java为了实现自动扩容,引入了Capacity和size的概念,用来区别数组的length。为了保证用户增加新的对象,java设置了最小容量(minCapacity),通常情况下,它大于列表对象的数目,所以Capactiy虽然就是底层数组的长度(length),但是对于最终用户来讲,它是没有意义的。而存储着列表对象数量的size才是最终用户所需要的。为了防止用户错误修改,这一属性被设置为private的,不过可以通过size()方法获取。

ArrayList的初始容量默认为10:

ArrayList有两个构造方法:

这说明Capacity初始值(initialCapacity)可以由用户直接指定或由用户指定的Collection集合存储的对象数目确定,如果没有指定,系统默认为10。而size的被声明为int型变量,默认为0,当用户用指定Collection创建ArrayList时,size值等于initialCapacity。

我们知道ArrayList可以用add()方法添加元素,我们来看一下add()的实现:

ensureCapacityInternal()方法的调用主要用来确认数组是否可以放下这一元素,修改elementData数组的指向。ensureCapacityInternal()方法的实现如下:

首先看看数组是否为空,如果数组为空,就将DEFAULT_CAPACITY和minCapacity中较大的一个作为初始大小赋给minCapacity,DEFAULT_CAPACITY就是先前定义的10,minCapacity就是add方法中传入的size+1。

如果数组不为空,就执行ensureExplicitCapacity()方法,其实现如下:

modCount属性在ArrayList的父类AbstractList中定义,用于存储结构修改次数。

此方法比较minCapacity与elementData.length的大小。当第一次插入值时,由于minCapacity一定大于等于10,而elementData.length 是0,此时调用grow()方法,grow()方法正是ArrayList扩容的核心所在,其实现如下:

这个方法首先计算出一个容量,大小为oldCapacity + (oldCapacity >> 1)。即elementData数组长度的1.5倍。再从minCapacity和这个容量中取较大值作为扩容后的新的数组大小。

新的容量小于数组的最大值MAX_ARRAY_SIZE,可能超过一次能申请的整块内存的大小上限,出现OutOfMemoryError。

如果新的容量大于数组的最大值MAX_ARRAY_SIZE,调用hugeCapacity()方法,其实现如下:

此方法会对minCapacity和MAX_ARRAY_SIZE进行比较,minCapacity 大的话,就将Integer.MAX_VALUE 作为新数组的大小,否则将MAX_ARRAY_SIZE作为数组的大小。最后,就把原来数组的数据复制到新的数组中。调用了Arrays的copyOf方法。内部是System的arraycopy方法,由于是native方法,所以效率较高。

通过以上源码我们不难看出,java自动增加ArrayList大小的思路是:向ArrayList添加对象时,原对象数目加1,如果大于原底层数组长度,则以适当长度新建一个原数组的拷贝,并修改原数组,指向这个新建数组。原数组自动抛弃(java垃圾回收机制会自动回收)。size则在向数组添加对象,自增1。

综上所述,ArrayList的扩容会产生一个新的数组,将原来数组的值复制到新的数组中。会消耗一定的资源。所以我们初始化ArrayList时,最好可以估算一个初始的大小。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • ConcurrentHashMap源码(一)

    整体流程跟HashMap比较类似,大致是以下几步: (1)如果桶数组未初始化,则初始化; (2)如果待插入元素所在的桶为空,则尝试把此元素直接插入到桶的第一个位...

    Java阿呆
  • ConcurrentHashMap源码(二)

    删除元素跟添加元素一样,都是先找到元素所在的桶,然后采用分段锁的思想锁住整个桶,再进行操作。

    Java阿呆
  • java源码之数组、链表与哈希表

    在java中,数组定义为一种基本类型,其可以通过下标获取到对应位置的数据。数组在内存中是一段连续的存储单元,每个数据依次放在每个单元中。分析这种结构,可以得出以...

    Java阿呆
  • 面经手册 · 第7篇《ArrayList也这么多知识?一个指定位置插入就把谢飞机面晕了!》

    说到数据结构基本包括;数组、链表、队列、红黑树等,但当你看到这些数据结构以及想到自己平时的开发,似乎并没有用到过。那么为什么还要学习数据结构?

    小傅哥
  • 面经手册 · 第7篇《ArrayList也这么多知识?一个指定位置插入就把谢飞机面晕了!》

    说到数据结构基本包括;数组、链表、队列、红黑树等,但当你看到这些数据结构以及想到自己平时的开发,似乎并没有用到过。那么为什么还要学习数据结构?

    小傅哥
  • 漫画 | 什么是散列表(哈希表)?

    创建与输入数组相等长度的新数组,作为直接寻址表。两数之和的期望是Target,将Target依次减输入数组的元素,得到的值和直接寻址表比较,如果寻址表存在这个值...

    我脱下短袖
  • Python全栈开发之函数

    正常情况下,给函数传递参数需要按照定义的顺序,不想按顺序就要使用关键参数,但是关键参数必须放在普通参数之后

    py3study
  • 【干货】用大白话聊聊JavaSE — ArrayList 深入剖析和Java基础知识详解(二)1. 新建一个MyList类2. 构造函数设计3. add方法实现4. remove方法实现

    剽悍一小兔
  • 【剑指Offer】32.3 按之字形顺序打印二叉树

    请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

    瑞新
  • Day3 python基础

    py3study

扫码关注云+社区

领取腾讯云代金券