1. 回顾
在上一篇 我们介绍了 java 集合的整体架构, 为了复习方便请重新看下图
Colletion 有 List Set 等子接口 而每个子接口又有具体的实现类, 本文要讲的 ArrayList 就是 List 的一种实现. List 可存储有序可重复的元素, 那么可知 ArrayList 也是. 相反 Set 却是无序不可重复的.
2. 结构
那么我们开始重点看 ArrayList, 通过 idea 可得下图
由上图知
实现 RandomAccess 接口: 可以通过下标序号快速访问
实现了 Cloneable, 能被克隆
实现了 Serializable, 支持序列化
再看类中方法如下
可见 ArrayList 除了实现类 Collection 接口方法外 还多了许多重载多方法 例如
- void add(int index, E element)
- boolean addAll(int index, Collection<? extends E> c)
- E get(int index)
- int indexOf(Object o)
- int lastIndexOf(Object o)
- E remove(int index)
- E set(int index, E element)
- List<E> subList(int fromIndex, int toIndex)
上面的方法 顾名思义都可以猜出来 由于 ArrayList 是有序可重复的, 其中维护了一个索引 index 固可以以指定索引 index 来进行更多的操作, 例如获取指定索引位置的元素, 删除指定索引位置的元素, 截取某个索引范围的所有元素等等
3. 源码分析
一. 成员变量
- private static final long serialVersionUID = 8683452581122892189L;
- private static final int DEFAULT_CAPACITY = 10;
- private static final Object[] EMPTY_ELEMENTDATA = {
- };
- private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
- };
- transient Object[] elementData; // non-private to simplify nested class access
- private int size;
DEFAULT_CAPACITY 默认容量是 10
EMPTY_ELEMENTDATA 数组
DEFAULTCAPACITY_EMPTY_ELEMENTDATA
elementData 存放元素
size 元素个数
二. 构造函数
- public ArrayList(int initialCapacity) {
- if (initialCapacity> 0) {
- this.elementData = new Object[initialCapacity];
- } else if (initialCapacity == 0) {
- this.elementData = EMPTY_ELEMENTDATA;
- } else {
- throw new IllegalArgumentException("Illegal Capacity:"+
- initialCapacity);
- }
- }
- public ArrayList() {
- this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
- }
- public ArrayList(Collection<? extends E> c) {
- elementData = c.toArray();
- if ((size = elementData.length) != 0) {
- // c.toArray might (incorrectly) not return Object[] (see 6260652)
- if (elementData.getClass() != Object[].class)
- elementData = Arrays.copyOf(elementData, size, Object[].class);
- } else {
- // replace with empty array.
- this.elementData = EMPTY_ELEMENTDATA;
- }
- }
有三个构造函数 分析代码可知可初始化时传递一个 int 值指定容量, 也可以不传默认 10 的容量 还可以传递一个指定 Collection 来初始化 其中第三个指定 Collection 来初始化较长, 无非就是先把集合转化成数组 然后把元素复制到 list 中去来完成初始化
三. 常用方法
新增
- public boolean add(E e) {
- ensureCapacityInternal(size + 1); // Increments modCount!!
- elementData[size++] = e;
- return true;
- }
其中调用 ensureCapacityInternal 方法
- private void ensureCapacityInternal(int minCapacity) {
- if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
- minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
- }
- ensureExplicitCapacity(minCapacity);
- }
再调用 ensureExplicitCapacity 方法
- private void ensureExplicitCapacity(int minCapacity) {
- modCount++;
- // overflow-conscious code
- if (minCapacity - elementData.length> 0)
- grow(minCapacity);
- }
又调用 grow 方法
- private void grow(int minCapacity) {
- // overflow-conscious code
- int oldCapacity = elementData.length;
- int newCapacity = oldCapacity + (oldCapacity>> 1);
- if (newCapacity - minCapacity <0)
- newCapacity = minCapacity;
- if (newCapacity - MAX_ARRAY_SIZE> 0)
- newCapacity = hugeCapacity(minCapacity);
- // minCapacity is usually close to size, so this is a win:
- elementData = Arrays.copyOf(elementData, newCapacity);
- }
总结以上便是新增前需要确定容量, 当当前数组容量不够时就需要扩容, 然后调 Arrays.copyOf() 创建一个新的数组并将数据拷贝到新数组中, 且把引用赋值给 elementData
删除 remove
- public E remove(int index) {
- rangeCheck(index);
- modCount++;
- E oldValue = elementData(index);
- int numMoved = size - index - 1;
- if (numMoved> 0)
- System.arraycopy(elementData, index+1, elementData, index,
- numMoved);
- elementData[--size] = null; // clear to let GC do its work
- return oldValue;
- }
- public boolean remove(Object o) {
- if (o == null) {
- for (int index = 0; index < size; index++)
- if (elementData[index] == null) {
- fastRemove(index);
- return true;
- }
- } else {
- for (int index = 0; index < size; index++)
- if (o.equals(elementData[index])) {
- fastRemove(index);
- return true;
- }
- }
- return false;
- }
两种重载方法 先检查范围 然后拿到被删的元素 然后把被删元素后到元素往前移动 复制到目标数组 然后返回被删元素
修改 set
- public E set(int index, E element) {
- rangeCheck(index);
- E oldValue = elementData(index);
- elementData[index] = element;
- return oldValue;
- }
这段代码比较简单 范围检查和重新赋值
获取 get
- public E get(int index) {
- rangeCheck(index);
- return elementData(index);
- }
这个估计都不用我说把
4. 总结
通过结构源码都分析我们知道, ArrayList 底层就是通过数组来实现, 添加的时候检查容量不够就扩容, 然后赋值 删除时则把被删元素后往前移动 更新则比较简洁明白.
来源: https://juejin.im/post/5c374e52518825247c722daf