ArrayList是用数组实现的，LinkedList是用双向链表实现的。
ArrayList:
内含两个成员变量：elementDate和size，elementData是对象数组类型的变量(Object[])，声明为transient，即序列化的时候不包括elementData这个变量。
声明一个ArrayList对象时，若无参数，默认的数组大小是10。
public ArrayList() {
this(10);
}
trimToSize()方法，把数组的大小缩小到数组成员的个数，减少存储空间的使用。
public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
}
若新加成员后数组不够用，则使用ensureCapacity(int minCapacity)来扩大数组大小，新数组大小为为原来的1.5倍加1
int newCapacity = (oldCapacity * 3)/2 + 1;
list可以存储null元素。
get操作：
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
set操作：
public E set(int index, E element) {
RangeCheck(index);
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
add操作：
public boolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
remove操作：
public E remove(int index) {
RangeCheck(index);
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}
LinkedList:
内含2个成员变量header和size，header表示头节点。
LinkedList用静态内部类Entry来表示一个节点，除了存储元素的数据外，还存储前驱节点和后驱节点。
get操作：
public E get(int index) {
return entry(index).element;
}
set操作：
public E set(int index, E element) {
Entry<E> e = entry(index);
E oldVal = e.element;
e.element = element;
return oldVal;
}
entry方法：
private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
Entry<E> e = header;
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}
entry方法需要移动指针。故set操作需要较多的时间。
remove操作：
private E remove(Entry<E> e) {
if (e == header)
throw new NoSuchElementException();
E result = e.element;
e.previous.next = e.next;
e.next.previous = e.previous;
e.next = e.previous = null;
e.element = null;
size--;
modCount++;
return result;
}
只需要移动前驱节点和后继节点的指向即可。
总结：
1：对set、get方法，因为ArrayList采用的是数组实现，故在常数时间里即可实现，而对LinkedList来说，它要移动指针来定位相应的元素，故需花多点的时间。
2：对insert、remove操作，ArrayList常需要一定数组元素，而LinkedList只要改变指针指向即可。
责任编辑：小草
您现在的位置： 