JDK 之 ArrayList 和 LinkedList 源码阅读笔记
Contents
类声明
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
其中
public abstract class AbstractSequentialList<E> extends AbstractList<E>
可以看到,它们的共同点是
- 都继承 AbstractList 类
- 都实现了 List
接口 - 都实现了 Cloneable 接口
- 都实现了 Serializable 接口
区别
ArrayList 实现了 RandomAccess 接口,因为它底层是使用数组(会自动 resize)来维护的,而数组是可随机访问的。
LinkedList 实现了 Deque
共同点
- 它们都不是线程安全的,因为它们的方法并没有任何同步语义
- 它们都是 List 这个数据结构的实现(有序列表)
区别
- 实现上不同。ArrayList 使用的是动态数组来维护该列表,而 LinkedList 使用的是双向链表来实现
- 根据实现的不同,就决定了它们各自的特点:ArrayList 读取性能快(O(1)),而 LinkedList 修改(插入或删除)性能快(O(1))
- 内存占用不同因为链表是使用前后指针来进行维护的,所以要占用一些额外的内存占用,而数组实现的方式则不需要。
注意点
因为 ArrayList 使用的是动态数组来维护,所以为了避免频繁地进行数组的内存分配与复制,最好要事先估算它的大小,然后提供足够的容量大小因子(这个参数只有在 ArrayList 才会有)来初始化它。
扩容的触发条件:
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
即 minCapacity - elementData.length > 0 时,就需要扩容了。扩容源码:
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);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
首先,将大小扩大为原内部维护的数组大小的 oldCapacity + (oldCapacity>>1),即 1.5 倍(右移一位,相当于除以2,即 oldCapacity + oldCapacity/2) 如果扩大后的大小,还是小于 minCapacity ,则 newCapacity = minCapacity,否则是扩大后1.5倍的大小为基准 将再 newCapacity 与 MAX_ARRAY_SIZE 比较,判断是不是超大数组,如果是超大数组,则以 Integer.MAX_VALUE 为最终的扩大大小。
注意,initCapacity 是在一开始的时候,就会 new Object[initCapacity] 大小的Object数组引用的了。
删除元素
如果想在循环里删除元素,一定要用 Iterator 来进行 remove ,而不要使用 List.remove() !!
同步的 List
List list = Collections.synchronizedList(new ArrayList());
通过源码注释可知,这种 List ,在进行迭代的时候,需要手动同步(其他的通过 Collections.synchronizedXXXX() 返回的对象也一样):
* <pre>
* List list = Collections.synchronizedList(new ArrayList());
* ...
* synchronized (list) {
* Iterator i = list.iterator(); // Must be in synchronized block
* while (i.hasNext())
* foo(i.next());
* }
* </pre>
Vector
public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
可以看到它和 ArrayList 实现的接口和继承的类都是一样的。最最主要的区别就是,这个类是线程安全的,因为它的所有涉及线程安全的方法,都添加了 synchronized 关键字来进行同步了。
它和 ArrayList 的扩容大小不同:
int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
capacityIncrement 可以通过构造函数来提供,默认为0,即如果不提供 capacityIncrement 参数,则以2倍的大小来进行扩容。
Vector 还是 Collections.synchronizedList ?
这个问题,首先要考虑你之前是否已经有了 List 的数据。因为如果之前已经有了数据的,但想转换为同步的数据,这时它们的区别是:
Vector : 虽然它有个构造函数,提供以另一个 Collection 类型为参数来进行初始化,不过,这会 *导致复制数据*,即完全是以 Vector 为基准了
public Vector(Collection<? extends E> c) {
elementData = c.toArray();
elementCount = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}
Collections.synchronizedList : 这种方式,只是一种包装,即它不会进行数据复制,底层还是引用了相同的数据结构,只是在方法上提供了同步的语义(synchronized)
final List<E> list;
SynchronizedList(List<E> list) {
super(list);
this.list = list;
}
SynchronizedList(List<E> list, Object mutex) {
super(list, mutex);
this.list = list;
}