JAVA ArrayList VS LinkedList 对比之一-背景调查

API 地址：http://docs.oracle.com/javase/6/docs/api/

涉及概念之间的关系如下：

图解：

List 是一个接口，它继承于Collection的接口。它代表着有序的队列。它允许重复的元素。
AbstractList 是一个抽象类，它继承于AbstractCollection。AbstractList实现List接口中除size()、get(int location)之外的函数。
AbstractSequentialList 是一个抽象类，它继承于AbstractList。它的方法较少。专门为LinkedList而设计。
ArrayList, LinkedList, Vector, Stack是List的4个实现类。

背景一：

   ArrayList 通过一个Object[]数组存储对象，要注意这个数组是transient类型的。它的add()和remove()方法是通过System.arraycopy(...)实现的，get()方法就是返回数组的一个元素。

  AbstractSequentialList 进一步地实现了add()、get()以及remove()方法。它通过调用ListIterator类中相应的方法实现这些方法。这样的目的是通过双向列表的特性，提高执行速度。它把listIterator(int index)方法声明为abstract类型，要求用户必须重新实现。

  LinkedList 继承自AbstractSequentialList，通过一个双向链表存储对象。注意这个链表的header是transient类型的。这里的header中是不包含实际数据的，仅仅作为链表的头节点。它的add()、get()、remove()方法就是对双向链表的操作。它通过双向链表地特性，重新实现了listIterator(int index)方法，定义内嵌的ListIterator类。

背景二：

ArrayList 是一个可改变大小的数组.当更多的元素加入到ArrayList中时,其大小将会动态地增长.内部的元素可以直接通过get与set方法进行访问,因为ArrayList本质上就是一个数组.
LinkedList 是一个双链表,在添加和删除元素时具有比ArrayList更好的性能.但在get与set方面弱于ArrayList.

源代码初探：

ArrayList 源代码摘要：

// size, isEmpty, get, set, iterator, 和listIterator 等操作都是常量时间.add操作也接近常量时间。ArrayList实例都有一个属性：capacity. capacity至少和size一样大，它是自动增长的。它表示ArrayList可以存放的元素数目。

private static final int DEFAULT_CAPACITY = 10; //默认capacity. 

private static final Object[] EMPTY_ELEMENTDATA = {};//capacity 就是这个 array buffer的大小
private transient Object[] elementData; //这就是arraylist最主要的元素：数组。

public void ensureCapacity(int minCapacity) ;//这个方法以及之后的一系列方法都是用来操作capacity 的，它们可以让capacity 增长。
private void grow(int minCapacity) //这个方法展示了每次扩容扩多少，基本上相当于：newCapacity = oldCapacity + (oldCapacity >> 1);
public int indexOf(Object o) //顺序查找对象。线性时间
public E get(int index) //索引获取对象。常量时间
public E set(int index, E element)//线性时间
public boolean add(E e) //相当于线性时间
public void add(int index, E element) //插入，线性时间
public E remove(int index) //删除，线性时间

JAVA ArrayList VS LinkedList 对比之一-背景调查

原文：http://blog.csdn.net/aaashen/article/details/44925181