ArrayList

LinkedList

描述

可变数组

链表

底层结构

数组：

private transient Object[] elementData;

双向循环链表：
class Node<E> {

        E item;

        Node<E> next;

        Node<E> prev;
}

特性

序列化

支持

支持

线程安全性

1非线程安全
2快速失败机制（通过modCount）
3 Collections.synchronizedList(new ArrayList(...));

1 非线程安全
2快速失败机制（通过modCount）

随机访问

支持，下标快速访问O(1)

需要遍历O(n)

Null值

允许

允许

空间(capacity)

默认容量

10

由于链表的特性，LinkedList支持在任意位置插入数据，无需动态扩容

增长方式

数据copy

增长动因

旧空间无法满足新加元素后总长度

增量计算

int newCapacity = (oldCapacity * 3)/2 + 1;  即为原来的1.5倍

性能优化点

空间大小

如果预先知道数组大小，初始化时设置合适的大小，避免因数组扩容导致数据拷贝