List接口的俩个实现的区别

今天闲着没事，学习一下java的知识，突然想到了List

实际上有两种List: 一种是基本的ArrayList,其优点在于随机访问元素，另一种是更强大的LinkedList,它并不是为快速随机访问设计的，而是具有一套更通用的方法。

　　List : 次序是List最重要的特点：它保证维护元素特定的顺序。List为Collection添加了许多方法，使得能够向List中间插入与移除元素(这只推荐LinkedList使用。)一个List可以生成ListIterator,使用它可以从两个方向遍历List,也可以从List中间插入和移除元素。

　　ArrayList : 由数组实现的List。允许对元素进行快速随机访问，但是向List中间插入与移除元素的速度很慢。ListIterator只应该用来由后向前遍历ArrayList,而不是用来插入和移除元素。因为那比LinkedList开销要大很多。

　　LinkedList : 对顺序访问进行了优化，向List中间插入与删除的开销并不大。随机访问则相对较慢。(使用ArrayList代替。)还具有下列方法：addFirst(), addLast(), getFirst(), getLast(), removeFirst() 和 removeLast(), 这些方法 (没有在任何接口或基类中定义过)使得LinkedList可以当作堆栈、队列和双向队列使用。

好了，现在写段代码来测试一下俩者之间的速度

import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Test {
    
    public static void main(String[] args){
        SimpleDateFormat matter = new SimpleDateFormat("现在时间:yyyy年MM月dd日E HH时mm分ss秒");
        List<Integer> list = new ArrayList<Integer>();
        System.out.println("数组形式开始时间为： " + matter.format(System.currentTimeMillis()));
        for(int i = 0; i < 300000; i++){
            list.add(0);
        }
        System.out.println("写入完成时间为: " + matter.format(System.currentTimeMillis()));
        System.out.println("每次都清除最后一个元素..." + matter.format(System.currentTimeMillis()));
        while(list.size() > 0){
            list.remove(list.size() - 1);
        }
        System.out.println("清除完毕时间为: " + matter.format(System.currentTimeMillis()));
        
        for(int i = 0; i < 300000; i++){
            list.add(0);
        }
        System.out.println("每次都清除第一个元素..." + matter.format(System.currentTimeMillis()));
        while(list.size() > 0){
            list.remove(0);
        }
        System.out.println("清除完毕时间为: " + matter.format(System.currentTimeMillis()));
        
        for(int i = 0; i < 300000; i++){
            list.add(0);
        }
        System.out.println("每次随机清除一个元素..." + matter.format(System.currentTimeMillis()));
        while(list.size() > 0){
            list.remove((int)Math.random() * (list.size() - 1));
        }
        System.out.println("清除完毕时间为: " + matter.format(System.currentTimeMillis()));
        
        
        list = new LinkedList<Integer>();
        System.out.println("链表形式开始时间为： " + matter.format(System.currentTimeMillis()));
        for(int i = 0; i < 300000; i++){
            list.add(0);
        }
        System.out.println("写入完成时间为: " + matter.format(System.currentTimeMillis()));
        System.out.println("每次都清除最后一个元素..." + matter.format(System.currentTimeMillis()));
        while(list.size() > 0){
            list.remove(list.size() - 1);
        }
        System.out.println("清除完毕时间为: " + matter.format(System.currentTimeMillis()));
        
        for(int i = 0; i < 300000; i++){
            list.add(0);
        }
        System.out.println("每次都清除第一个元素..." + matter.format(System.currentTimeMillis()));
        while(list.size() > 0){
            list.remove(0);
        }
        System.out.println("清除完毕时间为: " + matter.format(System.currentTimeMillis()));
        
        for(int i = 0; i < 300000; i++){
            list.add(0);
        }
        System.out.println("每次随机清除一个元素..." + matter.format(System.currentTimeMillis()));
        while(list.size() > 0){
            list.remove((int)Math.random() * (list.size() - 1));
        }
        System.out.println("清除完毕时间为: " + matter.format(System.currentTimeMillis()));
        
    }
}

输出结果如下：

数组形式开始时间为：现在时间:2013年05月29日星期三 16时49分07秒
写入完成时间为: 现在时间:2013年05月29日星期三 16时49分07秒
每次都清除最后一个元素...现在时间:2013年05月29日星期三 16时49分07秒
清除完毕时间为: 现在时间:2013年05月29日星期三 16时49分07秒
每次都清除第一个元素...现在时间:2013年05月29日星期三 16时49分07秒
清除完毕时间为: 现在时间:2013年05月29日星期三 16时49分37秒
每次随机清除一个元素...现在时间:2013年05月29日星期三 16时49分37秒
清除完毕时间为: 现在时间:2013年05月29日星期三 16时49分51秒
链表形式开始时间为： 现在时间:2013年05月29日星期三 16时49分51秒
写入完成时间为: 现在时间:2013年05月29日星期三 16时49分51秒
每次都清除最后一个元素...现在时间:2013年05月29日星期三 16时49分51秒
清除完毕时间为: 现在时间:2013年05月29日星期三 16时49分51秒
每次都清除第一个元素...现在时间:2013年05月29日星期三 16时49分52秒
清除完毕时间为: 现在时间:2013年05月29日星期三 16时49分52秒
每次随机清除一个元素...现在时间:2013年05月29日星期三 16时49分52秒
清除完毕时间为: 现在时间:2013年05月29日星期三 16时49分52秒

从输出结果中可以看到，数组形式的时候每次都清除最后一个元素的时间消耗只有1秒不到，主要是清除的过程中不涉及到排序操作

数组形式清除第一个元素的操作中，每次都要将之后的N-1个剩余元素向前移动，消耗时间大约30秒

数组形式清除随机元素，每次要移动的元素有1/2(N-1)个，所以理论上消耗的时间为15秒，出来的结果是14秒，表明正常！

从结果中也可以看出在链表形式的实现在删除操作中基本不会消耗到时间。