List，根据名字我们知道是有序的元素集合。先贴一张集合的关系图。这里我们分析LinkedList与ArrayList。
Collection结构
LinkedList与ArrayList
它们都实现了List接口。但是内部实现上有些区别，我们具体看下。
LinkedList以链表的方式实现
ArrayList内部以数组方式实现
插入操作
默认顺序插入
按照默认顺序插入，两者耗费的时间都是O(1)。
// LinkedList add操作
public boolean add(E e) {
linkLast(e);
return true;
}
// 新建一个节点。然后让最后一个节点指向新加入的节点
// 如果最后一个为空，那么这是第一个新插入的节点
// 否则，节点按链表方式接在后面
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
// 增加大小，增加修改次数
size++;
modCount++;
}
// ArrayList插入
public boolean add(E e) {
// 确保数组的容量足够。这个方法感兴趣可以看一下。
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
指定index插入元素
ArrayList的最坏情况下性能为O(n)，最好情况下为O（1）
LinkedList在任何情况下都是O(1)
// LinkedList
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
// LinkedList节点的查找方法
Node<E> node(int index) {
// 不断的遍历索引的位置。
// 如果index 为小于size的一半，从头遍历
// index 大于size的一半，从尾部索引
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;
}
}
// 直接修改要插入
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
//ArrayList 。
//需要调用 System.arraycopy 扩充数组，数组中的元素都往后挪一个位置，在底层实现上应该是进行了(n-index)次的赋值操作。
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
删除操作
删除元素，与插入本质上是类似的，有兴趣可以阅读JDK内部实现方式。
ArrayList的删除操作最差情况下性能为O(n)，最好为O(1),删除最后一个元素的时候性能为O(1)
LinkedList删除任何元素的性能都为O(1)
搜索元素
ArrayList的搜索性能为O(1)
LinkedList的搜索性能差一些，最差为O(n/2)
//LinkedList的搜索
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(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;
}
}
// ArrayList搜索
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
//直接从数组的下标拿到元素即可。
E elementData(int index) {
return (E) elementData[index];
}
注意事项
LinkedList与ArrayList的源码非常容易阅读，没什么难度。这里我们说一下它们的使用事项。
- LinkedList因为要同时维护邻居节点的两个指针，内存消耗大于ArrayList。
- 在频繁的插入和删除的时候，可以考虑使用LinkedList
- 在频繁的搜索的时候，考虑使用ArrayList
- 它们都不是非线程安全的。
想要获取线程安全的List
List list = Collections.synchronizedList(new ArrayList());
...
synchronized(list) {
Iterator i = list.iterator(); // 必须在 synchronized 块中
while (i.hasNext())
foo(i.next());
}
最后
文中可能有描述不正确的地方，如果有的话欢迎指出。不过LinkedList与ArrayList是数据结构中很基础的结构，JDK源码读起来也很简单，可以试着读一下。
