29
2020
11

Java中ArrayList和LinkedList区别?

ArrayList和Vector使用了数组的实现,可以认为 ArrayList 或者 Vector 封装了对内部数组的操作,比如向数组中添加、删除、插入新的元素或者数据的扩展和重定向。

 

LinkedList 使用了循环双向链表数据结构。与基于数组的 ArrayList 相比,这是两种截然不同的实现技术,这也决定了它们将适用于完全不同的工作场景。

 

LinkedList 链表由一系列表项连接而成。一个表项总是包含 3 个部分:元素内容,前驱表和后驱表,如图所示:

 

1557476054@a3fbf8a49f2e9cf5a54478ccc9a9d840.png

 

在下图展示了一个包含 3 个元素的 LinkedList 的各个表项间的连接关系。在 JDK 的实现中,无论 LikedList 是否为空,链表内部都有一个 header 表项,它既表示链表的开始,也表示链表的结尾。表项 header 的后驱表项便是链表中第一个元素,表项 header 的前驱表项便是链表中最后一个元素。

 

1557476130@3b3411a65547803e24883fb86e0187c3.png

 

ArrayList 是实现了基于动态数组的数据结构,LinkedList 基于链表的数据结构。如果集合数据是对于集合随机访问 get 和 set,ArrayList 绝对优于 LinkedList,因为 LinkedList 要移动指针。如果集合数据是对于集合新增和删除操作 add 和 remove,LinkedList 比较占优势,因为ArrayList要移动数据。

 

ArrayList 和 LinkedList 是两个集合类,用于存储一系列的对象引用(references)。例如我们可以用 ArrayList 来存储一系列的 String 或者 Integer。那么 ArrayList 和 LinkedList 在性能上有什么差别呢?什么时候应该用 ArrayList 什么时候又该用 LinkedList 呢?

 

● 时间复杂度

 

首先一点关键的是,ArrayList 的内部实现是基于基础的对象数组的,因此,它使用 get 方法访问列表中的任意一个元素时(random access),它的速度要比 LinkedList 快。LinkedList 中的 get 方法是按照顺序从列表的一端开始检查,直到另外一端。对 LinkedList 而言,访问列表中的某个指定元素没有更快的方法了。

 

假设我们有一个很大的列表,它里面的元素已经排好序了,这个列表可能是 ArrayList 类型的也可能是 LinkedList 类型的,现在我们对这个列表来进行二分查找(binary search),比较列表是 ArrayList 和 LinkedList 时的查询速度,看下面的程序:

 

public class TestList {

    public static final int N = 50000;    //50000 个数

    public static List values; //要查找的集合

    //放入 50000 个数给 value;

    static {

        Integer vals[] = new Integer[N];

        Random r = new Random();

        for (int i = 0, currval = 0; i < N; i++) {

            vals = new Integer(currval);

            currval += r.nextInt(100) + 1;

        }

        values = Arrays.asList(vals);

    }

    //通过二分查找法查找

    static long timeList(List lst) {

        long start = System.currentTimeMillis();

        for (int i = 0; i < N; i++) {

            int index = Collections.binarySearch(lst, values.get(i));

            if (index != i)

                System.out.println("***错误***");

        }

        return System.currentTimeMillis() - start;

    }

    public static void main(String args[]) {

        System.out.println("ArrayList 消耗时间:" + timeList(new ArrayList(values)));

        System.out.println("LinkedList 消耗时间:" + timeList(new LinkedList(values)));

    }

}

 

LinkedList 做随机访问所消耗的时间与这个 list 的大小是成比例的。而相应的,在 ArrayList 中进行随机访问所消耗的时间是固定的。

 

这是否表明 ArrayList 总是比 LinkedList 性能要好呢?这并不一定,在某些情况下 LinkedList 的表现要优于ArrayList,有些算法在 LinkedList 中实现时效率更高。比方说,利用 Collections.reverse 方法对列表进行反转时,其性能就要好些。看这样一个例子,加入我们有一个列表,要对其进行大量的插入和删除操作,在这种情况下LinkedList 就是一个较好的选择。请看如下一个极端的例子,我们重复的在一个列表的开端插入一个元素:

 

public class ListDemo {

    static final int N = 50000;

    static long timeList(List list) {

        long start = System.currentTimeMillis();

        Object o = new Object();

        for (int i = 0; i < N; i++)

            list.add(0, o);

        return System.currentTimeMillis() - start;

    }

    public static void main(String[] args) {

        System.out.println("ArrayList 耗时:" + timeList(new ArrayList()));

        System.out.println("LinkedList 耗时:" + timeList(new LinkedList()));

    }

}

 

输出结果是:

 

ArrayList 耗时:2463

 

LinkedList 耗时:15

 

● 空间复杂度

 

在 LinkedList 中有一个私有的内部类,定义如下:

 

private static class Entry {

    Object element;

    Entry next;

    Entry previous;

}

 

每个 Entry对象reference列表中的一个元素,同时还有在 LinkedList 中它的上一个元素和下一个元素。一个有1000个元素的LinkedList 对象将有 1000 个链接在一起的 Entry 对象,每个对象都对应于列表中的一个元素。这样的话,在一个 LinkedList 结构中将有一个很大的空间开销,因为它要存储这 1000 个 Entity 对象的相关信息。

 

ArrayList 使用一个内置的数组来存储元素,这个数组的起始容量是10。当数组需要增长时,新的容量按如下公式获得:新容量=(旧容量*3)/2+1,也就是说每一次容量大概会增长 50%。这就意味着,如果你有一个包含大量元素的 ArrayList 对象,那么最终将有很大的空间会被浪费掉,这个浪费是由ArrayList 的工作方式本身造成的。如果没有足够的空间来存放新的元素,数组将不得不被重新进行分配以便能够增加新的元素。对数组进行重新分配,将会导致性能急剧下降。如果我们知道一个ArrayList将会有多少个元素,我们可以通过构造方法来指定容量。我们还可以通过 trimToSize 方法在 ArrayList 分配完毕之后去掉浪费掉的空间。

 

● 总结

 

ArrayList 和 LinkedList 在性能上各有优缺点,都有各自所适用的地方,总的说来可以描述如下:

 

第一:对 ArrayList 和 LinkedList 而言,在列表末尾增加一个元素所花的开销都是固定的。对 ArrayList 而言,主要是在内部数组中增加一项,指向所添加的元素,偶尔可能会导致对数组重新进行分配;而对 LinkedList 而言,这个开销是统一的,分配一个内部 Entry 对象。

 

第二:在 ArrayList 的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动;而在 LinkedList 的中间插入或删除一个元素的开销是固定的。

 

第三:LinkedList 不支持高效的随机元素访问。

 

第四:ArrayList 的空间浪费主要体现在在 list 列表的结尾预留一定的容量空间,而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗相当的空间。

 

可以这样说:当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList 会提供比较好的性能;当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了。

« 上一篇 下一篇 »

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。