文档章节

ArrayList、LinkedList、Vestor区别

Clarence_D
 Clarence_D
发布于 2017/05/16 18:50
字数 1571
阅读 60
收藏 0
点赞 0
评论 0

ArrayList、LinkedList、Vestor这两个类都实现了java.util.List接口,各自不同的特性。主要如下: 

特性

  • 同步性 :ArrayList,LinkedList是不同步的,而Vestor是同步的。所以如果不要求线程安全的话,可以使用ArrayList或LinkedList,可以节省为同步而耗费的开销。但在多线程的情况下,有时候就不得不使用Vector了。当然,也可以通过一些办法包装ArrayList,LinkedList,使他们也达到同步,但效率可能会有所降低。 
  • 数据增长 :从内部实现机制来讲ArrayList和Vector都是使用Objec的数组形式来存储的。当你向这两种类型中增加元素的时候,如果元素的数目超出了内部数组目前的长度它们都需要扩展内部数组的长度,Vector缺省情况下自动增长原来一倍的数组长度,ArrayList是原来的50%,所以最后你获得的这个集合所占的空间总是比你实际需要的要大。所以如果你要在集合中保存大量的数据那么使用Vector有一些优势,因为你可以通过设置集合的初始化大小来避免不必要的资源开销。 
  • 检索、插入、删除对象的效率 :ArrayList和Vector中,从指定的位置(用index)检索一个对象,或在集合的末尾插入、删除一个对象的时间是一样的,可表示为O(1)。但是,如果在集合的其他位置增加或移除元素那么花费的时间会呈线形增长:O(n-i),其中n代表集合中元素的个数,i代表元素增加或移除元素的索引位置。为什么会这样呢?以为在进行上述操作的时候集合中第i和第i个元素之后的所有元素都要执行(n-i)个对象的位移操作。 

ArrayList和LinkedList的大致区别

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

 实战

    我们来看看ArrayList与LinkedList的查询

public class Test {
    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;
    }
    static long readList(List list){
        long start=System.currentTimeMillis();
        for(int i=0,j=list.size();i<j;i++){

        }
        return System.currentTimeMillis()-start;
    }
    static List addList(List list){
        Object o = new Object();
        for(int i=0;i<N;i++) {
            list.add(0, o);
        }
        return list;
    }
    public static void main(String[] args) {
        System.out.println("ArrayList添加"+N+"条耗时:"+timeList(new ArrayList()));
        System.out.println("LinkedList添加"+N+"条耗时:"+timeList(new LinkedList()));
        List list1=addList(new ArrayList());
        List list2=addList(new LinkedList());
        System.out.println("ArrayList查找"+N+"条耗时:"+readList(list1));
        System.out.println("LinkedList查找"+N+"条耗时:"+timeList(list2));
    }
}

我们向集合中添加5万条数据,我们来看下控制台输出结果如何:

ArrayList添加50000条耗时:240
LinkedList添加50000条耗时:7
ArrayList查找50000条耗时:0
LinkedList查找50000条耗时:9

显然我们可以看出ArrayList更适合读取数据,linkedList更多的时候添加或删除数据。

PS

    ArrayList内部是使用可増长数组实现的,所以是用get和set方法是花费常数时间的,但是如果插入元素和删除元素,除非插入和删除的位置都在表末尾,否则代码开销会很大,因为里面需要数组的移动。
LinkedList是使用双链表实现的,所以get会非常消耗资源,除非位置离头部很近。但是插入和删除元素花费常数时间。

ArrayList和Vector的大致区别

  • ArrayList在内存不够时默认是扩展50% + 1个,Vector是默认扩展1倍。
  • Vector属于线程安全级别的,但是大多数情况下不使用Vector,因为线程安全需要更大的系统开销。

 源码

ArrayList源码

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  //增加元素,判断是否能够容纳。不能的话就要新建数组
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    //如果添加一个元素之后,新容器的大小大于容器的容量,那么就无法存值了,需要扩充空间
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);//扩充的空间增加原来的50%(即是原来的1.5倍)
    if (newCapacity - minCapacity < 0)//如果容器扩容之后还是不够,那么干脆直接将minCapacity设为容器的大小
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)//如果扩充的容器太大了的话,那么就执行hugeCapacity
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Vector源码

public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);//增加元素,判断是否能够容纳。不能的话就要新建数组
    elementData[elementCount++] = obj;
}
private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    //如果添加一个元素之后,新容器的大小大于容器的容量,那么就无法存值了,需要扩充空间
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    /* 这个扩容需要做个判断:如果容量增量初始化的不是0,即使用的public Vector(int initialCapacity,
     * int capacityIncrement) 
     * 构造方法进行的初始化,那么扩容的容量是(oldCapacity+capacityIncrement)
     * 如果没有设置容量增量,那么扩容后的容量就是(oldCapacity+oldCapacity),就是原有容量的二倍。
     */
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)//如果容器扩容之后还是不够,那么干脆直接将minCapacity设为容器的大小
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)//如果扩充的容器太大了的话,那么就执行hugeCapacity
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

    所以,如果只是查找特定位置的元素或只在集合的末端增加、移除元素,那么使用Vector或ArrayList都可以,但要考虑下是否需要使用线程安全。如果是对其它指定位置的插入、删除操作,最好选择LinkedList。

© 著作权归作者所有

共有 人打赏支持
Clarence_D
粉丝 8
博文 112
码字总数 98515
作品 0
天津
程序员
ArrayList vs. LinkedList vs. Vector

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

markGao ⋅ 2014/01/21 ⋅ 0

ArrayList和LinkedList的区别

一般大家都知道ArrayList和LinkedList的大致区别: 1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。 2.对于随机访问get和set,ArrayList觉得优于LinkedList,因...

小和尚敲代码 ⋅ 2016/02/27 ⋅ 0

ArrayList vs. LinkedList vs. Vector

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

LCZ777 ⋅ 2014/07/30 ⋅ 0

ArrayList、linklist、list的区别

List是一个接口,ArrayList和LinkedList是两个实现类,他们实现的方式不一样,其实LinkedList才是真正的链表(如果不清楚什么是链表,需要了解一下相关数据结构的知识,这不是一两句话能说清楚...

随智阔 ⋅ 2014/03/04 ⋅ 0

Java:ArrayList和LinkedList区别

一般大家都知道ArrayList和LinkedList的大致区别: 1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。 2.对于随机访问get和set,ArrayList觉得优于LinkedList,因...

heiyexue ⋅ 2014/09/09 ⋅ 0

ArrayList和LinkedList的区别

大致的区别: ArrayList是实现了基于动态数组的数据结构, LinkedList基于链表的数据结构 对于随机访问get和set,ArrayList优于LinkedList,因为ArrayList可以随机定位,而LinkedList要移动指针一...

1314Stone ⋅ 2017/11/23 ⋅ 0

Arrylist、linkelist、vector之间的区别

ArrayList,LinkedList是不同步的,而Vector是同步的,Vector适合线程使用, ArrayList和Vector都是使用Objec的数组形式来存储的,当元素数目超出其长度时,Vector缺省情况下自动增长原来一倍...

刘谱_smile ⋅ 2015/10/23 ⋅ 0

LinkedList VS ArrayList

List,根据名字我们知道是有序的元素集合。先贴一张集合的关系图。这里我们分析LinkedList与ArrayList。 Collection结构 LinkedList与ArrayList 它们都实现了List接口。但是内部实现上有些区...

Real_man ⋅ 03/21 ⋅ 0

ArrayList VS LinkedList

java编程中我们用最多的几个类可以就是String,ArrayList,HashMap了.特别是ArrayList我们几乎无人不知,甚至有乱用的嫌疑了我们来看看ArrayList和LinkedList的区别.故名思意ArrayList是数组表,...

steven ⋅ 2016/03/30 ⋅ 0

详解Java中ArrayList、Vector、LinkedList三者的异同点

一、ArrayList ArrayList是一个可以处理变长数组的类型,这里不局限于“数”组,ArrayList是一个泛型类,可以存放任意类型的对象。顾名思义,ArrayList是一个数组列表,因此其内部是使用一个...

断桥残雪断桥残雪 ⋅ 2015/08/12 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

10个免费的服务器监控工具

监控你的WEB服务器或者WEB主机运行是否正常与健康是非常重要的。你要确保用户始终可以打开你的网站并且网速不慢。服务器监控工具允许你收集和分析有关你的Web服务器的数据。 有许多非常好的服...

李朝强 ⋅ 17分钟前 ⋅ 0

压缩工具之zip-tar

zip 支持目录压缩。使用yum安装zip包,使用yum安装unzip包 zip 1.txt.zip 1.txt #将1.txt文件压缩,新生成的压缩文件为1.txt.zip,原文件保留 zip -r 123.zip 123/ #-r对目录操作。将123/目录...

ZHENG-JY ⋅ 18分钟前 ⋅ 0

Dubbo @Activate注解使用和实现解析

Activate注解标识一个扩展是否被激活和使用,可以放在定义的类上和方法上,dubbo用它在SPI扩张类定义上,标识这个扩展实现激活的条件和时机,先看下定义: /** * Activate * <p/> * ...

哲别0 ⋅ 25分钟前 ⋅ 0

6.5 zip压缩工具 tar打包 打包并压缩

1.tar tar命令格式 [-zjxcvfpP] filename tar -z:表示同时用gzip压缩。 -j:表示同时用bzip2压缩。 -J:表示同时用xz压缩。 -x:表示解包或者解压缩。 -t:表示查看tar包里的文件。 -c:表示建...

oschina130111 ⋅ 26分钟前 ⋅ 0

Linux系统工程狮养成记

如今的社会,随着时代的发展,出现了很多职业,像电子类,计算机类的专业,出现了各种各样的工程师,有算法工程师,java工程师,前端工程师,后台工程师,Linux工程师,运维工程师等等,不同...

六库科技 ⋅ 33分钟前 ⋅ 0

Linux 机器的渗透测试命令备忘表

如下是一份 Linux 机器的渗透测试备忘录,是在后期开发期间或者执行命令注入等操作时的一些典型命令,设计为测试人员进行本地枚举检查之用。 此外,你还可以从这儿(https://gbhackers.com/c...

寰宇01 ⋅ 34分钟前 ⋅ 0

windows 安装java开发环境,配置jdk

下载jdk安装文件 链接:https://pan.baidu.com/s/1UEKPjnAdMqNj612B39Pfsg 密码:ipqx 如果javac无法使用 1,检查环境变量名称中是否有空格。。。,去除后即可 2,将JAVA_HOME替换为原始路径...

阿豪boy ⋅ 36分钟前 ⋅ 0

简析log4j的实现方式

刚加入新公司,对日志的要求比较严格,对此特意花了几天时间看了一下log4j的源码,大概了解了一下log4j的实现方式,总结如下: log4j的实现分为两个步骤:log4j.xml的加载,logger的使用 这里...

zdatbit ⋅ 今天 ⋅ 0

win环境下jdk7与jdk8共存配置

1.jdk安装包 jdk安装包 安装步骤略 2.jdk等配置文件修改 在安装JDK1.8时(本机先安装jdk1.7再安装的jdk1.8),会将java.exe、javaw.exe、javaws.exe三个文件copy到了C:\Windows\System32,这...

泉天下 ⋅ 今天 ⋅ 0

windows profesional 2017 build problem

.net framework .... https://stackoverflow.com/questions/43330915/could-not-load-file-or-assembly-microsoft-build-frameworkvs-2017...

机油战士 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部