List是有序列,所以定义的接口中都有基于index的各种方法。
public interface List<E> extends Collection<E> {
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.ORDERED);
}
}
AbstractList是List抽象基类,ArrayList
,LinkedList
都是它的子类或孙子类。它采用模版方法模式通过调用抽象方法get(int index)
实现iterator()
基本算法,它有get(int index)
,add(int index, E element)
,remove(int index)
三个抽象方法需要自己去实现。
public E next() {
checkForComodification();
try {
int i = cursor;
E next = get(i);
lastRet = i;
cursor = i + 1;
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
ArrayList是由数组实现,基本操作实现遵循数据结构中的线性表。实现add(int index, E element)
,remove(int index)
,iterator()
方法。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
//默认容器大小,小于10时,第一次扩容
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;
//创建一个空数组
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
}
下面介绍Array对于add,remove,iterator方法的源码实现
add(int index, E element)
方法通过两次数组copy实现的,具体实现是
size+1
是否越界,越界新建长度为原长1.5倍的数组并copy;index
到length-1
的元素复制到index+1
到length-1
;如[1,2,3]在index为2的插入5,步骤2数组为[1, 2, 2, 3],步骤3数组为[1, 5, 2, 3]。
ArrayList初始化的长度为0,第一次加节点时,长度为10。
minCapacity = Math.max(10, length+1)
。
public void add(int index, E element) {
rangeCheckForAdd(index);
//验证大小,判断是否扩容
ensureCapacityInternal(size + 1);
//将index到size的节点,copy到index+1到size
System.arraycopy(elementData, index, elementData, index + 1,size - index);
elementData[index] = element;
size++;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//扩容
private void grow(int minCapacity) {
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);
// copy一个新数组对象
elementData = Arrays.copyOf(elementData, newCapacity);
}
remove(int index)
实现原理是将index+1
到length-1
的元素复制到index
到length-1
。
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;
}
ArrayList
实现了迭代器,是为了避免ArrayList在迭代过程中数组结构发生变化的问题,称为Fail-Fast机制。
Fail-Fast就是一个乐观锁,实现如下。
ArrayList有一个modCount属性,在add()
,remove()
执行开始,modCount++
。ArrayList
创建迭代器对象时,会复制当前modCount
到expectedModCount
,迭代器每次执行next()
,remove()
,forEachRemaining()
时,都判断modCount
是否与expectedModCount
相同,若不相同,则抛出异常。
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
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];
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}