java提高篇（二一）-----arraylist
java提高篇（二二）-----linkedlist
java提高篇（二九）-----vector
java提高篇（三一）-----stack
一、list接口概述 list接口，成为有序的collection也就是序列。该接口可以对列表中的每一个元素的插入位置进行精确的控制，同时用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。 下图是list接口的框架图：
通过上面的框架图，可以对list的结构了然于心，其各个类、接口如下：
collection：collection 层次结构 中的根接口。它表示一组对象，这些对象也称为 collection 的元素。对于collection而言，它不提供任何直接的实现，所有的实现全部由它的子类负责。
abstractcollection：提供 collection 接口的骨干实现，以最大限度地减少了实现此接口所需的工作。对于我们而言要实现一个不可修改的 collection，只需扩展此类，并提供 iterator 和 size 方法的实现。但要实现可修改的 collection，就必须另外重写此类的 add 方法（否则，会抛出 unsupportedoperationexception），iterator 方法返回的迭代器还必须另外实现其 remove 方法。
terator：迭代器。
listiterator：系列表迭代器，允许程序员按任一方向遍历列表、迭代期间修改列表，并获得迭代器在列表中的当前位置。
list：继承于collection的接口。它代表着有序的队列。
abstractlist：list 接口的骨干实现，以最大限度地减少实现“随机访问”数据存储（如数组）支持的该接口所需的工作。
queue：队列。提供队列基本的插入、获取、检查操作。
deque：一个线性 collection，支持在两端插入和移除元素。大多数 deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。
abstractsequentiallist：提供了 list 接口的骨干实现，从而最大限度地减少了实现受“连续访问”数据存储（如链接列表）支持的此接口所需的工作。从某种意义上说，此类与在列表的列表迭代器上实现“随机访问”方法。
linkedlist：list 接口的链接列表实现。它实现所有可选的列表操作。
arraylist：list 接口的大小可变数组的实现。它实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 list 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。
vector：实现可增长的对象数组。与数组一样，它包含可以使用整数索引进行访问的组件。
stack：后进先出（lifo）的对象堆栈。它通过五个操作对类 vector 进行了扩展 ，允许将向量视为堆栈。
enumeration：枚举，实现了该接口的对象，它生成一系列元素，一次生成一个。连续调用 nextelement 方法将返回一系列的连续元素。
二、使用场景 学习知识的根本目的就是使用它。每个知识点都有它的使用范围。集合也是如此，在java中集合的家族非常庞大，每个成员都有最适合的使用场景。在刚刚接触list时，lz就说过如果涉及到“栈”、“队列”、“链表”等操作，请优先考虑用list。至于是那个list则分如下：
1、对于需要快速插入、删除元素，则需使用linkedlist。
2、对于需要快速访问元素，则需使用arraylist。
3、对于“单线程环境”或者“多线程环境，但是list仅被一个线程操作”，需要考虑使用非同步的类，如果是“多线程环境，切list可能同时被多个线程操作”，考虑使用同步的类（如vector）。
2.1arraylist、linkedlist性能分析 在list中我们使用最普遍的就是linkedlist和arraylist，同时我们也了解了他们两者之间的使用场景和区别。
public class listtest { private static final int count = 100000; private static arraylist arraylist = new arraylist<>(); private static linkedlist linkedlist = new linkedlist<>(); private static vector vector = new vector<>(); public static void inserttolist(list list){ long starttime = system.currenttimemillis(); for(int i = 0 ; i < count ; i++){ list.add(0,i); } long endtime = system.currenttimemillis(); system.out.println("插入 " + count + "元素" + getname(list) + "花费 " + (endtime - starttime) + " 毫秒"); } public static void deletefromlist(list list){ long starttime = system.currenttimemillis(); for(int i = 0 ; i < count ; i++){ list.remove(0); } long endtime = system.currenttimemillis(); system.out.println("删除" + count + "元素" + getname(list) + "花费 " + (endtime - starttime) + " 毫秒"); } public static void readlist(list list){ long starttime = system.currenttimemillis(); for(int i = 0 ; i < count ; i++){ list.get(i); } long endtime = system.currenttimemillis(); system.out.println("读取" + count + "元素" + getname(list) + "花费 " + (endtime - starttime) + " 毫秒"); } private static string getname(list list) { string name = ""; if(list instanceof arraylist){ name = "arraylist"; } else if(list instanceof linkedlist){ name = "linkedlist"; } else if(list instanceof vector){ name = "vector"; } return name; } public static void main(string[] args) { inserttolist(arraylist); inserttolist(linkedlist); inserttolist(vector); system.out.println("--------------------------------------"); readlist(arraylist); readlist(linkedlist); readlist(vector); system.out.println("--------------------------------------"); deletefromlist(arraylist); deletefromlist(linkedlist); deletefromlist(vector); } }
运行结果:
插入 100000元素arraylist花费 3900 毫秒 插入 100000元素linkedlist花费 15 毫秒 插入 100000元素vector花费 3933 毫秒 -------------------------------------- 读取100000元素arraylist花费 0 毫秒 读取100000元素linkedlist花费 8877 毫秒 读取100000元素vector花费 16 毫秒 -------------------------------------- 删除100000元素arraylist花费 4618 毫秒 删除100000元素linkedlist花费 16 毫秒 删除100000元素vector花费 4759 毫秒
从上面的运行结果我们可以清晰的看出arraylist、linkedlist、vector增加、删除、遍历的效率问题。下面我就插入方法add(int index, e element),delete、get方法各位如有兴趣可以研究研究。
首先我们先看三者之间的源码：
arraylist
public void add(int index, e element) { rangecheckforadd(index); //检查是否index是否合法 ensurecapacityinternal(size + 1); //扩容操作 system.arraycopy(elementdata, index, elementdata, index + 1, size - index); //数组拷贝 elementdata[index] = element; //插入 size++; }
rangecheckforadd、ensurecapacityinternal两个方法没有什么影响，真正产生影响的是system.arraycopy方法，该方法是个jni函数，是在jvm中实现的。声明如下：
public static native void arraycopy(object src, int srcpos, object dest, int destpos, int length);
目前lz无法看到源码，具体的实现不是很清楚，不过system.arraycopy源码分析对其进行了比较清晰的分析。但事实上我们只需要了解该方法会移动index后面的所有元素即可，这就意味着arraylist的add(int index, e element)方法会引起index位置之后所有元素的改变，这真是牵一处而动全身。
linkedlist
public void add(int index, e element) { checkpositionindex(index); if (index == size) //插入位置在末尾 linklast(element); else linkbefore(element, node(index)); }
该方法比较简单，插入位置在末尾则调用linklast方法，否则调用linkbefore方法，其实linklast、linkbefore都是非常简单的实现，就是在index位置插入元素，至于index具体为知则有node方法来解决，同时node对index位置检索还有一个加速作用，如下：
node<e> node(int index) { if (index < (size >> 1)) { //如果index 小于 size/2 则从头开始查找 node<e> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { //如果index 大于 size/2 则从尾部开始查找 node<e> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
所以linkedlist的插入动作比arraylist动作快就在于两个方面。1：linkedlist不需要执行元素拷贝动作，没有牵一发而动全身的大动作。2:查找插入位置有加速动作即：若index < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查找。
vector
vector的实现机制和arraylist一样，同样是使用动态数组来实现的，所以他们两者之间的效率差不多，add的源码也一样，如下：
public void add(int index, e element) { insertelementat(element, index); } public synchronized void insertelementat(e obj, int index) { modcount++; if (index > elementcount) { throw new arrayindexoutofboundsexception(index + " > " + elementcount); } ensurecapacityhelper(elementcount + 1); system.arraycopy(elementdata, index, elementdata, index + 1, elementcount - index); elementdata[index] = obj; elementcount++; }
上面是针对arraylist、linkedlist、vector三者之间的add（int index,e element)方法的解释，解释了linkedlist的插入动作要比arraylist、vector的插入动作效率为什么要高出这么多！至于delete、get两个方法lz就不多解释了。
同时lz在写上面那个例子时发现了一个非常有趣的现象，就是linkedlist在某些时候执行add方法时比arraylist方法会更慢！至于在什么情况？为什么会慢lz下篇博客解释，当然不知道这个情况各位是否也遇到过？？
2.2、vector和arraylist的区别
四、更多 java提高篇（二一）-----arraylist
java提高篇（二二）-----linkedlist
java提高篇（二九）-----vector
java提高篇（三一）-----stack
以上就是java提高篇（三二）-----list总结的内容。