目录
- 前言
- 类继承关系
- 成员变量解读
- 构造器
- 重要方法
- 迭代器内部实现解读
- 总结
前言
1）本文章的JDK版本为JDK1.8，如果你使用的是其他版本，请参考你的Java源码！
2）由于作者水平有限，本文只对部分的方法进行了分析。不足之处，希望大家指出，谢谢
3）如果你对Java中的数组还没有理解，可以先学习数组及其在JVM中的存储方式，可以参考下面文章
Java中数组在内存中的存放原理讲解
java对象数组的概述和使用
1、继承关系
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
2、成员变量
private static final int DEFAULT_CAPACITY = 10;
ArrayList默认的初始容量private static final Object[] EMPTY_ELEMENTDATA = {};
默认的空Object数组private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
与默认初始容量对应的Object数组transient Object[] elementData;
存放元素的数组private int size;
动态数组的sizeprivate static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
最大的数组size = 0x7FFFFFF7 =(Integer.MAX_VALUE = 0x7fffffff)-8
3、构造器
//指定初始化容量的构造器，它通过判断int值大小来初始化elementData
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)
/*类型判断，如果elementData的类型不是Object[]数组，则将其
*复制为Object类型的数组，并且elementData的大小小于size时，多于的位置
*填入null
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
4、方法
4.1 public void trimToSize()
/**
* ArrayList大小整理，在size < elementData.length 且 size != 0时，
* elementData将会被截断为size的长度！！！！
* elementData将会被截断为size的长度！！！！
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
4.2 public void ensureCapacity(int minCapacity)及相关私有方法
/**
* 增加数组的容量的判定，这个操作只有在 minCapacity>minExpand 时，
* 才能完成操作。
* 注意下面的三目运算符，minExpand的值取决于
* 你是否已经在你的ArrayList对象中放入了值。
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/* 核心方法，动态数组的增长实现
* 一般情况按oldCapacity的半数增长，但最大的size不能大于Integer.MAX_VALUE
* 原数组会被copy到一个新的数组(size=newCapacity)中，多于的位置填充null
*/
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
grow()流程图：
4.3 public int indexOf(Object o)
//返回指定元素第一次出现的索引，无则返回 -1
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
//如果使用 o.equals()则会抛出空指针异常(null.equals()是错的)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
//Object类的equals90直接调用“==”
if (o.equals(elementData[i]))
return i;
}
return -1;
}
4.4 public int lastIndexOf(Object o)
//返回指定元素最后一次出现的索引，无则返回 -1
//从尾部开始遍历
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
4.6 add方法
//（1）在尾部添加
public boolean add(E e) {
//确定是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//（2）在指定位置添加
public void add(int index, E element) {
//判定是否索引越界
rangeCheckForAdd(index);
//确定是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//从指定数组的指定开始位置到指定结束位置复制一个数组，在本节末尾给出了该方法的详细解释
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//将index位置的原element替换为新的element
elementData[index] = element;
size++;
}
//（3）两个索引越界检查方法
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//索引越界信息
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
public static void arraycopy(Object src, int srcPos,Object dest, int destPos,int length)
- src - 源数组。
- srcPos - 源数组中的起始位置。
- dest - 目标数组。
- destPos - 目标数据中的起始位置。
- length - 要复制的数组元素的数量。
从指定源数组中复制一个数组，复制从指定的位置开始，到目标数组的指定位置结束。从 src 引用的源数组到 dest 引用的目标数组，数组组件的一个子序列被复制下来。被复制的组件的编号等于 length 参数。源数组中位置在 srcPos 到 srcPos+length-1 之间的组件被分别复制到目标数组中的 destPos 到 destPos+length-1 位置。
如果参数 src 和 dest 引用相同的数组对象，则复制的执行过程就好像首先将 srcPos 到 srcPos+length-1 位置的组件复制到一个带有 length 组件的临时数组，然后再将此临时数组的内容复制到目标数组的 destPos 到 destPos+length-1 位置一样。
这样一来，ArrayList的插入就很好理解了，先将 __index 及其后__面的所有元素复制一份，然后从 index+1 处到destPos+length-1；然后将 index 处的元素替换为新的元素即可！。
4.7 remove方法
在理解了add方法之后，remove方法就很好理解了。
//移除指定位置的元素
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
//所要移除元素的位置之所以不用 index - 1，
//是因为rangCheck()方法中是判断 index>size，而不是>=
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将最后一个元素置null，方便垃圾回收器回收
//至于为什么置null能方便GC回收，请阅读“对象生命周期”和JVM垃圾回收机制的相关书籍和文章
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
//注意for循环，是移除所有满足条件的obj
public boolean remove(Object o) {
//空判断！集合框架中有大量空判断，自己在编程过程中也要注意空判断，
//以免抛出“空指针异常”
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//不进行索引越界检查的快速remove
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
//跳过边界检查的私有移除方法，并且不返回删除的值。
//相比 remove 少了检查，和返回值，一个对象的创建
private void fastRemove(int index) {
modCount++;
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
}
4.8 两种toArray
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
此方法担当基于数组的 API 和基于 collection 的 API 之间的桥梁。
4.9 public Object clone()
//返回这个ArrayList实例的一个浅副本。（元素本身没有被复制。）
//它的modCount将会置0
//todo 不懂对象克隆的原理
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
4.10 其他增删查改操作类似
5、迭代器内部类实现
未完待续...
6、总结
- 适用范围
- 和刚学习使用它时一样、ArrayList有其特殊的应用场景，与LinkedList相对应。其优点是随机读取，缺点是插入元素时需要移动大量元素，效率不太高。
- 关于 null 判断
- 在写这篇文章前，自己也试着在 LeetCode 上自己实现链表和数组，但是老报空指针异常。估计也是因为没有进行 null判断 引起的。
- 对象置null，方便 GC 回收垃圾