最常用的集合有List, Set 和 Map
List ------------LinkedList
------------ArrayList
------------Vector
|-------Stack
Set------------HashSet
|-------LinkedHashSet
-------------SortedSet
|------TreeSet
对于它们的数据是否可以重复出现，是否有序，有如下特点：
2.List
2.1 ArrayList
List的本质是array。 它在插入操作时会自动增加其大小，如下图的JDK 1. 6提供的
源码：
[java]
private transient Object[] elementData; //elementData是一个数组
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1; //每次自动增加适量长度
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity); //拷贝旧数组到新数组，增加长度
}
}
public void add(int index, E element) { //时间复杂度： O(n)
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
ensureCapacity(size+1); // Increments modCount!!增加数组长度
System.arraycopy(elementData, index, elementData, index + 1,
size - index); //再拷贝一次，留下index的位置给要插入的数据
elementData[index] = element;
size++;
}
[java]
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;
}
[java]
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
结构特点：ArrayList的特性跟数组很相似。元素有序可重复。
查找操作：继承数组的特点，查找很快。
修改操作：每次插入数据，必须移动其它数据，所以它在指定位置的插入操作较慢O(n)，且浪费资源。
线程安全：非线程同步。
适用情况：适用于无平凡增删的情况。
2.2 linkedList
[java]
private transient Entry header = new Entry(null, null, null);
private transient int size = 0;
/**
* Constructs an empty list.
*/
public LinkedList() {
header.next = header.previous = header;
}
[java]
private E remove(Entry 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;
}
[java]
/**
* Returns the indexed entry.
*/
private Entry entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
Entry 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;
}
ret