java 容器和泛型（2）arraylist 、linkedlist和vector比较-mile米乐体育

一、list回顾

序列（list），有序的collection，正如它的名字一样，是一个有序的元素列表。确切的讲，列表通常允许满足 e1.equals(e2) 的元素对 e1 和 e2，并且如果列表本身允许 null 元素的话，通常它们允许多个 null 元素。实现list的有：arraylist、linkedlist、vector、stack等。值得一提的是，vector在jdk1.1的时候就有了，而list在jdk1.2的时候出现，待会我们会聊到arraylist和vector的区别。

二、arraylist vs. vector

arraylist是一个可调整大小的数组实现的序列。随着元素增加，其大小会动态的增加。此类在iterator或listiterator迭代中，调用容器自身的remove和add方法进行修改，会抛出concurrentmodificationexception并发修改异常。

注意，此实现不是同步的。如果多个线程同时访问一个 arraylist 实例，而其中至少一个线程从结构上修改了列表，那么它必须 保持外部同步。（结构上的修改是指任何添加或删除一个或多个元素的操作，或者显式调整底层数组的大小；仅仅设置元素的值不是结构上的修改。）这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 collections.synchronizedlist 方法将该列表“包装”起来。这最好在创建时完成，以防止意外对列表进行不同步的访问：

list list = collections.synchronizedlist(new arraylist(…)); 

下面演示下相关arraylist例子。

arraylist基本方法代码：

@suppresswarnings({ "rawtypes", "unchecked" })     public static void listmethods()     {          list a1 = new arraylist();          a1.add("list01");         a1.add("list03");         a1.add("list04");         system.out.print("原来集合：/n/t" a1 "/n");          a1.add(1,"list02");         system.out.print("指定角标1插入：/n/t" a1 "/n");          a1.remove(2);         system.out.print("指定角标2删除：/n/t" a1 "/n");          system.out.print("指定角标2查询：/n/t" a1.get(2) "/n");          iterator i1 = a1.iterator();         system.out.println("用迭代器查询全部元素：");         while (i1.hasnext())         {             system.out.print(i1.next() ",");         }     }

可以从控制台可以看出：

原来集合：     [list01, list03, list04] 指定角标1插入：     [list01, list02, list03, list04] 指定角标2删除：     [list01, list02, list04] 指定角标2查询：     list04 用迭代器查询全部元素： list01,list02,list04

在上面我们可以根据角标来增加(add)、删除(remove)、获取(get)列表里面元素。arraylist提供了iterator迭代器来遍历序列。值得注意的是，迭代器的就相当于一个指针指向角标，next()方法就相当于指针往后移一位。所以切记，用迭代器中一次循环用一次next()。

下面演示下在concurrentmodificationexception的出现，及处理方案。泥瓦匠用iterator演示这个异常的出现：

@suppresswarnings({ “unchecked”, “rawtypes” })     public static void iteratortest()     {         list a1 = new arraylist();          a1.add(“list01″);         a1.add(“list02″);         a1.add(“list04″);         a1.add(“list05″);          iterator i1 = a1.iterator();         while (i1.hasnext())         {             object obj = i1.next();             if (obj.equals(“list02″))                 a1.add(“list03″);         }          system.out.print(“集合：/n/t” a1 ”/n”);     }

运行，我们可以在控制台看到：

怎么解决的，先看清楚这个问题。问题描述很清楚，在创建迭代器之后，除非通过迭代器自身的 remove 或 add 方法从结构上对列表进行修改，否则在任何时间以任何方式对列表进行修改，迭代器都会抛出concurrentmodificationexception。

因此我们应该这样修改代码，用listiterator迭代器提供方法：

@suppresswarnings({ "unchecked", "rawtypes" })     public static void listiterator()     {          list a1 = new arraylist();          a1.add("list01");         a1.add("list");         a1.add("list03");         a1.add("list04");          listiterator l1 = a1.listiterator();         while (l1.hasnext())         {             object obj = l1.next();             if (obj.equals("list"))             {                 l1.remove();                 l1.add("list02");             }         }         system.out.print("集合：/n/t" a1 "/n");     }

运行下，我们可以看到：

集合：     [list01, list02, list03, list04]

这样，我们成功解决了这个并发修改异常。把其中‘list’元素删除，新增了一个‘list02’的元素。

vector非常类似arraylist。早在jdk1.1的时候就出现了，以前没有所谓的list接口，现在此类被改进为实现list接口。但与新的collection不同的是，vector是同步的。泥瓦匠想说的是vector，在像查询的性能上会比arraylist开销大。下面演示下vector的基本例子：

@suppresswarnings({ "unchecked", "rawtypes" })     public static void vectormethods()     {         vector v1 = new vector();          v1.add("vector001");         v1.add("vector002");         v1.add("vector003");         v1.add("vector004");         v1.add("vector005");          enumeration e1 =v1.elements();         while (e1.hasmoreelements())         {             object object = e1.nextelement();             system.out.println(object);         }     }

从方法上看几乎没差别，同样注意的是：此接口的功能与 iterator 接口的功能是重复的。此外，iterator 接口添加了一个可选的移除操作，并使用较短的方法名。新的实现应该优先考虑使用 iterator 接口而不是 enumeration 接口。

三、linkedlist及其与arraylist性能比

linkedlist与arraylist一样实现list接口，linkedlist是list接口链表的实现。基于链表实现的方式使得linkedlist在插入和删除时更优于arraylist，而随机访问则比arraylist逊色些。linkedlist实现所有可选的列表操作，并允许所有的元素包括null。除了实现 list 接口外，linkedlist 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。

linkedlist和arraylist的方法时间复杂度总结如下图所示。

表中，添加add()指添加元素的方法，remove()是指除去（int index）角标。arraylist具有o（n）的任意指数时间复杂度的添加/删除，但o（1）的操作列表的末尾。链表的o（n）的任意指数时间复杂度的添加/删除，但o（1）操作端/列表的开始。

泥瓦匠用代码验证下这个结论：

public static void testperbtwnarlandlkl()     {         arraylist arraylist   = new arraylist();         linkedlist linkedlist = new linkedlist();          // arraylist add         long starttime  = system.nanotime();         long endtime;         long duration;          for (int i = 0; i < 100000; i  ) {             arraylist.add(i);         }         endtime = system.nanotime();         duration = endtime - starttime;         system.out.println("arraylist add:  "   duration);          // linkedlist add         starttime = system.nanotime();          for (int i = 0; i < 100000; i  ) {             linkedlist.add(i);         }         endtime = system.nanotime();         duration = endtime - starttime;         system.out.println("linkedlist add: "   duration);          // arraylist get         starttime = system.nanotime();          for (int i = 0; i < 10000; i  ) {             arraylist.get(i);         }         endtime = system.nanotime();         duration = endtime - starttime;         system.out.println("arraylist get:  "   duration);          // linkedlist get         starttime = system.nanotime();          for (int i = 0; i < 10000; i  ) {             linkedlist.get(i);         }         endtime = system.nanotime();         duration = endtime - starttime;         system.out.println("linkedlist get: "   duration);          // arraylist remove         starttime = system.nanotime();          for (int i = 9999; i >=0; i--) {             arraylist.remove(i);         }         endtime = system.nanotime();         duration = endtime - starttime;         system.out.println("arraylist remove:  "   duration);          // linkedlist remove         starttime = system.nanotime();          for (int i = 9999; i >=0; i--) {             linkedlist.remove(i);         }         endtime = system.nanotime();         duration = endtime - starttime;         system.out.println("linkedlist remove: "   duration);     }

控制台输出如下：

arraylist add:  16904776 linkedlist add: 12015418 arraylist get:  1304593 linkedlist get: 108950741 arraylist remove:  787388127 linkedlist remove: 128145950

对比下的话，其性能差距很明显。linkedlist在添加和删除中性能快，但在获取中性能差。从复杂度和测试结果，我们应该懂得平时在添加或者删除操作频繁的地方，选择linkedlist时考虑：

1、没有大量的元素的随机访问

2、添加/删除操作

自然我下面用linedlist实现一个数据结构–栈。泥瓦匠留给大家linkedlist的一些方法自己消化下。

package com.sedion.bysocket.collection; import java.util.linkedlist;  /**  * 用linkedlist实现栈  * 队列和栈区别：队列先进先出，栈先进后出。  */ public class stack {     private linkedlist storage = new linkedlist();      /** 入栈 */     public void push(t v)     {         storage.addfirst(v);     }      /** 出栈，但不删除 */     public t peek()     {         return storage.getfirst();     }      /** 出栈，删除 */     public t pop()     {         return storage.removefirst();     }      /** 栈是否为空 */     public boolean empty()     {         return storage.isempty();     }      /** 输出栈元素 */     public string tostring()     {         return storage.tostring();     }      public static void main(string[] args)     {         stack stack=new stack();         stack.push("a");         stack.push("b");         stack.push("c");         system.out.println(stack.tostring());         object obj=stack.peek();         system.out.println(obj "--" stack.tostring());         obj=stack.pop();         system.out.println(obj "--" stack.tostring());         system.out.println(stack.empty());     } }

四、总结

泥瓦匠总结如下：

vector和arraylist

1、vector是线程同步的，所以它也是线程安全的，而arraylist是线程异步的，是不安全的。

2、记住并发修改异常 java.util.concurrentmodificationexception ，优先考虑arraylist，除非你在使用多线程所需。

aarraylist和linkedlist

1、对于随机访问get和set，arraylist觉得优于linkedlist，linkedlist要移动指针。

2、于新增和删除操作add和remove，linedlist比较占优势，arraylist要移动数据。

3、单条数据插入或删除，arraylist的速度反而优于linkedlist.若是批量随机的插入删除数据，linkedlist的速度大大优于arraylist. 因为arraylist每插入一条数据，要移动插入点及之后的所有数据。