JDK Collection 源码分析(2)—— List

时间:2021-09-22 16:26:18

JDK List源码分析

List接口定义了有序集合(序列)。在Collection的基础上,增加了可以通过下标索引访问,以及线性查找等功能。

整体类结构

JDK Collection 源码分析(2)—— List

1.AbstractList

  该类作为List的通用骨架实现,和AbstractCollection一样,也是为了减少实现该接口的工作量。为了实现一个只读的List,仅仅只需要实现get和size方法即可。而对于读写的List,则需要额外覆写set,add和remove。

  该类基于get(int),set(int, Object)等方法实现了Iterator方法,基于随机访问的,所以如果如果是链表,还是得重新实现该方法。

  该类有一个重要的属性:protected transient int modCount = 0;,这个属性用于检测多线程并发的,每次对集合的结构发生了变化(如添加或者删除等,由子类实现控制),modCount就会自增。当创建迭代器的时候,迭代器内部就会用一个属性(expectedModCount)来保存当前modCount的值,用于表示当前的状态。在遍历的过程中,如果另一个线程修改了集合(modCount发生变化),在该线程就会检测到expectedModCountmodCount 不一样,从而抛出并发异常(fast-fail)。(并不严格保证并发控制)

私有内部类:Itr和ListItr

  Itr为最基本的迭代器,基于外部类的get等方法来构建。该类有三个属性:cursor用于记录当前的访问位置,expectedModCount保存当前容器状态,lastRet则保存上次访问的结果。而ListItr继承了Itr,添加了双向遍历的功能

  对于迭代器的实现,和Lua等动态语言的闭包类似。

例如next操作:

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();
}
} public void remove() {
// lastRet<0表示已经删除过一次,不允许连续删除(可以控制越界删除)
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification(); try {
// 调用外部类的删除方法,modCount发生变化
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
// 防止连续删除
lastRet = -1;
// 记录下modCount当前的值
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
} final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}

2.ArrayList

  List接口的动态数组实现,和Vector最大不同之处在于,它是非同步的。如果需要同步,可以使用Collections.synchronizedList或者加锁同步。

  添加元素的时候,如果当前数组已满,则会先执行扩容,再添加。每次扩展增加为原来容量的1/2,如:newCapacity = oldCapacity + (oldCapacity >> 1),如果新计算出来的容量比所需要的小或者溢出,则只扩展至所需的大小:

private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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);
}

  在删除元素的时候,经过移动后,需要把数组最后一个元素的引用置空,否则会存在强引用,GC无法收集而导致内存泄漏。如:

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; // Let gc do its work
}

3.AbstractSequentialList/LinkedList

  AbstractSequentialList抽象类是为了减少实现序列访问存储的工作量,如链表等,该类通过使用ListIterator迭代器来实现父类的get,set等方法,如果要实现链表,仅仅只需要实现该方法的迭代器即可。

  LinkedList继承了该抽象类,并实现了Deque双端队列的接口,底层采用双向链表的方式实现,其并没有沿用父类的一些实现,如对add的实现,父类通过迭代器从头遍历到尾部,后再添加,这里直接通过尾指针在表尾部添加,以实现O(1)的操作。在使用下标遍历访问时,做了点小优化,如果靠近头部,就从头部开始遍历,靠近尾部,则从尾部开始遍历。如下:

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;
}
}