Java源码学习--ArrayList、LinkedList、Vector比较
在进行三个的总结之前，还有一个需要了解一下的就是Stack这个类。
一、Stack
这个类继承了Vector，而且该类只是提供了栈操作的方法，没有其他任何的东西：
public class Stack<E> extends Vector<E> {
public Stack() {
}
public E push(E item) {
addElement(item);
return item;
}
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
public boolean empty() {
return size() == 0;
}
public synchronized int search(Object o) {
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
private static final long serialVersionUID = 1224463164541339165L;
}
二、ArrayList、LinkedList、Vector比较
1. ArrayList
1.1 add方法
ArrayList的add系列的方法的实现逻辑为：
- 检查index是否合法(不是每种add方法都会，当add时指定index时才会有这一步)
- 检查size+1时是否到达了容量上限，即是否需要扩容
- 将index后面的元素通过System.arraycopy方法向后移动一个位置
- 执行元素的添加，在ArrayList中这一步只是一个数组某一位置的赋值操作
由于ArrayList中维护的是一个数组，而数组根据下标的操作的时间复杂度都是O(1)所以ArrayList的add方法几乎是没有耗时的，当调用在指定位置添加的方法时由于需要把index后面的元素向后移动一格而调用了System.arraycopy方法，会产生一些耗时,当遇到需要扩容时由于执行了Arrays.copyof方法，此时需要一些耗时
1.2 addAll方法
ArrayList的addAll系列方法的实现逻辑为：
- 检查index是否合法(不是每种addAll方法都会，当addAll时指定index时才会有这一步)
- 通过toArray方法将方法参数的Collection对象转化为数组类型
- 检查size+newLength时是否到达了容量上限，即是否需要扩容
- 将index后面的元素通过System.arraycopy方法向后移动newLength个位置
- 执行元素的添加，在ArrayList中也是通过System.arraycopy方法实现的
在ArrayList的addAll方法中，和add相比，多执行了一次System.arraycopy方法，多出的耗时就是在这里。
1.3 remove方法
ArrayList的remove(int index)方法实现逻辑为：
- 检查index是否小于当前的size
- 将index后面的元素通过System.arraycopy方法向前移动一个位置
- 执行元素的删除，在ArrayList中这一步只是将数组中下标为size的元素赋值为null
可见ArrayList的删除执行位置的方法，唯一耗时的就是向前移动元素。
ArrayList的remove(Object o)方法的实现逻辑为：
- 通过for循环找到(通过equals方法进行判断)需要删除的元素的位置position
- 调用fastRemove(position)执行删除，该方法的实现几乎和remove(index)是一样的
直接删除对象的方法更加耗时，原因就在于多了一个for来寻找被删除对象的位置。
ArrayList中还有一个removeAll的方法，其作用是将参数集合中所有的元素都从ArrayList中删除；该方法效率很低下，就是对于参数中的每一个元素ArrayList都要调用contains方法来判断是否含有该元素，关键是contains方法的实现就是一个for循环遍历ArrayList中是所有元素，所以removeAll的复杂度为O(n^2)
1.4 get和set方法
ArrayList的get和set就是一个数组根据下标来查找元素的方法，所以没任何毛病；不过发扬传统，在执行数组的写和读的操作之前还是要检查一下index的合法性问题。
2. LinkedList
2.1 add方法
LinkedList的add方法就是一个双向链表的插入方法，其逻辑为：
- 首先找到index位置对应的节点(在指定插入位置时，通过for循环中计数得到)
- 执行节点的插入
LinkedList方法的插入和ArrayList相比会慢一些，首先是节点的插入肯定比不上数组根据下标进行读写，其次是虽然指定添加位置时ArrayList需要将index后面的元素拷贝一下，但是LinkedList中却需要找到index位置的节点，所以前者耗时在后续数据的移动，而后者耗时在index位置节点的获取，这么一比还是ArrayList占据了上风；但是LinkedList有一个优点就是没有需要扩容的情况。
2.2 addAll方法
LinkedList的addAll方法的逻辑为：
- 首先找到index位置对应的节点(在指定插入位置时，通过for循环中计数得到)
- 对参数的Collection对象中的元素通过for循环挨个进行节点的加入
额，这个方法好像没啥好说的。
2.3 remove方法
LinkedList的remove(Object o)方法的实现逻辑是：
- 一个for循环找到o对应的对象
- 执行节点的删除方法
可见该方法和ArrayList相比在找该对象时使用的都是for循环，在这一步上是势均力敌的(ArrayList稍微领先)，包括数据的删除都是ArrayList要由于LinkedList；但是ArrayList在删除数据之后还要把后面的数据整体向前移动一个位置，而LinkedList则没有这一步。
LinkedList的remove(int index)方法的实现逻辑是：
- 首先通过for循环找到index对应的节点
- 执行节点的删除方法
LinkedList的该方法和ArrayList相比就没有多大的优势了，因为ArrayList通过index删除时根本不需要通过for循环，直接一个数组的根据下标操作数据秒杀LinkedList，但是ArrayList还是有一个后续数据的前移的工作要做，因此这个方法ArrayList以微弱优势取胜。
2.4 get和set方法
LinkedList的get和set方法就都很惨了，因为只要涉及到指定了位置index，那LinkedList就只能通过for遍历来找到，所以这里相较于ArrayList直接通过数组的下标操作数据，LinkedList通过for循环找到数据变完全被秒杀了。
3. Vector
由于Vector和ArrayList几乎是一样的实现，这里就不在进行对比了。
三、总结
看完了List系列的源代码，虽然这些源代码确实很简单易懂，但是还是有很多能够学习的：
- 良好的习惯：涉及到index的操作，可以看到所有的方法第一件做的是就是检查index的合法性，这等细节却能反应很多东西；在各种面试的书集中，都会说到考虑要完善，考虑到特殊情况等，这都是在考验我们的严谨性
- 主动释放资源：在涉及到删除的操作时，特别是批量的删除，源代码中都会有一个将被删除的位置或者区间的元素赋值为null的操作，并且代码中通常会有注释：// clear to let GC do its work；这也是一个好的习惯，“不要以为我的size属性会卡主操作者他不会访问到那些数据，我干嘛要去删除”
