文档章节

ArrayList vs. LinkedList vs. Vector

markGao
 markGao
发布于 2014/01/21 18:20
字数 1093
阅读 196
收藏 8

1. List概览

List,就像它的名字暗示的一样,是一组排列有序的元素。当我们讨论List的时候,很容易将它和Set作比较。Set是一组唯一的而且排列无序的元素。

下图是集合类的层次结构图。你可以总体上知道我们今天讨论的主题。

2. ArrayList vs. LinkedList vs. Vector

从上图可知,它们都实现了List接口。它们的用法差不多,主要的区别在于它们对于不同操作的操作速度不同。

ArrayList是可以改变大小的数组。当有元素添加到ArrayList中去时,它的大小动态的增加。元素可以直接通过get()和set() 方法进行访问,因为ArrayList实际上是数组。LinkedList是个双向链表。它的add()和remove()方法比ArrayList快, 但是get()和set()方法却比ArrayList慢。Vector和ArrayList类似,但是Vector是同步的。如果在线程安全的环境下, 使用ArrayList是更好的选择。添加元素的时候,当超过初始容量的时候,Vector和ArrayList需要更多的空间:Vector需要将数组 的大小增加一倍,而ArrayList需要增加50%。

LinkedList还实现了Queue接口,这样就比ArrayList和Vector多出了一些方法如offer(), peek(), poll()等。

注意:ArrayList的初始容量(initial capacity)很小。我们应该设置一个比较大的初始容量,这样可以避免重新改变大小。

3. ArrayList的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
ArrayList al =     new     ArrayList();
al.add(     3     );
al.add(     2     );     
al.add(     1     );
al.add(     4     );
al.add(     5     );
al.add(     6     );
al.add(     6     );
 
Iterator iter1 = al.iterator();
while     (iter1.hasNext()){
         System.out.println(iter1.next());
}

4. LinkedList的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
LinkedList ll =     new     LinkedList();
ll.add(     3     );
ll.add(     2     );     
ll.add(     1     );
ll.add(     4     );
ll.add(     5     );
ll.add(     6     );
ll.add(     6     );
 
Iterator iter2 = ll.iterator();
while     (iter2.hasNext()){
         System.out.println(iter2.next());
}

由上可见,它们的用法相同,主要的区别在于它们内部的实现,以及操作的复杂度的不同。

5. Vector

Vector几乎和ArrayList相等,主要的区别在于Vector是同步的。正因为此,Vector比ArrayList的开销更大。通常大部分程序员都使用ArrayList,他们可以自己写代码进行同步。

6. ArrayList vs. LinkedList的性能比较

时间复杂度如下:

* 表中的add()指的是add(E e)(即是在列表末尾添加元素),remove()方法指的是remove(int index)。

ArrayList对于任意索引的插入/删除操作的时间复杂度是O(n),而在列表的尾部的操作时间为O(1)。

LinkedList对于任意索引的插入/删除操作的时间复杂度是O(n),而在列表的头部或尾部的操作时间为O(1)。

(译者注:这里原文解释的不是太清楚。对于任意索引的插入/删除操作

Arrays:

  • 找到插入/删除位置的时间复杂度是O(1)

  • 进行插入/删除操作的时间复杂度是O(n)

Linked Lists:

  • 找到插入/删除位置的时间复杂度是O(n)

  • 进行插入/删除操作的时间复杂度是O(1)

我使用下面的代码测试它们的性能:

package javaBasic;

import java.util.ArrayList;
import java.util.LinkedList;

public class ArrayListVSLinkedList {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        LinkedList<Integer> linkedList = new LinkedList<Integer>();

        // ArrayList add
        long startTime = System.nanoTime();

        for (int i = 0; i < 100000; i++) {
            arrayList.add(i);
        }
        long endTime = System.nanoTime();
        long duration = endTime - startTime;
        System.out.println("ArrayList add:  " + duration);

        // LinkedList add
        startTime = System.nanoTime();

        for (int i = 0; i < 100000; i++) {
            linkedList.add(i);
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("LinkedList add: " + duration);

        // ArrayList get
        startTime = System.nanoTime();

        for (int i = 0; i < 10000; i++) {
            arrayList.get(i);
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("ArrayList get:  " + duration);

        // LinkedList get
        startTime = System.nanoTime();

        for (int i = 0; i < 10000; i++) {
            linkedList.get(i);
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("LinkedList get: " + duration);

        // ArrayList remove
        startTime = System.nanoTime();

        for (int i = 9999; i >= 0; i--) {
            arrayList.remove(i);
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("ArrayList remove:  " + duration);

        // LinkedList remove
        startTime = System.nanoTime();

        for (int i = 9999; i >= 0; i--) {
            linkedList.remove(i);
        }
        endTime = System.nanoTime();
        duration = endTime - startTime;
        System.out.println("LinkedList remove: " + duration);
    }

}

输出如下:

ArrayList add:  135335877
LinkedList add: 52054821
ArrayList get:  539366
LinkedList get: 209043151
ArrayList remove:  608561973
LinkedList remove: 212236791

它们的性能的差别很显著。LinkedList对于add()和remove()相对于ArrayList要快,但是get()要慢些。按照复杂度 以及测试结果来看,我们很容易知道什么时候该使用ArrayList,什么时候该使用LinkedList。简而言之,下面的情况该使用 LinkedList:

  • 如果没有大量的随机访问

  • 如果有很多add/remove的操作


本文转载自:http://www.importnew.com/8782.html

markGao
粉丝 15
博文 187
码字总数 91352
作品 0
宝山
程序员
私信 提问
ArrayList vs. LinkedList vs. Vector

List概览 List,就像它的名字暗示的一样,是一组排列有序的元素。当我们讨论List的时候,很容易将它和Set作比较。Set是一组唯一的而且排列无序的元素。 下图是集合类的层次结构图。你可以总体...

LCZ777
2014/07/30
21
0
ArrayList VS Vector VS LinkedList

ArrayList VS Vector 相同点:1>都是基于Object数组实现的。2>都允许添加null元素。 不同点:1>ArrayList不是线程安全的,Vector是线程安全的(方法是Synchronized的)。2>ArrayList扩容后容量...

A__17
2018/03/05
18
0
java.util包中集合详解

本文只是集合的概述,介绍集合之间的关系,以及各种集合的异同,不会深入介绍具体的实现,具体实现的介绍,可以参见文中提供的链接。 java集合概述 java集合整体分为collection和map两种,接...

jacksu在简书
2018/01/25
0
0
Java 容器 & 泛型:二、ArrayList 、LinkedList和Vector比较

Writer:BYSocket(泥沙砖瓦浆木匠) 微博:BYSocket 豆瓣:BYSocket 继续上一篇的容器文章认识容器,泥瓦匠慢慢带你们走进List的容器解说。今天泥瓦匠想说说 ArrayList 、LinkedList和Vecto...

泥沙砖瓦浆木匠
2015/03/19
1K
10
Java集合类之List源码学习笔记

Java集合类主要分为List,Set,Map三大类。ArrayList和LinkedList是则List接口的俩个实现。他们都可以作为顺序存放元素的容器,并且元素可以重复,可以为null值。当有元素重复时,如果按元素而...

单线程程序员
2018/12/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

还为PDF转Word抓狂?以下神器让你在职场倍受欢迎!

身在职场的你,是否一直在琢磨:如何能让自己在公司更受欢迎?如何才能在办公室里混个好人缘?如何在同事圈里留个好印象?其实,想要让自己成为受欢迎的人,只要让自己成为大家需要的人不就行...

foxit2world
9分钟前
3
0
AndServer+Service打造Android服务器实现so文件调用

so 文件调用 随着 Android 移动安全的高速发展,不管是为了执行效率还是程序的安全性等,关键代码下沉 native 层已成为基本操作。 native 层的开发就是通指的 JNI/NDK 开发,通过 JNI 可以实...

夜幕NightTeam
11分钟前
3
0
Docker下kafka学习三部曲之二:本地环境搭建

在上一章《 Docker下kafka学习,三部曲之一:极速体验kafka》中我们快速体验了kafka的消息分发和订阅功能,但是对环境搭建的印象仅仅是执行了几个命令和脚本,本章我们通过实战来学习如何编写...

程序员欣宸
11分钟前
2
0
萌新推荐!不再为Excel转换PDF发愁,Aspose.Cells for .NET一步到位!

Aspose.Cells for .NET(点击下载)是Excel电子表格编程API,可加快电子表格管理和处理任务,支持构建具有生成,修改,转换,呈现和打印电子表格功能的跨平台应用程序。 将Excel工作簿转换为...

mnrssj
12分钟前
2
0
对于绘画小白怎么画制服?该注意什么?

怎样制作学生服装?想必绘画初学者们常常会想的问题吧,不知道怎样才能画好人物的衣服,别着急,今日就在这儿讲一些关于如何绘画学生衣服校服的教程给我们!期望能够帮到你们! 轻便西装是不...

热爱画画的我
18分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部