一、介绍首先回顾一下List的框架图从图中的继承关系可以知道ArrayList、LinkedList、Vector、Stack是四个实现类列表。AbstractList是一个抽象类，继承自AbstractCollection。AbstractList实现了List接口中除size()和get(intlocation)之外的功能。AbstractSequentialList是一个抽象类，继承于AbstractList。AbstractSequentialList实现了“链表中所有根据index索引值操作链表的函数”。ArrayList是一个数组队列，相当于一个动态数组。采用数组实现，随机存取效率高，随机插入随机删除效率低。LinkedList是一个双向链表。它也可以作为堆栈、队列或双端队列来操作。LinkedList随机访问是低效的，但是随机插入和随机删除也是低效的。Vector是向量队列，和ArrayList一样，也是动态数组，由数组实现。但是ArrayList不是线程安全的，而Vector是线程安全的。Stack是一个栈，继承自Vector。其特点是：先进后出（FILO，FirstInLastOut）。2.性能测试在比较ArrayList、LinkedList、Vector、Stack之前，我们先对它们进行性能测试，结合源码和测试结果对ArrayList、LinkedList、Vector、Stack进行详细分析。得到的结果如下根据结果可以明显看出ArrayList、LinkedList、Vector、Stack的性能差别很大。读取：ArrayList>Vector>Stack>LinkedList插入：LinkedList>Vector>ArrayList>Stack删除：LinkedList>Vector>ArrayList>Stack3、分析插入LinkedList从中我们可以看出：通过add(intindex,Eelement)时向LinkedList中插入元素。首先找到要插入的节点在双向链表中的位置索引；找到后，插入一个新节点。双向链表在查找index位置的结点时，有一个加速动作：如果index<1/2的双向链表长度，则从前向后查找；否则，从后往前搜索。ArrayList有一个非常耗时的操作System.arraycopy(elementData,index,elementData,index+1,size-index);这个方法被标记为native，调用系统的C/C++代码，在JDK中是看不到的，但是在openJDK中可以看到它的源码。该函数实际上调用了C语言的memmove()函数，因此可以保证同一数组中元素的正确复制和移动，比一般的复制方法效率高很多，非常适合批量处理数组。Java强烈推荐在复制大量数组元素时使用这种方式，以达到更高的效率。Vector可以看到Vector和ArrayList是一样的，都是调用System.arraycopy。因为Stack和继承还有Vector，就不仔细分析了。四、查找LinkedList的分析从中我们可以看出：当通过get(intindex)获取LinkedList的索引元素时。先在双向链表中找到索引位置的元素；找到后返回。双向链表在查找index位置的结点时，有一个加速动作：如果index<1/2的双向链表长度，则从前向后查找；否则，从后往前搜索。ArrayList我们可以看到ArrayList直接返回数组中索引位置的元素，而不像LinkedList那样查找。通过源码发现Vector和Stack的运行方式与ArrayList相同，这里不再详细分析。5、删除分析LinkedList因为某个节点被删除，调整对应节点的前后指针信息，如下：e.previous.next=e.next;//预删除节点的previous指针指向预删除节点下一个节点。e.next.previous=e.previous;//预删除节点的下一个节点的previous指针指向预删除节点的前一个节点。清空预删除节点：e.next=e.previous=null；e.element=null；交给gc完成资源回收，删除操作结束。与ArrayList相比，LinkedList的删除动作不需要“移动”大量数据，因此效率更高。嗯，ArrayList又调用了System.arraycopy。6.结论操作ArrayListLinkedListVectorStack读O(1)O(n)O(1)O(1)插入O(n)O(1)O(n)O(n)删除O(n)O(1)O(n)O(n)ArrayList（动态数组的实现），查询快（随机访问或顺序访问），增删慢。整体清盘快，线程不同步（非线程安全）。数组长度可变50%扩展LinkedList（实现链表），查询慢，增删快。Vector（实现动态数组）速度慢，被ArrayList取代。长度可以任意延长。线程安全（同步的类和函数都是同步的）Stack（实现栈）继承自Vector，先进后出。所以，快速访问ArrayList，快速增删LinkedList，单线程可以用，多线程只能用同步类Vector
