内部结构
- ArrayList内部核心是一个Object数组elementData
- Object数组的长度（length）视为ArrayList当前的容量（capacity）
- size对象表示ArrayList当前的元素个数
类上的重要注释
内部是Object数组
允许put null值,会自动扩容
size、isEmpty、get、set、add 等方法时间复杂度都是 O (1);
多个线程操作一个ArrayList实例，如果有改变结构的操作，就一定要在外部进行线程同步，推荐的做法：List list = Collections.synchronizedList(new ArrayList(...))
增强for循环,或者使用迭代器迭代过程中，如果数组大小被改变，会快速失败，抛出异常。
如何初始化一个有元素的ArrayList
- 普通方式：
ArrayList<String> list = new ArrayList<>();
list.add("1");
list.add("2");
- 内部类方式：
ArrayList<String> list = new ArrayList<>(){
add("aaa");
add("bbb");
}
- Arrays.asList
ArrayList<String> list = new ArrayList<>(Arrays.asList("aaa", "bbb");
- Collections.ncopies
例子：初始化一个由10个0组成的集合
ArrayList<Integer> list = new ArrayList<>(Collections.nCopies(10, 0));
重要源码
构造
ArrayList有三种构造方法
public ArrayList()；//elementData初始化一个空数组
public ArrayList(int initialCapacity) //this.elementData = new Object[initialCapacity]
public ArrayList(Collection<? extends E> c)
这里主要关注new ArrayList()和new ArrayList(0)的区别，两者都是初始化一个空数组，但是：
无参构造得到的ArrayList，容量一开始是0，初次add时会直接扩容到10（重新申请一个length为10的数组，并且拷贝过来）
但new ArrayList(0)得到ArrayList，按照扩容核心方法grow()中的写法，从0开始增长容量，前期容量增长的会很慢（0->1->2->3->4->6->9->13)
一般情况下为了避免扩容造成的造成的损耗，new ArrayList(0)不推荐使用
</aside>
add 尾部添加
//要点：添加前会确认容量,防止数组越界
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
//扩容
//1.先确认是否需要扩容,当期望容量(size(元素数)+1)超过当前容量了，就需要扩容
//2.一般期望容量都是size+1,除了无参构造的空数组第一次扩容时,期望容量是10
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0) //所需的最小容量超过当前容量了，就需要扩容
grow(minCapacity);
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //无参构造,默认初始化容量为10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//扩容本质是按照新容量创建一个新数组，然后把老数组数据用Arrays.copyOf复制过去
//新容量的计算规则
//1.一般是原容量的3/2，用old+old>>1实现
//2.3/2可能都不够（比如0*3/2）,直接扩容成期望容量(其实就是+1)
//3.3/2超过最大容量了 Integer.MAX_VALUE - 8,看看期望容量和Integer.MAX_VALUE - 8哪个更适合
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); //3/2
if (newCapacity - minCapacity < 0) //比如0的3/2倍还是0,直接扩容到1就好了
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) //newCapacity超大了,就不能用3/2规则了,看看minCapacity
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;
}
指定位置插入
从逻辑上看指定位置插入是四步：
- 查看index是否越界
- 容量检查，不够扩容
- 数据迁移：将插入位置之后的所有元素拷贝到+1的位置
- element插入到指定位置
注意这个方法上面的注释
-
rangeCheck，越界的标准是看size而不是capacity：
- 对于ArrayList来说，内部数组的长度就是capacity也就是容量，当前数组的元素个数是size，这两个数据并不见得相等（比如无参构造生成的ArrayList，size可能为1，capacity为10）
- 但从使用者的角度来看，ArrayList就是个动态增长的list，使用者感知不到容量、扩容，使用者看起来这个ArrayList的末尾就是size
- 调用add只能在数据中间插入或者在数据末尾（下标为size的位置）插入，否则即使插入的下标没有超过capacity，但是超过了size，也算越界。
- 删除,同理,也会有rangeCheck
- 固定位置的插入删除,每次都会涉及大量的数据迁移,在拥有大量数据的ArrayList中不建议这么做
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
指定位置删除
可类比上个方法
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;
}
按元素删除
方法注释：
- 新增的时候是没有对 null 进行校验的，所以删除的时候也是允许删除 null 值的；
- 找到值在数组中的索引位置，是通过 equals 来判断的，如果数组元素不是基本类型，需要我们关注 equals 的具体实现。
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;
}
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
}
重点：迭代器
迭代器模式简介
我们遍历一个一维的集合时，经常会使用for循环或者foreach循环
for (String item : list) {
System.out.println(item);
}
如果我们要遍历一个二维的图，简单的for循环就做不到了，这时我们可能会采用DFS或者BFS之类的办法，相信大家刷算法的时候都写过。
这时就会存在以下问题，同时也引出迭代器模式：
- 我肯定不想每次遍历时都把DFS的代码重新在客户端代码里写一遍，这意味着客户端代码需要关心数据结构的具体实现，一旦数据结构的具体实现变了（比如邻接矩阵变成邻接表了），或者遍历方法变了（DFS变成BFS了），就需要把客户端代码的遍历代码全都修改一遍
- 如果将这部分遍历的逻辑封装到到容器类中，也会导致容器类代码的复杂性。
因此，我们可以将遍历操作拆分到迭代器类中。比如，针对图的遍历，我们就可以定义 DFSIterator、BFSIterator 两个迭代器类，让它们分别来实现深度优先遍历和广度优先遍历，容器类和迭代器之间用组合方式关联。
并且，容器和迭代器都提供了抽象的接口，方便我们在开发的时候，基于接口而非具体的实现编程。当需要切换新的遍历算法的时候，比如，从前往后遍历链表切换成从后往前遍历链表，客户端代码只需要将迭代器类从 LinkedIterator 切换为 ReversedLinkedIterator 即可，其他代码都不需要修改。除此之外，添加新的遍历算法，我们只需要扩展新的迭代器类，也更符合开闭原则。
请添加图片描述
总结起来，迭代器模式有以下的好处
- 封装复杂数据结构的遍历代码：简单的数据结构我可以直接用for循环遍历，但是复杂数据结构的遍历代码，没必要在自己的客户端代码里再实现一遍，于是拆分出迭代器接口，容器类和迭代器之间用组合方式关联。
- 扩展性：我们也不想把遍历方法写在容器类中（容器类更加复杂，变化原因增加，不符合单一职责）我需要更改或添加迭代方式时，只需要扩展新的迭代器类，而不需要去更改其他地方的代码，更符合开闭原则
- 基于接口编程：容器和迭代器都提供了抽象的接口，方便我们在开发的时候，基于接口而非具体的实现编程。当需要切换新的遍历算法的时候，比如，从前往后遍历链表切换成从后往前遍历链表，客户端代码只需要将迭代器类从 LinkedIterator 切换为 ReversedLinkedIterator 即可，其他代码都不需要修改
ArrayList的迭代器
Java中如果要自己实现迭代器，实现java.util.Iterator类就好了，ArrayList就是这样做的
ArrayList实现了两个迭代器类Itr和ListItr，后者继承了前者，先看看第一个
这里先省略方法的具体实现，看看一个迭代器的主要参数和方法
private class Itr implements Iterator<E> {
int cursor; // 迭代过程中下一个元素的位置，默认从0开始
int lastRet = -1; // 一般情况下表示上一次迭代过程中索引的位置；删除一次后：为-1
int expectedModCount = modCount; //expectedModCount表示迭代过程中期望的版本号
Itr() {}
public boolean hasNext() { //查看还有没有值可以迭代
}
public E next() { //如果有值可以迭代，迭代值是多少
}
public void remove() { //删除当前迭代的值
}
public void forEachRemaining(Consumer<? super E> consumer) {
}
final void checkForComodification() {
}
}
常规情况下，遍历一个list的代码，以及删除元素的代码如下
// 获取迭代器并遍历 ArrayList
Iterator<String> iter = list.iterator();
while (iter.hasNext()) {
String item = iter.next(); //next的关键无非是cursor如何移动
if (item.equals("banana")) {
// 使用迭代器删除元素
iter.remove(); //cursor指向的是下一个元素的位置，lastRet是cursor的前一个位置，所以remove操作实际上删除的是lastRet指向的元素
}
}
需要注意删除操作：
- cursor指向的是下一个元素的位置，lastRet是cursor的前一个位置，所以remove操作实际上删除的是lastRet指向的元素
- 执行remove之后，cursor=lastRet，退回到前一个位置，防止遍历时丢失元素，lastRet=-1
- 这也就导致了remove操作不能连续执行，必须是先执行next操作(会将lastRet重新变为cursor-1)，才能执行一次remove
modCount有什么作用？与一个Fail-Fast 机制有关：
首先ArrayList中有一个modCount属性，所有更改数据结构的操作，add，remove都会将modCount++，可以被视作更改了ArrayList的版本号
另外，迭代器Itr中有属性expectedModCount，初始化为modCount。每次next()都会先检查expectedModCount有没有发生改变，如果改变就抛异常。
也就是说从Itr创建开始，就不允许当前ArrayList有结构上的改变，避免可能存在的错误
private class Itr implements Iterator<E> {
int expectedModCount = modCount; //expectedModCount表示迭代过程中期望的版本号
public E next() { //如果有值可以迭代，迭代值是多少
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
那可能会出什么错呢？
一句话总结就是：遍历过程中在当前游标之前（包括当前游标）的位置插入或删除元素，会导致某个元素重复遍历或者丢失遍历
因此，在ArrayList实现的Iterator逻辑中，每次cursor指向的都是下次元素的位置，而lastRet指向最后一次遍历元素的位置
每次remove操作，因为调用了arraylist的remove方法，modCount会自增，这时会将expectedModCount重置为modCount（防止fail-fast），并且将cursor回退为lastRet，避免丢失元素
Fail-Fast 机制通常设计用于停止正常操作，而不是试图继续可能出错的过程。（注意这个并不能防止多线程操作出现异常，只是防止单线程操作，迭代器遍历过程中被其他方式改变了集合结构，那么继续使用迭代器是有可能报异常的，因为从使用者的角度看这不属于使用者的逻辑错误，但是可能会出错，所以在设计上应当主动报异常）
ArrayList还实现了一个迭代器ListIterator
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
区别：
1.使用范围不同，Iterator可以应用于所有的集合，Set、List和Map和这些集合的子类型。而ListIterator只能用于List及其子类型。
2.ListIterator有add方法，可以向List中添加对象，而Iterator不能。
3.ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历，但是ListIterator有hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历。Iterator不可以。
4.ListIterator可以定位当前索引的位置，nextIndex()和previousIndex()可以实现。Iterator没有此功能。
5.都可实现删除操作，但是ListIterator可以实现对象的修改，set()方法可以实现。Iterator仅能遍历，不能修改。
参考资料
王争. 设计模式之美
网友评论