2. 简介
java.util.List 是有序集合，也称为 sequence。此接口可以精确控制每个元素在 List 中的插入位置。用户可以通过整数索引访问集合中的元素。
2. List 实现类 - ArrayList
java.util.ArrayList 接口是基于 Object 数组、可调整容量大小的 java.util.List 接口的实现之一。java.util.ArrayList 实现了 java.util.List 接口的所有操作，并允许存储所有元素(包括 null)。java.util.ArrayList 类大致相当于 java.util.Vector，不同的是 java.util.Vector 类是线程安全的。
2.1 ArrayList 类的重要属性
- transient Object[] elementData : 用于元素存储的对象数组；
- private static final int DEFAULT_CAPACITY = 10 : 默认初始容量；
- private static final Object[] EMPY_ELEMENTDATA = {} : 用于空实例的共享空数组实例；
- private static final Object[] DEFAULTCAPACITY_EMPY_ELEMENTDATA = [] : 用于默认大小的空实例的共享空数组实例；
- private int size : ArrayList 的大小(包含的元素个数)；
2.2 实例化 ArrayList 对象
2.2.1 实例化一个默认初始容量为 10 的空 List
class ArrayListTest {
public static void main(String [] args) {
new ArrayList();
}
}
ArrayList 对应的构造函数源码如下：
/**
* Constructs an empty list with an initial capacity of ten.
* 构造一个初始容量为 10 的空 list
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2.2.2 实例化一个具有指定容量的空 ArrayList
class ArrayListTest {
public static void main(String [] args) {
new ArrayList(20);
}
}
ArrayList 对应的构造函数源码如下：
/**
* Constructs an empty list with the specified initial capacity.
* 构造一个具有指定初始容量的空 list
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
* 如果指定的初始容量为负，则抛出 IllegalArgumentException 异常。
*/
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);
}
}
2.2.3 按集合迭代器返回顺序实例化一个包含指定集合元素的 ArrayList
class ArrayListTest {
public static void main(String [] args) {
Collection list = new ArrayList();
new ArrayList(list);
}
}
ArrayList 对应的构造函数源码如下：
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
* 按照集合的迭代器返回的顺序构造一个包含指定集合元素的list。
* 将list转换为数组，然后使用数组拷贝填充到list
*
* @param c the collection whose elements are to be placed into this list
* 其元素将被放入此list的集合。
* @throws NullPointerException if the specified collection is null
* 如果指定的集合为空，则抛出 NullPointerException。
*/
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;
}
}
2.2.4 使用常用工具包实例化 ArrayList
使用 guava 实例化期望容量的 ArrayList：
Guava com.google.common.collect.Lists#newArrayListWithExpectedSize(int) 源码如下：
@GwtCompatible(serializable = true)
public static <E> ArrayList<E> newArrayListWithExpectedSize(int estimatedSize) {
return new ArrayList<>(computeArrayListCapacity(estimatedSize));
}
@VisibleForTesting
static int computeArrayListCapacity(int arraySize) {
checkNonnegative(arraySize, "arraySize");
// TODO(kevinb): Figure out the right behavior, and document it
return Ints.saturatedCast(5L + arraySize + (arraySize / 10));
}
@CanIgnoreReturnValue
static int checkNonnegative(int value, String name) {
if (value < 0) {
throw new IllegalArgumentException(name + " cannot be negative but was: " + value);
}
return value;
}
public static int saturatedCast(long value) {
if (value > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
if (value < Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
return (int) value;
}
2.3 ArrayList 插入元素 add
2.3.1 将指定元素插入到 ArrayList 实例对象末尾 add(E e)
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = Lists.newArrayListWithExpectedSize(20);
arrayList.add("hello");
}
}
add(E e) 方法源代码如下：
/**
* Appends the specified element to the end of this list.
* 将指定的元素插入到此list的末尾
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
add(E e) 方法的时间复杂度
add 方法在插入元素之前有一步确保数组容量的判断，所以数组是否进行扩容操作，对于 ArrayList 的时间复杂度有很大不同。扩容操作在后续进行讲解。
- 不扩容时 add 方法的时间复杂度为 O(1)
- 扩容时 add 方法的时间复杂度为 O(n + 1)
2.3.2 在ArrayList实例对象指定位置插入元素 add(int index, E element)
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = Lists.newArrayListWithExpectedSize(20);
arrayList.add("hello");
arrayList.add(0, "world");
}
}
add(int index, E element) 源代码如下：
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
* 在此list中指定位置插入指定元素。将当前在该位置的元素和任何其后续元素向右移动。
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
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++;
}
add(int index, E element) 时间复杂度
在指定位置插入元素时，其后续元素向右移动(数组拷贝)。
- 不扩容且在最后插入元素时时间复杂度为 O(1)
- 需要扩容且在头部插入元素时时间复杂度为 O(2n + 1)
2.3.3 按指定集合的迭代器返回顺序，将指定集合中的所有元素追加到集合末尾 addAll(Collection<? Extends E> c)
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>(20);
ArrayList<String> arrayList2 = new ArrayList<>(20);
arrayList2.addAll(arrayList2);
}
}
addAll(Collection<? extends E> c) 源代码如下：
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the
* specified collection's Iterator. The behavior of this operation is
* undefined if the specified collection is modified while the operation
* is in progress. (This implies that the behavior of this call is
* undefined if the specified collection is this list, and this
* list is nonempty.)
* 按照指定集合的迭代器返回的顺序，将指定集合中的所有元素追加到此list的末尾。如果在操作进行时
* 修改了指定的集合，则此操作的行为未定义。这意味着如果指定的集合是这个list，并且这个list是非空的，
* 那么这个调用的行为是未定义。
*
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
时间复杂度：
- 不扩容情况下为 O(n)，取决于要添加元素的个数
- 扩容情况下为 O(m + n)，取决于原始集合和添加的集合中元素的个数
2.3.3 按指定集合的迭代器返回顺序，将指定集合中的所有元素追加到指定位置 addAll(int index, Collection<? Extends E> c)
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>(20);
ArrayList<String> arrayList2 = new ArrayList<>(20);
arrayList2.addAll(1, arrayList2);
}
}
addAll(int index, Collection<? extends E> c) 源代码如下：
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
* 从指定位置开始，将指定集合中的所有元素插入此list。将当前在该位置和其后续元素向右移动。
* 新元素将按照指定集合的迭代器返回的顺序出现在列表中。
*
* @param index index at which to insert the first element from the
* specified collection
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
时间复杂度：
- 不扩容情况下为 O(size() - index + n) size() 为源集合的大小，index 为要插入的位置，n 为追加元素的个数；
- 扩容情况下为 o(m + m - index + n) m 为源集合的大小，index 为要出入的位置，n 为追加元素的个数；
2.4 ArrayList 更新指定元素 set(int index, E element)
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = Lists.newArrayListWithExpectedSize(20);
arrayList.add("hello");
arrayList.set(0, "world");
}
}
set(int index, E element) 方法源代码如下：
/**
* Replaces the element at the specified position in this list with
* the specified element.
* 用指定的元素替换此list中指定位置的元素
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
set(int index, E element) 方法时间复杂度
set(int index, E element) 方法时间复杂度为 O(1)
2.5 ArrayList 获取元素
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = Lists.newArrayListWithExpectedSize(20);
arrayList.add("hello");
arrayList.get(0);
}
}
get(int index) 方法源代码如下：
/**
* Returns the element at the specified position in this list.
* 返回此list中指定位置的元素。
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
get(int index) 方法时间复杂度
get(int index) 方法时间复杂度为 O(1)
2.6 ArrayList 遍历的几种方式
2.6.1 fori 遍历 ArrayList
Fori 遍历 ArrayList 的优缺点：
**优点：**可以取到下标
**缺点：**代码比较繁琐
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = Lists.newArrayListWithExpectedSize(20);
for (int i = 0; i < arrayList.size(); i ++) {
System.out.println(arrayList.get(i))
}
}
}
2.6.2 foreach 遍历 ArrayList
Foreach 遍历 ArrayList 的优缺点：
优点： 代码相比 fori 方法更加简洁
缺点： 无法获取当前元素的下标
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = Lists.newArrayListWithExpectedSize(20);
for (String item : arrayList) {
System.out.println(item);
}
}
}
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = Lists.newArrayListWithExpectedSize(20);
arrayList.forEach(a -> {
System.out.println(a);
});
}
}
2.6.3 Iterator 迭代器遍历 ArrayList
iterator 遍历 ArrayList 的优缺点：
优点： 可以在遍历时进行元素移除操作
缺点： 无法获取当前元素的下标
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>(20);
Iterator iterator = arrayList.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>(20);
Iterator iterator = arrayList.iterator();
for (Iterator item = iterator; item.hasNext(); ) {
System.out.println(item.next());
}
}
}
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>(20);
ListIterator<String> iterator = arrayList.listIterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
while (iterator.hasPrevious()) {
System.out.println(iterator.previous());
}
}
}
2.6.4 stream 流遍历 ArrayList
class ArrayListTest {
public void static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>(20);
arrayList.stream().forEach(item -> {
System.out.println(item);
});
}
}
2.6.5 parallelStream() 遍历 ArrayList
class ArrayListTest {
public void static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>(20);
arrayList.parallelStream().forEach(item -> {
System.out.println(item);
});
}
}
2.7 ArrayList 元素移除
2.7.1 移除指定下标的元素 remove(int index)
移除指定下标位置的元素。将其所有后续元素向左移动，将最后一个元素设置为 null 以便 GC
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>(20);
arrayList.add("hello");
arrayList.remove(0);
}
}
2.7.2 移除指定元素第一次出现的元素
从集合中删除第一次出现的指定元素。如果集合不包含该元素，则保持不变。
class ArrayListTest {
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>(20);
arrayList.add("hello");
arrayList.remove("hello");
}
}
remove(Object o) 方法的源代码如下：
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
* 从此list中删除第一次出现的指定元素。如果list不包含该元素，则保持不变。更正式地，
* 删除具有最低索引 i 的元素，使得 o==null ? get(i)==null : o.equals(get(i))。
* 如果此list包含指定的元素，则返回 true。
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
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 remove method that skips bounds checking and does not
* return the value removed.
* 跳过边界检查并且不返回移除的值的私有方法。
*/
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
}
2.7.3 从集合中删除包含在指定集合中的所有元素 removeAll(Collection<?> c)
@TODO
2.8 ArrayList 扩容和边界问题
初始化一个空 ArrayList 对象时默认容量为 0 ，在第一次插入元素时扩容，默认扩容为 10，若在此扩容，则为上次容量的 1.5 倍。
ArrayList 最小容量为 0，最大容量根据 JVM 平台的不同且在 JVM 内存足够的情况下，大多接近于 Integer.MAX_VALUE，HotSpot VM 最大容量为 Integer.MAX_VALUE。超过最大容量时将最大容量设置为 Integer.MAX_VALUE。
扩容相关源代码：
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code - 预防溢出代码
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
* 增加容量以确保它至少可以容纳由最小容量参数指定的元素数量。
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code - 预防溢出
// oldCapacity 大小等于 elementData.length，元素数量
int oldCapacity = elementData.length;
// 新的 capacity 为 oldCapacity + (oldCapacity >> 1)
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果 newCapacity 小于 minCapacity，则将 minCapacity 赋值给 newCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果 newCapacity 的值大于 MAX_ARRAY_SIZE-(Integer.MAX_VALUE - 8)，则启用 hugeCapacity，hugeCapacity 允许最大容量大小为 Integer.MAX_VALUE
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);
}
/**
* list 大容量允许存储元素的个数，Integer.MAX_VALUE
* @param minCapacity
* @return
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow - 溢出
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
2.9 ArrayList 线程安全问题
ArrayList 实现不同线程同步的，如果多个线程同时访问一个 ArrayList 实例，并且至少有一个线程在结构上修改了集合，它必须在外部同步(结构修改是添加或删除一个或多个元素，或显式调整后备数组大小的任何操作；仅设置元素的值不是结构修改)；这通常是通过同步一些自然封装的对象来实现的。
使用 Collections#synchronizedList 方法包装 ArrayList 以实现线程同步，这最好在创建时完成，以防止对集合的意外不同步访问：
使用 CopyOnWriteArrayList 实现同步对象：
CopyOnWriteArrayList 中元素结构修改时是加锁的，修改时进行 copy。读的时候不需要加锁，如果读的时候有多个线程正在想 CopyOnWriteArrayList 添加数据，读还是会读到旧的数据，因为锁的时候不会锁住旧的 CopyOnWriteArrayList。有点像 ThreadLocal 。
2.10 ArrayList 总结
- 创建ArrayList实例对象时最好根据业务数据量指定初始容量，防止扩容影响性能；
- 在遍历集合时只允许在 Iterator 迭代器中移除元素，否则会报错 ConcurrentModificationException 异常；
- 多线程操作时请手动保证线程同步(Collections、CopyOnWriteArrayList)；