ArrayList和LinkedList对比

次序是List最重要的特点;它保证维护元素特定的顺序
简单介绍:
ArrayList底层的实现是数组,随机访问所以用下标访问的速度比较快,但是插入和删除元素,会有移动元素的开销,所以速度比LinkedList差。
LikedList底层是双向链表实现的,对顺序访问进行了优化,插入和删除元素时间复杂度较LinkedList好,但是随机访问需要遍历元素,所以效率比ArrayList差。

例子如下:

import org.junit.Test;  
import java.util.ArrayList;  
import java.util.LinkedList;  
import java.util.List;  
  
public class ListAddTest {  
  
    List<String> arrList = new ArrayList<String>();  
    List<String> lnkList = new LinkedList<String>();  
  
    void add(List<String> list) {  
  
        long startTime = System.currentTimeMillis();  
        System.out.println("开始的时间:" + startTime);  
        for (int i = 0; i < 100000; i++) {  
            list.add(0, String.valueOf(i));  
        }  
        long endTime = System.currentTimeMillis();  
        System.out.println("结束的时间:" + endTime);  
        System.out.println("总耗时:" + (endTime - startTime));  
  
    }  
  
    @Test  
    public void addTimeTest() {  
  
        add(arrList);  
        // 开始的时间:1487783199226  
        // 结束的时间:1487783199741  
        // 总耗时:515  
  
        add(lnkList);  
        // 开始的时间:1487783199741  
        // 结束的时间:1487783199756  
        // 总耗时:15  
  
    }  
  
}  

分析

首先,阅读JDK的文档,我们从中可以知道,ArrayList实际上是一个可变长的数组,LinkedList则是由相互引用的节点组成的双向链表

紧接着我们就要知道,在增加数据时LinkedList和ArrayList分别在底层发生了什么?于是略读JDK源码我们就可以得出:
● 既然LinkedList是一个由相互引用的节点组成的双向链表,那么当把数据插入至该链表某个位置时,该数据就会被组装成一个新的节点,随后只需改变链表中对应的两个节点之间的引用关系,使它们指向新节点,即可完成插入(如下图);同样的道理,删除数据时,只需删除对应节点的引用即可

clipboard.png

● 而ArrayList是一个可变长数组,插入数据时,则需要先将原始数组中的数据复制到一个新的数组,随后再将数据赋值到新数组的指定位置(如下图);删除数据时,也是将原始数组中要保留的数据复制到一个新的数组

clipboard.png

结论

因此,在添加或删除数据的时候,ArrayList经常需要复制数据到新的数组,而LinkedList只需改变节点之间的引用关系,这就是LinkedList在添加和删除数据的时候通常比ArrayList要快的原因。

结论补充

但是在一定程度上此结论不成立,参考https://blog.csdn.net/hzj1998...。

因为链表插入的时候首先要找到插入的位置在哪,查找时间复杂度为On,数组则是O1,查找越靠后的索引,链表的速度越慢(但是后面优化了链表查询速度,哪边近从哪边开始遍历),查找中间的时候最慢,On/2的时间复杂度。

若是每次插入都是从中间插入,数组arrayList速度会比链表快,同理remove方法也是一样,先要找到位置。

评论

暂无评论