ArrayList和LinkedList的速度问题

Question

都知道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---39LinkedList：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个连续的内存。而上面的每次循环都要开辟当前循环次数的内存。。一次性开辟的应该比较快啊。开辟内存不是件很耗时的事情吗？linkedlistarraylist

Answer 1

List<String> arrayLinkedList = new ArrayList<String>(linkedList); 为什么要这步

Answer 2

就是想最终都得到ArrayList。。验证一次开辟内存比多次开辟快啊ArrayList不是和数组一样，长度不能变的吗？加了元素就必须整体重新开辟内存吗？

Answer 3

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

Answer 4

这个第二次输出是：
arrayLinkedList:100000---34
我知道这样会快一点点的。。只是。我想知道，为什么一次开辟内存，比多次开辟要来的慢？

Answer 5

我发现要把第二次的a换成b，避免String pool的影响
这个难道和电脑配置有关？不可能吧？

Answer 6

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));

Answer 7

我用这个方法测试：
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---240arrayList:1000000---1009
arrayLinkedList:1000000---817arrayList: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);
}
    }

Answer 8

上面的上三个测试结果是有这句的结果：List<String> linkedList = new LinkedList<String>();

Answer 9

List<String> linkedList = new LinkedList<String>();删掉这句是什么意思？
是List<String> arrayLinkedList = new ArrayList<String>(linkedList);这句吧？
你电脑是有点小慢哦。哈哈。。
最后就是，原来ArrayList一次是扩展当前一般的长度的啊？这个还真不知道。那如果长度很长的话。不就很浪费内存了？
那这样的话，要linkedList来干什么啊？就增和删快了一点点。。但是很少有情况说是只存不读的吧？大多情况都是要读取的。。鸡肋。。

Answer 10

List<String> linkedList = new LinkedList<String>();删掉这句是什么意思？
是List<String> arrayLinkedList = new ArrayList<String>(linkedList);这句吧？
你电脑是有点小慢哦。哈哈。。
最后就是，原来ArrayList一次是扩展当前一般的长度的啊？这个还真不知道。那如果长度很长的话。不就很浪费内存了？
那这样的话，要linkedList来干什么啊？就增和删快了一点点。。但是很少有情况说是只存不读的吧？大多情况都是要读取的。。鸡肋。。嗯，删的那句就是你说的那句。。
关于如果长度太长的话，会不会浪费内存，这个问题不大吧。要从数量级上考虑，如果10000上都满了，加到20000问题也不是很大。实际可能也会作为一个考虑因素吧，一般大小的不用考虑吧。
也不是只存不读，ArrayList的优势是随机访问速度比较快，如果遍历什么的话，应该没有什么差别。也就是常用的操作中，基本上只有用到get(index)方法的时候，会有点差别。