终于，我读懂了所有Java集合——List篇
ArrayList基于数组实现，无容量的限制。在执行插入元素时可能要扩容，在删除元素时并不会减小数组的容量，在查找元素时要遍历数组，对于非null的元素采取equals的方式寻找。是非线程安全的。注意点：（1）ArrayList随机存取元素时间复杂度O(1)，插入删除操作需大量移动元素，效率较低（2）为了节约内存，当新建容器为空时，会共享Object[] EMPT...
·
ArrayList
基于数组实现，无容量的限制。
在执行插入元素时可能要扩容，在删除元素时并不会减小数组的容量，在查找元素时要遍历数组，对于非null的元素采取equals的方式寻找。
是非线程安全的。
注意点：
（1）ArrayList随机存取元素时间复杂度O(1)，插入删除操作需大量移动元素，效率较低
（2）为了节约内存，当新建容器为空时，会共享
Object[] EMPTY_ELEMENTDATA = {}和
Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}空数组
（3）容器底层采用数组存储，每次扩容为1.5倍
（4）ArrayList的实现中大量地调用了Arrays.copyof()和System.arraycopy()方法，其实Arrays.copyof()内部也是调用System.arraycopy()。System.arraycopy()为Native方法
（5）两个ToArray方法
Object[] toArray()方法。该方法有可能会抛出java.lang.ClassCastException异常
<T> T[] toArray(T[] a)方法。该方法可以直接将ArrayList转换得到的Array进行整体向下转型
（6）ArrayList可以存储null值
（7）ArrayList每次修改（增加、删除）容器时，都是修改自身的modCount；在生成迭代器时，迭代器会保存该modCount值，迭代器每次获取元素时，会比较自身的modCount与ArrayList的modCount是否相等，来判断容器是否已经被修改，如果被修改了则抛出异常（fast-fail机制）。
源码解析
package java.util;
import sun.misc.SharedSecrets;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
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;
/**
* 元素数量
*
*/
private int size;
/**
* 带有容量的构造方法
*
* @param 数组的初始容量
* @throws IllegalArgumentException 参数为负
*/
public ArrayList(int initialCapacity) {
// 参数>0
if (initialCapacity > 0) {
// new一个object数组赋给elementData
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {// 参数=0
// 将空数组赋给elementData
this.elementData = EMPTY_ELEMENTDATA;
} else {
//参数<0,抛出IllegalArgumentException异常
throw new IllegalArgumentException("Illegal Capacity: " +
initialCapacity);
}
}
/**
* 不带参数构造方法
*/
public ArrayList() {
// 将空数组赋给elementData
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 带参数Collection的构造方法
*
* @param c
* 其元素将被放入此列表中的集合
* @throws NullPointerException
* 集合为空
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray可能（错误地）不返回对象[]（JAVA BUG编号6260652）
if (elementData.getClass() != Object[].class)
// Array.copyOf()主要用来将原数组拷贝到一个新的数组，适用于数组扩容。
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 空数组
this.elementData = EMPTY_ELEMENTDATA;
}
}
/**
* 因为容量基本会大于实际元素的数量。内存紧张时，可以调用该方法调整容量为元素实际数量。
* 如果确定不会有元素添加进来时也可以调用该方法来节约空间
*/
public void trimToSize() {
modCount++;
// 如果size小于length
if (size < elementData.length) {
// 将elementData设置大小为size
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
/**
* 使用指定参数设置数组容量
*
* @param minCapacity
* 所需的最小容量
*/
public void ensureCapacity(int minCapacity) {
// 如果数组为空，容量预取0，否则去默认值(10)
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 static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
/**
* 得到最小扩容量
*
* @param minCapacity
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
/**
* 判断是否需要扩容
*
* @param minCapacity
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 最小需要空间比elementData的内存空间大
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 数组的最大容量，可能会导致内存溢出
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 扩容
*
* @param minCapacity
* 所需的最小容量
*/
private void grow(int minCapacity) {
// ArrayList中elementData的内存空间长度
int oldCapacity = elementData.length;
// 扩容原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 判断新数组的容量够不够
// 不够就将数组长度设置为需要的长度
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 预设值>默认的最大值,检查溢出
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 放到新数组中
elementData = Arrays.copyOf(elementData, newCapacity);
}
/**
* 检查是否溢出，若没有溢出，返回最大整数值或默认最大值
*
* @param minCapacity
* @return
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // 溢出
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
/**
* 返回ArrayList的大小
*
* @return ArrayList中的元素数量
*/
public int size() {
return size;
}
/**
* 返回是否为空
*
* @return true 如果ArrayList中无元素
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 是否包含一个数 返回bool
*
* @param o
* 被检查元素
* @return true 如果ArrayList中包含o元素
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
* 返回一个值首次出现的位置，不存在就返回-1。时间复杂度O(N)
*
* 返回第一个null
* @param o
* @return
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i] == null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* 返回一个值最后一次出现的位置，不存在就返回-1。时间复杂度O(N)
* 返回最后一个null
* @param o
* @return
*/
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;
}
/**
* 返回副本，元素本身没有被复制，复制过程中数组发生改变会抛出异常
*
* @return v ArrayList副本
*/
public Object clone() {
try {
// 调用Object类的clone方法得到ArrayList副本
ArrayList<?> v = (ArrayList<?>) super.clone();
// 调用copyOf，将ArrayList的elementData数组赋给副本的elementData数组
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);
}
}
/**
* 转换为Object数组
*
* @return 一个数组包含所有列表中的元素
*/
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
/**
* 将ArrayList里面的元素赋值到一个数组中去
* a的长度小于ArrayList的长度，直接调用Arrays类的copyOf
* a的长度大于ArrayList的长度，调用System.arraycopy，然后把size位置赋值为空。
*
* @param a
* 如果它的长度大的话，列表元素存储在这个数组中; 否则分配一个新数组。
* @return 一个包含ArrayList元素的数组
* @throws ArrayStoreException
* 将与数组类型不兼容的值赋值给数组元素时抛出的异常
* @throws NullPointerException
* 数组为空
*/
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
// 创建一个新的a的运行时类型数组，内容不变
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
/**
* 返回指定位置的值
* @param index
* @return
*/
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
/**
* 返回指定位置的值，先检查是否超出数组长度
*
* @param index
* 元素的索引
* @return ArrayList中指定位置的元素
* @throws IndexOutOfBoundsException
* {@inheritDoc}
*/
public E get(int index) {
// 检查是否越界
rangeCheck(index);
// 返回ArrayList的elementData数组index位置的元素
return elementData(index);
}
/**
* 设置指定位置为一个新值，返回之前的值
*
* @param index
* 要替换的元素的索引
* @param element
* 要存储在指定位置的元素
* @return 之前在指定位置的元素
* @throws IndexOutOfBoundsException
* {@inheritDoc}
*/
public E set(int index, E element) {
// 检查越界
rangeCheck(index);
// 获取当前位置的值
E oldValue = elementData(index);
// 将element赋值到index位置
elementData[index] = element;
return oldValue;
}
/**
* 添加一个值，首先会确保容量
*
* @param e
* 要添加到此列表中的元素
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
// 扩容
ensureCapacityInternal(size + 1);
// 将e赋值给elementData的size+1的位置
elementData[size++] = e;
return true;
}
/**
* index位置添加元素element，会检查添加的位置和容量
*
* @param index
* 指定元素将被插入的索引
* @param element
* 要插入的元素
* @throws IndexOutOfBoundsException
* {@inheritDoc}
*/
public void add(int index, E element) {
// 判断越界
rangeCheckForAdd(index);
// 扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将elementData从index位置开始，复制到elementData的index+1开始的连续空间
System.arraycopy(elementData, index, elementData, index + 1,size - index);
// 在index位置赋值element
elementData[index] = element;
// ArrayList的大小++
size++;
}
/**
* 移除index位置的元素,会检查去除的位置
*
* @param index
* 要删除的元素的索引
* @return 删除的元素
* @throws IndexOutOfBoundsException
* {@inheritDoc}
*/
public E remove(int index) {
// 判断越界
rangeCheck(index);
modCount++;
// 读取旧值
E oldValue = elementData(index);
// 获取index位置开始到最后一个位置的个数
int numMoved = size - index - 1;
if (numMoved > 0)
// index+1位置开始拷贝到从index开始的空间
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
elementData[--size] = null; // 便于垃圾回收器回收
return oldValue;
}
/**
* 移除对象为O的元素，跟indexOf方法思想基本一致
* @param o
* 要从该列表中删除的元素（如果存在）
* @return true 如果这个列表包含指定的元素
*/
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;
}
/**
* 快速删除指定位置的值，不需要检查和返回值
*
* @param index
*/
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; // 便于垃圾回收器回收
}
/**
* 清空数组，把每一个值设为null,方便垃圾回收(不同于reset，数组默认大小有改变的话不会重置)
*/
public void clear() {
modCount++;
// 便于垃圾回收器回收
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
/**
* 添加一个集合的元素到末端
*
* @param c
* 包含要添加到此列表中的元素的集合
* @return true 如果该列表因添加而改变
* @throws NullPointerException
* 如果指定的集合是空的
*/
public boolean addAll(Collection<? extends E> c) {
// c转换为数组a
Object[] a = c.toArray();
// a占的内存空间长度赋值给numNew
int numNew = a.length;
// 扩容至size + numNew
ensureCapacityInternal(size + numNew);
// 将a的第0位开始拷贝至elementData的size位开始，拷贝长度为numNew
System.arraycopy(a, 0, elementData, size, numNew);
// 将size增加numNew
size += numNew;
return numNew != 0;
}
/**
* 从第index位开始，将c全部拷贝到ArrayList
*
* @param index
* 在哪个索引开始插入
* @param c
* 包含要添加到此列表中的元素的集合
* @return true 如果该列表因添加而改变
* @throws IndexOutOfBoundsException
* {@inheritDoc}
* @throws NullPointerException
* 如果指定的集合是空的
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
// 将c转换为数组a
Object[] a = c.toArray();
int numNew = a.length;
// 扩容至size + numNew
ensureCapacityInternal(size + numNew);
// 获取需要添加的个数
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;
}
/**
* 删除指定范围元素。
*
* @throws IndexOutOfBoundsException
* if {@code fromIndex} or {@code toIndex} is out of range ({@code fromIndex < 0 ||
* fromIndex >= size() || toIndex > size() || toIndex <
* fromIndex})
*/
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;// 后段保留的长度
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// 便于垃圾回收
int newSize = size - (toIndex - fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
/**
* 检查index是否超出数组长度
*/
private void rangeCheck(int index) {
// 如果下标超过ArrayList的数组长度
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;
}
/**
* ArrayList移除集合c中的所有元素
*
* @param c
* 包含要从此列表中移除的元素的集合
* @return {@code true} 如果该列表因移除而改变
* @throws ClassCastException
* if the class of an element of this list is incompatible with
* the specified collection (<a
* href="Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException
* if this list contains a null element and the specified
* collection does not permit null elements (<a
* href="Collection.html#optional-restrictions">optional</a>),
* or if the specified collection is null
* @see Collection#contains(Object)
*/
public boolean removeAll(Collection<?> c) {
// 如果c为空，则抛出空指针异常
Objects.requireNonNull(c);
// 调用batchRemove移除c中的元素
return batchRemove(c, false);
}
/**
* 仅保留指定集合c中的元素
*
* @param c
* collection containing elements to be retained in this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException
* if the class of an element of this list is incompatible with
* the specified collection (<a
* href="Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException
* if this list contains a null element and the specified
* collection does not permit null elements (<a
* href="Collection.html#optional-restrictions">optional</a>),
* or if the specified collection is null
* @see Collection#contains(Object)
*/
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
// 调用batchRemove保留c中的元素
return batchRemove(c, true);
}
/**
* 根据complement值，将ArrayList中包含c中元素的元素删除或者保留
*
* @param c
* @param complement
* true时从数组保留指定集合中元素的值，为false时从数组删除指定集合中元素的值。
* @return 数组中重复的元素都会被删除(而不是仅删除一次或几次)，有任何删除操作都会返回true
*/
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
// 定义一个w，一个r，两个同时右移
int r = 0, w = 0;
boolean modified = false;
try {
// r先右移
for (; r < size; r++)
// 如果c中不包含elementData[r]这个元素
if (c.contains(elementData[r]) == complement)
// 则直接将r位置的元素赋值给w位置的元素，w自增
elementData[w++] = elementData[r];
} finally {
// 防止抛出异常导致上面r的右移过程没完成
if (r != size) {
// 将r未右移完成的位置的元素赋值给w右边位置的元素
System.arraycopy(elementData, r,
elementData, w,
size - r);
// 修改w值增加size-r
w += size - r;
}
// 如果有被覆盖掉的元素，则将w后面的元素都赋值为null
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;// 改变的次数
// 新的大小为保留的元素的个数
size = w;
modified = true;
}
}
return modified;
}
/**
* 保存数组实例的状态到一个流（即序列化）。写入过程数组被更改会抛出异常
*
* @serialData The length of the array backing the <tt>ArrayList</tt>
* instance is emitted (int), followed by all of its elements
* (each an <tt>Object</tt>) in the proper order.
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
// 执行默认的反序列化/序列化过程。将当前类的非静态和非瞬态字段写入此流
s.defaultWriteObject();
// 写入大小
s.writeInt(size);
// 写入所有元素
for (int i = 0; i < size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/**
* 从流中重构ArrayList实例（即反序列化）。
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// 执行默认的序列化/反序列化过程
s.defaultReadObject();
// 读入数组长度
s.readInt(); // ignored
if (size > 0) {
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
Object[] a = elementData;
// 读入所有元素
for (int i = 0; i < size; i++) {
a[i] = s.readObject();
}
}
}
/**
* 返回一个从index开始的ListIterator对象
*
* @throws IndexOutOfBoundsException
* {@inheritDoc}
*/
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: " + index);
return new ListItr(index);
}
/**
* 返回一个ListIterator对象，ListItr为ArrayList的一个内部类，实现了ListIterator<E> 接口
*
* @see #listIterator(int)
*/
public ListIterator<E> listIterator() {
return new ListItr(0);
}
/**
* 返回一个Iterator对象，Itr为ArrayList的一个内部类，实现了Iterator<E>接口
*
* @return an iterator over the elements in this list in proper sequence
*/
public Iterator<E> iterator() {
return new Itr();
}
/**
* 通用的迭代器实现
*/
private class Itr implements Iterator<E> {
int cursor; // 下一个元素的索引，默认为0
int lastRet = -1; // 上次访问的元素的位置
int expectedModCount = modCount;// 迭代过程修改数组抛出异常
// 是否还有下一个
public boolean hasNext() {
return cursor != size;
}
// 下一个元素
@SuppressWarnings("unchecked")
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];// 设置访问的位置并返回这个值
}
// 删除元素
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 ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
// 检查数组是否被修改
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
/**
* 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();
}
}
}
/**
*
* 该方法返回的是父list的一个视图，fromIndex（包含）到toIndex（不包含）。fromIndex=toIndex 表示子list为空
*/
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
/**
* 安全检查
*
* @param fromIndex
* @param toIndex
* @param size
*/
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > size)
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
}
/**
* 子数组
*/
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
public E set(int index, E e) {
rangeCheck(index);
checkForComodification();
E oldValue = ArrayList.this.elementData(offset + index);
ArrayList.this.elementData[offset + index] = e;
return oldValue;
}
public E get(int index) {
rangeCheck(index);
checkForComodification();
return ArrayList.this.elementData(offset + index);
}
public int size() {
checkForComodification();
return this.size;
}
public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = parent.remove(parentOffset + index);
this.modCount = parent.modCount;
this.size--;
return result;
}
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
parent.removeRange(parentOffset + fromIndex,
parentOffset + toIndex);
this.modCount = parent.modCount;
this.size -= toIndex - fromIndex;
}
public boolean addAll(Collection<? extends E> c) {
return addAll(this.size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
int cSize = c.size();
if (cSize == 0)
return false;
checkForComodification();
parent.addAll(parentOffset + index, c);
this.modCount = parent.modCount;
this.size += cSize;
return true;
}
public Iterator<E> iterator() {
return listIterator();
}
public ListIterator<E> listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
final int offset = this.offset;
return new ListIterator<E>() {
int cursor = index;
int lastRet = -1;
int expectedModCount = ArrayList.this.modCount;
public boolean hasNext() {
return cursor != SubList.this.size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= SubList.this.size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[offset + (lastRet = i)];
}
public boolean hasPrevious() {
return cursor != 0;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[offset + (lastRet = i)];
}
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = SubList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[offset + (i++)]);
}
// update once at end of iteration to reduce heap write
// traffic
lastRet = cursor = i;
checkForComodification();
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
SubList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(offset + lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
SubList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (expectedModCount != ArrayList.this.modCount)
throw new ConcurrentModificationException();
}
};
}
/**
* 返回指定范围的子数组
*
* @param fromIndex
* @param toIndex
* @return
*/
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, offset, fromIndex, toIndex);
}
private void rangeCheck(int index) {
if (index < 0 || index >= this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: " + index + ", Size: " + this.size;
}
private void checkForComodification() {
if (ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}
public Spliterator<E> spliterator() {
checkForComodification();
return new ArrayListSpliterator<E>(ArrayList.this, offset,
offset + this.size, this.modCount);
}
}
/**
* Java 8 lambda 使用流遍历数组
*/
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked") final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i = 0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/**
* 为了并行遍历元素而设计的一个迭代器
* @return a {@code Spliterator} over the elements in this list
* @since 1.8
*/
@Override
public Spliterator<E> spliterator() {
return new ArrayListSpliterator<>(this, 0, -1, 0);
}
/**
* Index-based split-by-two, lazily initialized Spliterator
*/
static final class ArrayListSpliterator<E> implements Spliterator<E> {
/**
//forEach（）
private final ArrayList<E> list;
private int index; // current index, modified on advance/split
private int fence; // -1 until used; then one past last index
private int expectedModCount; // initialized when fence set
/**
* Create new spliterator covering the given range
*/
ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
int expectedModCount) {
this.list = list; // OK if null unless traversed
this.index = origin;
this.fence = fence;
this.expectedModCount = expectedModCount;
}
private int getFence() { // initialize fence to size on first use
int hi; // (a specialized variant appears in method forEach)
ArrayList<E> lst;
if ((hi = fence) < 0) {
if ((lst = list) == null)
hi = fence = 0;
else {
expectedModCount = lst.modCount;
hi = fence = lst.size;
}
}
return hi;
}
public ArrayListSpliterator<E> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid) ? null : // divide range in half unless too small
new ArrayListSpliterator<E>(list, lo, index = mid,
expectedModCount);
}
public boolean tryAdvance(Consumer<? super E> action) {
if (action == null)
throw new NullPointerException();
int hi = getFence(), i = index;
if (i < hi) {
index = i + 1;
@SuppressWarnings("unchecked") E e = (E) list.elementData[i];
action.accept(e);
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
return false;
}
public void forEachRemaining(Consumer<? super E> action) {
int i, hi, mc; // hoist accesses and checks from loop
ArrayList<E> lst;
Object[] a;
if (action == null)
throw new NullPointerException();
if ((lst = list) != null && (a = lst.elementData) != null) {
if ((hi = fence) < 0) {
mc = lst.modCount;
hi = lst.size;
} else
mc = expectedModCount;
if ((i = index) >= 0 && (index = hi) <= a.length) {
for (; i < hi; ++i) {
@SuppressWarnings("unchecked") E e = (E) a[i];
action.accept(e);
}
if (lst.modCount == mc)
return;
}
}
throw new ConcurrentModificationException();
}
public long estimateSize() {
return (long) (getFence() - index);
}
public int characteristics() {
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
}
}
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
int removeCount = 0;
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
for (int i = 0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked") final E element = (E) elementData[i];
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed
// elements
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
for (int i = 0, j = 0; (i < size) && (j < newSize); i++, j++) {
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
for (int k = newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
@Override
@SuppressWarnings("unchecked")
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
for (int i = 0; modCount == expectedModCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
}LinkedList
java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractList<E>
java.util.AbstractSequentialList<E>
java.util.LinkedList<E>List 接口的链接列表实现。实现所有可选的列表操作，并且允许所有元素（包括 null）。
除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。
此类实现 Deque 接口，为 add、poll 提供先进先出队列操作，以及其他堆栈和双端队列操作。
所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。
操作效率：大部分效率都是o(n)的
同步：
注意，此实现不是同步的。如果多个线程同时访问一个链接列表，而其中至少一个线程从结构上修改了该列表，则它必须 保持外部同步。（结构修改指添加或删除一个或多个元素的任何操作；仅设置元素的值不是结构修改。）这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedList 方法来“包装”该列表。最好在创建时完成这一操作，以防止对列表进行意外的不同步访问，如下所示：
List list = Collections.synchronizedList(new LinkedList(...));iterator ：
此类的 iterator 和 listIterator 方法返回的迭代器是快速失败 的：在迭代器创建之后，如果从结构上对列表进行修改，除非通过迭代器自身的 remove 或 add 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒将来不确定的时间任意发生不确定行为的风险。
注意，迭代器的快速失败行为不能得到保证，一般来说，存在不同步的并发修改时，不可能作出任何硬性保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的方式是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。
源码解析
package java.util;
import java.util.function.Consumer;
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
/**
* 元素数量
*/
transient int size = 0;
/**
* 首结点引用
*/
transient Node<E> first;
/**
* 尾节点引用
*/
transient Node<E> last;
/**
* 无参构造方法
*/
public LinkedList() {
}
/**
* 通过一个集合初始化，元素顺序有这个集合的迭代器返回顺序决定
*
* @param c
* 其元素将被放入此列表中的集合
* @throws NullPointerException
* 如果指定的集合是空的
*/
public LinkedList(Collection<? extends E> c) {
// 调用无参构造
this();
// 添加所有的元素
addAll(c);
}
/**
* 头插，内部使用
*/
private void linkFirst(E e) {
// 当前首结点
final Node<E> f = first;
// 构建新节点
final Node<E> newNode = new Node<>(null, e, f);
// 将newNode作为首节点
first = newNode;
// 如果原首节点为null，即原链表为null，则链表尾节点也设置为newNode
if (f == null)
last = newNode;
else // 否则，原首节点的prev设置为newNode
f.prev = newNode;
size++; // 长度+1
modCount++; // 修改次数+1
}
/**
* 尾插
*/
void linkLast(E e) {
// 获取尾结点
final Node<E> l = last;
// 构建新节点
final Node<E> newNode = new Node<>(l, e, null);
// newNode作为尾节点
last = newNode;
// 如果原尾节点为null，即原链表为null，则链表首节点也设置为newNode
if (l == null)
first = newNode;
else // 否则，原尾节点的next设置为newNode
l.next = newNode;
size++;
modCount++;
}
/**
* 在非空节点succ前插入节点值e
*/
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;
// 构建新节点
final Node<E> newNode = new Node<>(pred, e, succ);
// 设置newNode为succ的前节点
succ.prev = newNode;
// 如果succ.prev为null，即succ为首节点，则将newNode设置为首节点
if (pred == null)
first = newNode;
else // 如果succ不是首节点
pred.next = newNode;
size++;
modCount++;
}
/**
* 删除首结点，返回存储的元素，内部使用
*/
private E unlinkFirst(Node<E> f) {
// 获取首结点存储的元素
final E element = f.item;
// 获取首结点的后继结点
final Node<E> next = f.next;
// 删除首结点
f.item = null;
f.next = null; // 便于垃圾回收
// 首结点后继结点设为首结点
first = next;
// 如果原来首结点的后继结点为空，则尾结点设为null
// 否则，原来首结点的后继结点的前驱结点设为null
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
// 返回原来首结点存储的元素
return element;
}
/**
* 删除尾结点，返回存储的元素，内部使用
*/
private E unlinkLast(Node<E> l) {
// 获取尾结点存储的元素
final E element = l.item;
// 获取尾结点的前驱结点
final Node<E> prev = l.prev;
// 删除尾结点
l.item = null;
l.prev = null; // help GC
// 原来尾结点的前驱结点设为尾结点
last = prev;
// 如果原来尾结点的前驱结点为空，则首结点设为null
// 否则，原来尾结点的前驱结点的后继结点设为null
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
// 返回原来尾结点存储的元素
return element;
}
/**
* 删除指定非空结点，返回存储的元素
*/
E unlink(Node<E> x) {
// 获取指定非空结点存储的元素
final E element = x.item;
// 获取指定非空结点的后继结点
final Node<E> next = x.next;
// 获取指定非空结点的前驱结点
final Node<E> prev = x.prev;
/**
* 如果指定非空结点的前驱结点为空，则指定非空结点的后继结点设为首结点
* 否则，指定非空结点的后继结点设为指定非空结点的前驱结点的后继结点，
* 指定非空结点的前驱结点设为null
*/
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
/**
* 如果指定非空结点的后继结点为空，则指定非空结点的前驱结点设为尾结点
* 否则，指定非空结点的前驱结点设为指定非空结点的后继结点的前驱结点，
* 指定非空结点的后继结点设为null
*/
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
// 指定非空结点存储的元素设为null
x.item = null;
size--;
modCount++;
// 返回指定非空结点存储的元素
return element;
}
/**
* 获取首结点存储的元素
*
* @return 首结点存储的元素
* @throws NoSuchElementException
* 如果链表为空
*/
public E getFirst() {
// 获取首结点引用
final Node<E> f = first;
// 如果首结点为空，则抛出无该元素异常
if (f == null)
throw new NoSuchElementException();
// 返回首结点存储的元素
return f.item;
}
/**
* 获取尾结点存储的元素
*
* @return 尾结点存储的元素
* @throws NoSuchElementException
* 如果链表为空
*/
public E getLast() {
// 获取尾结点引用
final Node<E> l = last;
// 如果尾结点为空，则抛出无该元素异常
if (l == null)
throw new NoSuchElementException();
// 返回尾结点存储的元素
return l.item;
}
/**
* 删除首结点，返回存储的元素
*
* @return 首结点存储的元素
* @throws NoSuchElementException
* 如果链表为空
*/
public E removeFirst() {
// 获取首结点引用
final Node<E> f = first;
// 如果首结点为空，则抛出无该元素异常
if (f == null)
throw new NoSuchElementException();
// 删除首结点，返回存储的元素
return unlinkFirst(f);
}
/**
* 删除尾结点，返回存储的元素
*
* @return 尾结点存储的元素
* @throws NoSuchElementException
* 如果链表为空
*/
public E removeLast() {
// 获取尾结点引用
final Node<E> l = last;
// 如果尾结点为空，则抛出无该元素异常
if (l == null)
throw new NoSuchElementException();
// 删除尾结点，返回存储的元素
return unlinkLast(l);
}
/**
* 头部插入指定元素
*
* @param e
* 要添加的元素
*/
public void addFirst(E e) {
// 通过头插法来插入指定元素
linkFirst(e);
}
/**
* 尾部插入指定元素，该方法等价于add()
*
* @param e
* the element to add
*/
public void addLast(E e) {
linkLast(e);
}
/**
* 判断是否包含指定元素
*
* @param o
* 判断链表是否包含的元素
* @return {@code true} 如果链表包含指定的元素
*/
public boolean contains(Object o) {
// 返回指定元素的索引位置，不存在就返回-1，然后比较返回bool值
return indexOf(o) != -1;
}
/**
* 获取元素数量
*
* @return 元素数量
*/
public int size() {
return size;
}
/**
* 插入指定元素，返回操作结果,默认添加到末尾作为最后一个元素
*
* @param e
* 要添加到此链表中的元素
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
// 通过尾插法来插入指定元素
linkLast(e);
return true;
}
/**
* 删除指定元素，默认从first节点开始，删除第一次出现的那个元素
*
* @param o
* 要从该列表中删除的元素（如果存在）
* @return {@code true} 如果这个列表包含指定的元素
*/
public boolean remove(Object o) {
// 会根据是否为null分开处理。若值不是null，会用到对象的equals()方法
if (o == null) {
// 遍历链表，查找到指定元素后删除该结点，返回true
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
// 查找失败
return false;
}
/**
* 将集合插入到链表尾部
*
* @param c
* 包含要添加到此链表中的元素的集合
* @return {@code true} 如果该链表因添加而改变
* @throws NullPointerException
* 如果指定的集合是空的
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/**
* 将集合从指定位置开始插入
*
* @param index
* 在哪个索引处前插入指定集合中的第一个元素
* @param c
* 包含要添加到此链表中的元素的集合
* @return {@code true} 如果该链表因添加而改变
* @throws IndexOutOfBoundsException
* {@inheritDoc}
* @throws NullPointerException
* 如果指定的集合是空的
*/
public boolean addAll(int index, Collection<? extends E> c) {
// 检查索引是否正确（0<=index<=size）
checkPositionIndex(index);
// 得到元素数组
Object[] a = c.toArray();
// 得到元素个数
int numNew = a.length;
// 没有元素，返回false
if (numNew == 0)
return false;
// succ指向当前需要插入节点的位置，pred指向其前一个节点
Node<E> pred, succ;
// 末尾开始添加，当前节点后一个节点为null，前一个节点为尾节点
if (index == size) {
succ = null;
pred = last;
} else {
//当前位置的节点为指定位置的节点，前一个节点为要添加的节点的前一个节点
succ = node(index);
pred = succ.prev;
}
// 遍历数组并添加到列表中
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
// “封装”一个新节点
Node<E> newNode = new Node<>(pred, e, null);
// 原链表为null，新插入的节点作为链表首节点
if (pred == null)
first = newNode;
else
pred.next = newNode; // 存在前节点，前节点向后指向新加的节点
pred = newNode; // pred指针向后移动
}
// 从最后开始添加，则新节点成为尾节点
if (succ == null) {
last = pred;
} else {
pred.next = succ; // 新节点向后指向之前得到的后续第一个节点
succ.prev = pred; // 后续的第一个节点也应改为向前指向最后一个添加的节点
}
size += numNew;
modCount++;
return true;
}
/**
* 删除所有元素
*/
public void clear() {
// 遍历链表，删除所有结点,方便gc回收垃圾
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
// 首尾结点置空
first = last = null;
// 元素数量置0
size = 0;
modCount++;
}
// 位置访问操作
/**
* 获取指定位置的元素
*
* @param index
* 要返回的元素的索引
* @return 该链表中指定位置的元素
* @throws IndexOutOfBoundsException
* {@inheritDoc}
*/
public E get(int index) {
// 判断指定位置是否合法
checkElementIndex(index);
// 返回指定位置的元素
return node(index).item;
}
/**
* 修改指定位置的元素，返回之前元素
*
* @param index
* 要替换的元素的索引
* @param element
* 要存储在指定位置的元素
* @return 之前在指定位置的元素
* @throws IndexOutOfBoundsException
* {@inheritDoc}
*/
public E set(int index, E element) {
// 判断指定位置是否合法
checkElementIndex(index);
// 获取指定位置的结点
Node<E> x = node(index);
// 获取该结点存储的元素
E oldVal = x.item;
// 修改该结点存储的元素
x.item = element;
// 返回该结点存储的之前的元素
return oldVal;
}
/**
* 在指定位置前插入指定元素
* 头插法
* @param index
* 指定元素将被插入的索引
* @param element
* 要插入的元素
* @throws IndexOutOfBoundsException
* {@inheritDoc}
*/
public void add(int index, E element) {
// 判断指定位置是否合法
checkPositionIndex(index);
// 如果指定位置在尾部，则通过尾插法来插入指定元素
if (index == size)
linkLast(element);
else // 如果指定位置不是尾部，则添加到指定位置前
linkBefore(element, node(index));
}
/**
* 删除指定位置的元素，返回之前元素
*
* @param index
* 要删除的元素的索引
* @return 之前在指定位置的元素
* @throws IndexOutOfBoundsException
* {@inheritDoc}
*/
public E remove(int index) {
// 判断指定位置是否合法
checkElementIndex(index);
// 删除指定位置的结点，返回之前元素
return unlink(node(index));
}
/**
* 判断指定位置是否合法
*/
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
/**
* 判断迭代器遍历时或插入元素时指定位置是否合法
*/
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
/**
* 获取越界异常信息
*/
private String outOfBoundsMsg(int index) {
return "Index: " + index + ", Size: " + size;
}
/**
* 判断指定位置是否合法
*
* @param index
*/
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 判断指定位置是否合法
*
* @param index
*/
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 获取指定下标的结点
*/
Node<E> node(int index) {
// 如果指定下标<一半元素数量，则从首结点开始遍历
// 否则，从尾结点开始遍历
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
// 查询操作
/**
* 获取首次出现指定元素的位置 -1表示不存在
* 同样是根据是否为null进行区分
* @param o
* 要查找的元素
* @return the index of the first occurrence of the specified element in
* this list, or -1 if this list does not contain the element
*/
public int indexOf(Object o) {
int index = 0;
if (o == null) {
// 遍历链表，顺序查找指定元素
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
/**
* 获取逆序下首次出现指定元素的位置 -1表示不存在
*
* @param o
* 要查找的元素
* @return the index of the last occurrence of the specified element in this
* list, or -1 if this list does not contain the element
*/
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
// 遍历链表，逆序查找指定元素
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
// 队列操作
/**
* 出队（从前端），获得第一个元素，不存在会返回null，不会删除元素（节点） 获取首元素
*
* @return the head of this list, or {@code null} 如果链表为空
* @since 1.5
*/
public E peek() {
final Node<E> f = first;
// 如果首结点为空，则返回null
// 否则，返回首结点存储的元素
return (f == null) ? null : f.item;
}
/**
* 出队（从前端），不删除元素，若为null会抛出异常而不是返回null 获取首元素
*
* @return the head of this list
* @throws NoSuchElementException
* 如果链表为空
* @since 1.5
*/
public E element() {
// 返回首结点存储的元素
return getFirst();
}
/**
* 出队（从前端），如果不存在会返回null，存在的话会返回值并移除这个元素（节点） 获取并删除首元素
*
* @return the head of this list, or {@code null} 如果链表为空
* @since 1.5
*/
public E poll() {
// 获取首结点引用
final Node<E> f = first;
// 如果首结点为空，则返回null
// 否则，删除首结点，返回首结点存储的元素
return (f == null) ? null : unlinkFirst(f);
}
/**
* 出队（从前端），如果不存在会抛出异常而不是返回null，存在的话会返回值并移除这个元素（节点） 获取并删除首元素
*
* @return the head of this list
* @throws NoSuchElementException
* 如果链表为空
* @since 1.5
*/
public E remove() {
// 删除首结点，返回首结点存储的元素
return removeFirst();
}
/**
* 入队（从后端），始终返回true
*
* 链表不会溢出
* @param e
* the element to add
* @return {@code true} (as specified by {@link Queue#offer})
* @since 1.5
*/
public boolean offer(E e) {
// 通过尾插法插入指定元素，返回操作结果
return add(e);
}
// 双端队列操作
/**
* 入队（从前端），始终返回true
*
* @param e
* 要插入的元素
* @return {@code true} (as specified by {@link Deque#offerFirst})
* @since 1.6
*/
public boolean offerFirst(E e) {
// 通过头插法来插入指定元素
addFirst(e);
return true;
}
/**
* 入队（从后端），始终返回true
*
* @param e
* 要插入的元素
* @return {@code true} (as specified by {@link Deque#offerLast})
* @since 1.6
*/
public boolean offerLast(E e) {
// 通过尾插法来插入指定元素
addLast(e);
return true;
}
/**
* 出队（从前端），获得第一个元素，不存在会返回null，不会删除元素（节点）
*
* @return the first element of this list, or {@code null} 如果链表为空
* @since 1.6
*/
public E peekFirst() {
// 获取首结点引用
final Node<E> f = first;
// 如果首结点为空，则返回null
// 否则，返回首结点存储的元素
return (f == null) ? null : f.item;
}
/**
* 出队（从后端），获得最后一个元素，不存在会返回null，不会删除元素（节点）
*
* @return the last element of this list, or {@code null} 如果链表为空
* @since 1.6
*/
public E peekLast() {
// 获取尾结点引用
final Node<E> l = last;
// 如果尾结点为空，则返回null
// 否则，返回尾结点存储的元素
return (l == null) ? null : l.item;
}
/**
* 出队（从前端），获得第一个元素，不存在会返回null，会删除元素（节点）
*
* @return the first element of this list, or {@code null} if this list is
* empty
* @since 1.6
*/
public E pollFirst() {
// 获取首结点引用
final Node<E> f = first;
// 如果首结点为空，则返回null
// 否则，删除首结点，返回首结点存储的元素
return (f == null) ? null : unlinkFirst(f);
}
/**
* 出队（从后端），获得最后一个元素，不存在会返回null，会删除元素（节点）
*
* @return the last element of this list, or {@code null} if this list is
* empty
* @since 1.6
*/
public E pollLast() {
// 获取尾结点引用
final Node<E> l = last;
// 如果尾结点为空，则返回null
// 否则，删除尾结点，返回尾结点存储的元素
return (l == null) ? null : unlinkLast(l);
}
/**
* 入栈，从前面添加
*
* @param e
* the element to push
* @since 1.6
*/
public void push(E e) {
// 通过头插法来插入指定元素
addFirst(e);
}
/**
* 出栈，返回栈顶元素，从前面移除（会删除）
*
* @return the element at the front of this list (which is the top of the
* stack represented by this list)
* @throws NoSuchElementException
* 如果链表为空
* @since 1.6
*/
public E pop() {
// 删除首结点，返回首结点存储的元素
return removeFirst();
}
/**
* 删除顺序下首次出现的指定元素，返回操作结果
*
* @param o
* 要从该列表中删除的元素（如果存在）
* @return {@code true} 如果链表包含指定的元素
* @since 1.6
*/
public boolean removeFirstOccurrence(Object o) {
// 删除顺序下首次出现的指定元素对应的结点，返回操作结果
return remove(o);
}
/**
* 删除逆序下首次出现的指定元素，返回操作结果
*
* @param o
* 要从该列表中删除的元素（如果存在）
* @return {@code true} 如果链表包含指定的元素
* @since 1.6
*/
public boolean removeLastOccurrence(Object o) {
// 由于LinkedList中允许存放null，因此下面通过两种情况来分别处理
if (o == null) {
// 遍历链表，从尾结点开始查找指定元素
// 如果查找成功，删除该结点，返回true
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
// 查找失败
return false;
}
/**
* Returns a list-iterator of the elements in this list (in proper
* sequence), starting at the specified position in the list. Obeys the
* general contract of {@code List.listIterator(int)}.
* <p>
* <p>
* The list-iterator is <i>fail-fast</i>: if the list is structurally
* modified at any time after the Iterator is created, in any way except
* through the list-iterator's own {@code remove} or {@code add} methods,
* the list-iterator will throw a {@code ConcurrentModificationException}.
* Thus, in the face of concurrent modification, the iterator fails quickly
* and cleanly, rather than risking arbitrary, non-deterministic behavior at
* an undetermined time in the future.
*
* @param index
* index of the first element to be returned from the
* list-iterator (by a call to {@code next})
* @return a ListIterator of the elements in this list (in proper sequence),
* starting at the specified position in the list
* @throws IndexOutOfBoundsException
* {@inheritDoc}
* @see List#listIterator(int)
*/
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
public boolean hasPrevious() {
return nextIndex > 0;
}
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
/**
* 节点的数据结构，包含前后节点的引用和当前节点
*
* @param <E>
*/
private static class Node<E> {
// 存储的元素
E item;
// 后继结点
Node<E> next;
// 前驱结点
Node<E> prev;
// 前驱结点、存储的元素和后继结点作为参数的构造方法
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
/**
* 返回迭代器
*
* @since 1.6
*/
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}
/**
* 因为采用链表实现，所以迭代器很简单
*/
private class DescendingIterator implements Iterator<E> {
private final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}
/**
* 父类克隆方法
*/
@SuppressWarnings("unchecked")
private LinkedList<E> superClone() {
try {
return (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
/**
* 克隆，浅拷贝
*
* 浅拷贝时，若存储的是对象的引用，拷贝时，对象本身的改变将表现到副本中，而深拷贝不会。
* @return a shallow copy of this {@code LinkedList} instance
*/
public Object clone() {
LinkedList<E> clone = superClone();
// 链表初始化
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// 插入结点
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
// 返回克隆后的对象引用
return clone;
}
/**
* 返回新的数组，数组含有列表中所有元素
*/
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
/**
* Returns an array containing all of the elements in this list in proper
* sequence (from first to last element); the runtime type of the returned
* array is that of the specified array. If the list fits in the specified
* array, it is returned therein. Otherwise, a new array is allocated with
* the runtime type of the specified array and the size of this list.
* <p>
* <p>
* If the list fits in the specified array with room to spare (i.e., the
* array has more elements than the list), the element in the array
* immediately following the end of the list is set to {@code null}. (This
* is useful in determining the length of the list <i>only</i> if the
* caller knows that the list does not contain any null elements.)
* <p>
* <p>
* Like the {@link #toArray()} method, this method acts as bridge between
* array-based and collection-based APIs. Further, this method allows
* precise control over the runtime type of the output array, and may, under
* certain circumstances, be used to save allocation costs.
* <p>
* <p>
* Suppose {@code x} is a list known to contain only strings. The following
* code can be used to dump the list into a newly allocated array of
* {@code String}:
* <p>
*
* <pre>
* String[] y = x.toArray(new String[0]);
* </pre>
*
* <p>
* Note that {@code toArray(new Object[0])} is identical in function to
* {@code toArray()}.
*
* @param a
* the array into which the elements of the list are to be
* stored, if it is big enough; otherwise, a new array of the
* same runtime type is allocated for this purpose.
* @return an array containing the elements of the list
* @throws ArrayStoreException
* if the runtime type of the specified array is not a supertype
* of the runtime type of every element in this list
* @throws NullPointerException
* if the specified array is null
*/
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
a = (T[]) java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size)
a[size] = null;
return a;
}
private static final long serialVersionUID = 876323262645176354L;
/**
* 序列化
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// 默认序列化
s.defaultWriteObject();
// 写入元素数量
s.writeInt(size);
// 遍历链表，写入所有元素
for (Node<E> x = first; x != null; x = x.next)
s.writeObject(x.item);
}
/**
* 反序列化
*/
@SuppressWarnings("unchecked")
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// 默认反序列化
s.defaultReadObject();
// 读取元素数量
int size = s.readInt();
// 遍历链表，读取所有元素并尾部插入
for (int i = 0; i < size; i++)
linkLast((E) s.readObject());
}
/**
* Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
* and <em>fail-fast</em> {@link Spliterator} over the elements in this
* list.
* <p>
* <p>
* The {@code Spliterator} reports {@link Spliterator#SIZED} and
* {@link Spliterator#ORDERED}. Overriding implementations should document
* the reporting of additional characteristic values.
*
* @return a {@code Spliterator} over the elements in this list
* @implNote The {@code Spliterator} additionally reports
* {@link Spliterator#SUBSIZED} and implements {@code trySplit} to
* permit limited parallelism..
* @since 1.8
*/
@Override
public Spliterator<E> spliterator() {
return new LLSpliterator<E>(this, -1, 0);
}
/**
* A customized variant of Spliterators.IteratorSpliterator
*/
static final class LLSpliterator<E> implements Spliterator<E> {
static final int BATCH_UNIT = 1 << 10; // batch array size increment
static final int MAX_BATCH = 1 << 25; // max batch array size;
final LinkedList<E> list; // null OK unless traversed
Node<E> current; // current node; null until initialized
int est; // size estimate; -1 until first needed
int expectedModCount; // initialized when est set
int batch; // batch size for splits
LLSpliterator(LinkedList<E> list, int est, int expectedModCount) {
this.list = list;
this.est = est;
this.expectedModCount = expectedModCount;
}
final int getEst() {
int s; // force initialization
final LinkedList<E> lst;
if ((s = est) < 0) {
if ((lst = list) == null)
s = est = 0;
else {
expectedModCount = lst.modCount;
current = lst.first;
s = est = lst.size;
}
}
return s;
}
public long estimateSize() {
return (long) getEst();
}
public Spliterator<E> trySplit() {
Node<E> p;
int s = getEst();
if (s > 1 && (p = current) != null) {
int n = batch + BATCH_UNIT;
if (n > s)
n = s;
if (n > MAX_BATCH)
n = MAX_BATCH;
Object[] a = new Object[n];
int j = 0;
do {
a[j++] = p.item;
} while ((p = p.next) != null && j < n);
current = p;
batch = j;
est = s - j;
return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
}
return null;
}
public void forEachRemaining(Consumer<? super E> action) {
Node<E> p;
int n;
if (action == null) throw new NullPointerException();
if ((n = getEst()) > 0 && (p = current) != null) {
current = null;
est = 0;
do {
E e = p.item;
p = p.next;
action.accept(e);
} while (p != null && --n > 0);
}
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
}
public boolean tryAdvance(Consumer<? super E> action) {
Node<E> p;
if (action == null) throw new NullPointerException();
if (getEst() > 0 && (p = current) != null) {
--est;
E e = p.item;
current = p.next;
action.accept(e);
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
return false;
}
public int characteristics() {
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
}
}
}
Vector
基于synchronized实现的线程安全的ArrayList，但在插入元素时容量扩充的机制和ArrayList稍有不同，并可通过传入capacityIncrement来控制容量的扩充。
成员变量
protected Object[] elementData;
protected int elementCount;
protected int capacityIncrement;构造方法
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector() {
this(10);
}
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}添加
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
删除
public boolean remove(Object o) {
return removeElement(o);
}
public synchronized boolean removeElement(Object obj) {
modCount++;
int i = indexOf(obj);
if (i >= 0) {
removeElementAt(i);
return true;
}
return false;
}扩容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}获取
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}更新
public synchronized E set(int index, E element) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}包含
public boolean contains(Object o) {
return indexOf(o, 0) >= 0;
}
public synchronized int indexOf(Object o, int index) {
if (o == null) {
for (int i = index ; i < elementCount ; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = index ; i < elementCount ; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}CopyOnWriteArrayList
是一个线程安全、并且在读操作时无锁的ArrayList。
很多时候，我们的系统应对的都是读多写少的并发场景。CopyOnWriteArrayList容器允许并发读，读操作是无锁的，性能较高。至于写操作，比如向容器中添加一个元素，则首先将当前容器复制一份，然后在新副本上执行写操作，结束之后再将原容器的引用指向新容器。
优点
1）采用读写分离方式，读的效率非常高
2）CopyOnWriteArrayList的迭代器是基于创建时的数据快照的，故数组的增删改不会影响到迭代器
缺点
1）内存占用高，每次执行写操作都要将原容器拷贝一份，数据量大时，对内存压力较大，可能会引起频繁GC
2）只能保证数据的最终一致性，不能保证数据的实时一致性。写和读分别作用在新老不同容器上，在写操作执行过程中，读不会阻塞但读取到的却是老容器的数据。
成员变量
/** The lock protecting all mutators */
final transient ReentrantLock lock = new ReentrantLock();
/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;
构造方法
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
final void setArray(Object[] a) {
array = a;
}
添加（有锁，锁内重新创建数组）
final Object[] getArray() {
return array;
}
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}存在则添加（有锁，锁内重新创建数组）
先保存一份数组snapshot，如果snapshot中存在，则直接返回。
如果不存在，那么加锁，获取当前数组current，比较snapshot与current，遍历它们共同长度内的元素，如果发现current中某一个元素等于e，那么直接返回（当然current与snapshot相同就不必看了）；
之后再遍历current单独的部分，如果发现current中某一个元素等于e，那么直接返回；
此时可以去创建一个长度+1的新数组，将e加入。
public boolean addIfAbsent(E e) {
Object[] snapshot = getArray();
return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
addIfAbsent(e, snapshot);
}
private boolean addIfAbsent(E e, Object[] snapshot) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] current = getArray();
int len = current.length;
if (snapshot != current) {
// Optimize for lost race to another addXXX operation
int common = Math.min(snapshot.length, len);
for (int i = 0; i < common; i++)
//如果snapshot与current元素不同但current与e相同，那么直接返回（扫描0到common）
if (current[i] != snapshot[i] && eq(e, current[i]))
return false;
// 如果current中存在e，那么直接返回（扫描commen到len）
if (indexOf(e, current, common, len) >= 0)
return false;
}
Object[] newElements = Arrays.copyOf(current, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
删除（有锁，锁内重新创建数组）
public E remove(int index) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
E oldValue = get(elements, index);
int numMoved = len - index - 1;
if (numMoved == 0)
setArray(Arrays.copyOf(elements, len - 1));
else {
Object[] newElements = new Object[len - 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
setArray(newElements);
}
return oldValue;
} finally {
lock.unlock();
}
}
获取（无锁）
public E get(int index) {
return get(getArray(), index);
}
private E get(Object[] a, int index) {
return (E) a[index];
}更新（有锁，锁内重新创建数组）
public E set(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
E oldValue = get(elements, index);
if (oldValue != element) {
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len);
newElements[index] = element;
setArray(newElements);
} else {
// 为了保持“volatile”的语义，任何一个读操作都应该是一个写操作的结果，
也就是读操作看到的数据一定是某个写操作的结果（尽管写操作没有改变数据本身）。
所以这里即使不设置也没有问题，仅仅是为了一个语义上的补充（就如源码中的注释所言）
// Not quite a no-op; ensures volatile write semantics
setArray(elements);
}
return oldValue;
} finally {
lock.unlock();
}
}包含（无锁）
public boolean contains(Object o) {
Object[] elements = getArray();
return indexOf(o, elements, 0, elements.length) >= 0;
}
private static int indexOf(Object o, Object[] elements,
int index, int fence) {
if (o == null) {
for (int i = index; i < fence; i++)
if (elements[i] == null)
return i;
} else {
for (int i = index; i < fence; i++)
if (o.equals(elements[i]))
return i;
}
return -1;
}List实现类之间的区别
(1) 对于需要快速插入，删除元素，应该使用LinkedList。
(2) 对于需要快速随机访问元素，应该使用ArrayList。
(3) 对于“单线程环境” 或者 “多线程环境，但List仅仅只会被单个线程操作”，此时应该使用非同步的类(如ArrayList)。
对于“多线程环境，且List可能同时被多个线程操作”，此时，应该使用同步的类(如Vector、CopyOnWriteArrayList)。
权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区
更多推荐
71
0- 0
已为社区贡献6条内容
所有评论(0)