Java 列表和队列（一）：剖析 ArrayList

1. Java 集合框架体系图

2. ArrayList 的基本用法

ArrayList 是 Java 中真正的动态数组容器类

ArrayList 是一个泛型容器，新建 ArrayList 需要实例化类型参数。比如

1 2	ArrayList<Integer> intList = new ArrayList<Integer> (); ArrayList<String> strList = new ArrayList<String> ();

3. `ArrayList` 的基本原理

代码基于 Java 7

1 2	private transient Object[] elementData; private int size;

内部有一个数组 elementData，一般会有一些预留的空间；有一个整数 size 纪录实际的元素个数
各种 public 方法内部操作的基本都是这个数组和这个整数，elementData 会随着实际元素个数的增多而重新分配，而 size 则始终纪录实际的元素个数

4. `ArrayList` 的 `add()` 方法的实现原理

add() 方法的主要代码

public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

分析：首先调用 ensureCapacityInternal() 方法确保数组容量是够的

ensureCapacityInternal() 方法代码

private void ensureCapacityInternal(int minCapacity) {
    if(elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

分析：它首先判断数组是不是空的，如果是空的，则首次至少要分配的大小为 DEFAULT_CAPACITY，DEFAULT_CAPACITY 的值为 10。接下来调用 ensureExplicitCapacity() 方法

ensureExplicitCapacity() 方法代码
1
2
3
4
5
6
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if(minCapacity - elementData.length > 0) {
grow(minCapacity);
}
}
- 分析：modCount 表示内部的修改次数，modCount++就是增加修改次数。如果需要的长度大于当前数组的长度，则调用 grow() 方法

grow() 方法主要代码

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if(newCapacity - minCapacity < 0) {
        newCapacity = minCapacity;
    }
    elementData = Arrays.copyOf(elementData, newCapacity);
}

扩容策略：右移一位相当于除 2，所以，newCapacity 相当于 oldCapacity 的 1.5 倍。如果扩展 1.5 倍还是小于 minCapacity，就扩展为 minCapacity

5. 怎样理解 `foreach` 语法

foreach 语法更简洁，适用于各种容器、更通用

6. `foreach` 语法背后是怎样实现的

Java 编译器会将 foreach 转换为迭代器 Iterator 和 while 循环的形式

Demo：

ArrayList<Integer> intList = new ArrayList<Integer> ();
intList.add(123);
intList.add(456);
intList.add(789);

//ArrayList 实现了 Iterable 接口
for(Integer a : intList) {
    System.out.println(a);
}

//Java 编译器会将 foreach 语法转换为类似如下代码：
Iterator<Integer> it = intList.iterator();
while(it.hasNext()) {
    System.out.println(it.next());
}

7. `Iterable` 和 `Iterator` 的定义分别是

源码基于 Java 7

Iterable 表示可迭代

1
2
3

public interface Iterable<T> {
    Iterator<T> iterator();
}

Iterator 表示迭代器

public interface Iterator<E> {
    boolean hasNext(); //判断是否还有元素未访问
    E next(); //返回下一个元素
    void remove(); //删除最后返回的元素
}

8. `Iterable` 和 `Iterator` 的联系是

Iterable 表示对象可以被迭代
- 它有一个方法 iterator()，返回 Iterator 迭代器对象，实际通过 Iterator 接口的方法进行遍历
- 如果对象实现了 Iterable 接口，就可以使用 foreach 语法（因为 foreach 基于迭代器 Iterator）
类可以不实现 Iterable 接口，也可以创建 Iterator 对象
Java 8
- 对 Iterable 增加了默认方法 forEach() 和 spliterator()
- 对 Iterator 增加了默认方法 forEachRemaining() 和 remove()

9. `ArrayList` 对 `Iterator` 接口的增强有

除了 iterator()，ArrayList 还提供了两个返回 Iterator 接口的方法

//返回的迭代器从 0 开始遍历
public ListIterator<E> listIterator();

//返回的迭代器从指定位置 index 开始遍历
public ListIterator<E> listIterator(int index);

ListIterator 扩展了 Iterator 接口，增加了一些方法：向前遍历、添加元素、修改元素、返回索引位置等，添加的方法有

public interface ListIterator<E> extends Iterator<E> {
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void set(E e);
    void add(E e);    
}

10. 对于一个 `ArrayList`，从末尾往前遍历，代码怎样实现

public void reverseTraverse(List<Integer> list) {
    ListIterator<Integer> it = list.listIterator(list.size());
    while(it.hasPrevious) {
        System.out.println(int.previous);
    }
}

11. 关于迭代器，有一种常见的误用是

在迭代的过程中调用容器的删除方法（不是迭代器的删除方法）

12. 接上题，下面代码是否合法，为什么

//一次迭代删除一个整数，最后删除 ArrayList 中【所有小于 100】 的整数
public void remove(ArrayList<Integer> list) {
    for(Integer a : list) {
        if(a <= 100) {
            list.remove(a);
        }
    }
}

结论：运行时抛出 ConcurrentModificationException 并发修改异常
原因：因为迭代器内部会维护一些索引位置相关的数据（cursor、lastRet、expectedModCount），要求在迭代过程中，容器不能发生结构性变化，否则这些索引位置就失效了
概念：所谓结构性变化就是添加、插入和删除元素，只是修改元素内容不算结构性变化

解决方法：使用迭代器的 remove() 方法。代码如下

public static void remove(ArrayList<Integer> list) {
    Iterator<Integer> it = list.iterator();
    while(it.next <= 100) {
        it.remove();
    }
}

13. 迭代器如何知道发生了结构性变化或者迭代器的实现原理是

ArrayList 中 iterator() 方法的实现，代码为

1
2
3

public Iterator<E> iterator() {
    return new Itr();
}

分析：新建了一个 Itr 对象，Itr 是一个成员内部类（可以直接访问外部类的实例变量），实现了 Iterator 接口，声明为：private class Itr implements Iterator<E>

它有三个成员变量

1
2
3

int cursor; //表示下一个要返回的元素位置
int lastRet; //表示最后一个返回的索引位置
int expectedModCount = modCount; //表示期望的修改次数，初始化为外部类当前的修改次数

Itr 的 hasNext() 方法代码实现
1
2
3
public boolean hasNext() {
return cursor != size;
}
- 分析：返回 cursor 与 size 是否不相等的布尔值

Itr 的 next() 方法代码实现

public E next() {
    checkForComodification();
    int i = cursor;
    if(i >= size) {
        throw new NoSuchElementException();
    }
    Object[] elementData = ArrayList.this.elementData;
    if(i >= elementData.length) {
        throw new ConcurrentModificationException();
    }
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

分析：首先调用了 checkForComodification() 方法，它的代码为：

final void checkForComodification() {
    if(modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

分析：所以，next() 方法前面部分主要就是在检查是否发生了结构性变化，如果没有变化，就更新 cursor 和 lastRet 的值，以保持其语义，然后返回对应的元素

Itr 的 remove() 方法代码实现

public void remove() {
    if(lastRet < 0) {
        throw new IllegalStateException();
    }
    checkForComodification();
    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificaitonException();
    }
}

分析：它调用了 ArrayList 的 remove() 方法，但同时更新了 cursor、lastRet、expectedModCount 的值，所以它可以正确删除

listIterator() 的实现使用了另一个内部类 ListItr，它继承自 Itr，基本思路类似

14. 下面代码是否合法，为什么，怎样解决

//通过迭代器【删除所有】元素
public static void removeAll(ArrayList<Integer> list) {
    Iterator<Integer> it = list.iterator();
    while(it.hasNext()) {
        it.remove();
    }
}

结论：运行时抛出 IllegalStateException 异常
原因：调用 remove() 方法前必须先调用 next() 方法
解决方法
- 在 it.remove() 之前先调用 it.next()
- 当然，如果只是要删除所有元素，ArrayList 有现成的方法 clear()

15. 为什么要通过迭代器这种方式访问元素呢，直接使用 `size()`、`get(index)` 语法不也可以吗，或者说，迭代器的好处是什么

在一些场景下，确实没有什么差别，两者都可以
不过，foreach 的语法更简洁一些。更重要的是，迭代器语法更通用，它适用于各种容器类
- 迭代器设计模式：是一种关注点分离的思想，将数据的实际组织方式与数据的迭代遍历相分离，是一种常见的设计模式
- 从性能的角度考虑：ArrayList 的 size()/get(index) 语法与迭代器性能是差不多的；但在 LinkedList中，迭代器性能就要高很多
- 从封装的思路上讲：迭代器封装了各种数据组织方法迭代操作，提供了简单和一致的接口

16. `ArrayList` 实现的主要接口有哪几个

Collection: 表示一个数据集合，数据间没有位置或顺序的概念
- Java 8 新增了几个默认方法，包括：removeIf()、stream()、spliterator() 等
List: 表示有顺序或位置概念的数据集合，它扩展了 Collection
- Java 8 新增了几个默认方法，包括：sort()、replaceAll()、spliterator()
- Java 9 新增了多个重载的 of() 方法，可以根据一个或多个元素生成一个不变的 List
RandomAccess: 空接口，没有定义任何代码
- 又称为标记接口，用于声明实现类的一种属性
- 这里，实现了 RandomAccess 接口的类表示可以随机访问（类似数组）

17. 有没有声明 `RandomAccess` 有什么关系呢

主要用于一些通用的算法代码中，它可以根据这个声明而选择效率更高的实现

比如，Collection 类中有一个方法 binarySearch()。在 List 中进行二分查找，它的实现代码就根据 list 是否实现了 RandomAccess 而采用不同的实现机制，代码如下

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if(list instanceof RandomAccess || list.size < BINARYSEARCH_THRESHOLD) {
        return Collection.indexedBinarySearch(list, key);
    } else {
        return Collection.iteratorBinarySearch(list, key);
    }
}

18. `ArrayList` 中还有哪些常用的方法

构造方法：ArrayList()
与数组的互相转换：toArray()、Arrays.asList()
容量大小控制：ensureCapacity()、trimTosize()

19. `ArrayList` 的特点是什么

它的特点就是内部采用动态数组实现，这决定了下面两点（性能和线程）
ArrayList 可以随机访问，按照索引位置进行访问效率很高，效率是 O(1)，即一步到位
- 除非数组已排序，否则按照内容查找元素效率比较低，具体是 O(N)，N 为数组长度，即性能与数组长度成正比
- 添加元素的效率还可以，重新分配和复制数组的开销被平摊了。具体来说，添加 N 个元素的效率为 O(N)
- 插入和删除元素的效率比较低，因为需要移动元素，具体为 O(N)
ArrayList 是线程不安全的
- 实现线程安全的一种方式是使用 Collection 提供的方法装饰 ArrayList
- 另外，类 Vector 作为 Java 最早实现的容器类之一，也实现了 List 接口。基本原理与 ArrayList 类似，内部使用了 synchronized 实现了线程安全
- 不需要线程安全的情况下，推荐使用 ArrayList

1. Java 集合框架体系图

2. ArrayList 的基本用法

3. ArrayList 的基本原理

4. ArrayList 的 add() 方法的实现原理

5. 怎样理解 foreach 语法

6. foreach 语法背后是怎样实现的

7. Iterable 和 Iterator 的定义分别是

8. Iterable 和 Iterator 的联系是

9. ArrayList 对 Iterator 接口的增强有

10. 对于一个 ArrayList，从末尾往前遍历，代码怎样实现