ArrayList和LinkedList的速度有关问题

2013-09-08

ArrayList和LinkedList的速度问题都知道ArrayList是顺序存储，LinkedList是链式存储。理论上，在增加或删除元

ArrayList和LinkedList的速度问题
都知道ArrayList是顺序存储，LinkedList是链式存储。理论上，在增加或删除元素的时候，链式的要比顺序的快，在遍历的时候则是顺序的快。
可刚刚写了个测试代码，结果不太对啊。。

ArrayList:


long startTime = System.currentTimeMillis();
List<String> arrayList = new ArrayList<String>();
for(int i=0;i<100000;i++){
arrayList.add("a"+i);
}
long endTime = System.currentTimeMillis();
System.out.println("arrayList:"+arrayList.size()+"---"+(endTime - startTime));

打印结果是 arrayList:100000---39

LinkedList：


long startTime1 = System.currentTimeMillis();
List<String> linkedList = new LinkedList<String>();
for(int i=0;i<100000;i++){
linkedList.add("a"+i);
}
List<String> arrayLinkedList = new ArrayList<String>(linkedList);
long endTime1 = System.currentTimeMillis();
System.out.println("arrayLinkedList:"+arrayLinkedList.size()+"---"+(endTime1 - startTime1));

打印结果是 arrayLinkedList:100000---68

为什么下面的比较慢呢？下面的这个只在最后一次性开辟100000个连续的内存。而上面的每次循环都要开辟当前循环次数的内存。。一次性开辟的应该比较快啊。开辟内存不是件很耗时的事情吗？ linkedlist arraylist
[解决办法]


long startTime1 = System.currentTimeMillis();
List<String> linkedList = new LinkedList<String>();
for(int i=0;i<100000;i++){
    linkedList.add("a"+i);
}
long endTime1 = System.currentTimeMillis();
List<String> arrayLinkedList = new ArrayList<String>(linkedList);//这步后移就没问题了,这里进行了一次遍历
System.out.println("arrayLinkedList:"+arrayLinkedList.size()+"---"+(endTime1 - startTime1));

[解决办法]
我用这个方法测试：

private static void test(int count) {
long startTime = System.currentTimeMillis();
List<String> arrayList = new ArrayList<String>();
for (int i = 0; i < count; i++) { 
 
arrayList.add("a" + i);
}
long endTime = System.currentTimeMillis();
System.out.println("arrayList:" + arrayList.size() + "---"
+ (endTime - startTime));

long startTime1 = System.currentTimeMillis();
List<String> linkedList = new LinkedList<String>();
for (int i = 0; i < count; i++) {
linkedList.add("b" + i);
}
//List<String> arrayLinkedList = new ArrayList<String>(linkedList);
long endTime1 = System.currentTimeMillis();
System.out.println("arrayLinkedList:" + linkedList.size() + "---"
+ (endTime1 - startTime1));
}

我的运行结果是这样的：
arrayList:100000---305
arrayLinkedList:100000---240

arrayList:1000000---1009
arrayLinkedList:1000000---817

arrayList:10000000---14226
arrayLinkedList:10000000---20284
不过linkedlist确实好像比较慢点，下面是把List<String> linkedList = new LinkedList<String>();这句删掉后运行的结果。
arrayList:10000000---12890
arrayLinkedList:10000000---19452

我想有个问题lz搞错咯，ArrayList扩展的时候不是每次扩展1的，每次扩展当前容量的一半，越往后，扩展越大，所以越往后，ArrayList的扩展操作越来越不频繁的，肯定没有N次循环次咯。

public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
    Object oldData[] = elementData;
    int newCapacity = (oldCapacity * 3)/2 + 1;
        if (newCapacity < minCapacity)
newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
}
    }

热点排行

J2SE开发

ArrayList和LinkedList的速度有关问题