文档章节

ArrayList、LinkedList、Vestor区别

Clarence_D
 Clarence_D
发布于 2017/05/16 18:50
字数 1571
阅读 64
收藏 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
粉丝 9
博文 125
码字总数 100989
作品 0
天津
程序员
Vector、ArrayList、LinkedList 有什么区别?

版权声明:本文供交流学习,能够帮助到你是我最大的荣幸! https://blog.csdn.net/u014231523/article/details/82086185 这个问题主要是考察集合框架的问题,主要考察三者之间的设计区别,以...

兴国First
08/26
0
0
ArrayList vs. LinkedList vs. Vector

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

markGao
2014/01/21
0
0
ArrayList vs. LinkedList vs. Vector

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

LCZ777
2014/07/30
0
0
ArrayList和LinkedList的区别

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

小和尚敲代码
2016/02/27
77
0
ArrayList、linklist、list的区别

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

随智阔
2014/03/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

20180920 rzsz传输文件、用户和用户组相关配置文件与管理

利用rz、sz实现Linux与Windows互传文件 [root@centos01 ~]# yum install -y lrzsz # 安装工具sz test.txt # 弹出对话框,传递到选择的路径下rz # 回车后,会从对话框中选择对应的文件传递...

野雪球
今天
2
0
OSChina 周四乱弹 —— 毒蛇当辣条

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ 达尔文:分享花澤香菜/前野智昭/小野大輔/井上喜久子的单曲《ミッション! 健?康?第?イチ》 《ミッション! 健?康?第?イチ》- 花澤香菜/前野智...

小小编辑
今天
7
3
java -jar运行内存设置

java -Xms64m #JVM启动时的初始堆大小 -Xmx128m #最大堆大小 -Xmn64m #年轻代的大小,其余的空间是老年代 -XX:MaxMetaspaceSize=128m # -XX:CompressedClassSpaceSize=6...

李玉长
今天
4
0
Spring | 手把手教你SSM最优雅的整合方式

HEY 本节主要内容为:基于Spring从0到1搭建一个web工程,适合初学者,Java初级开发者。欢迎与我交流。 MODULE 新建一个Maven工程。 不论你是什么工具,选这个就可以了,然后next,直至finis...

冯文议
今天
2
0
RxJS的另外四种实现方式(四)——性能最高的库(续)

接上一篇RxJS的另外四种实现方式(三)——性能最高的库 上一篇文章我展示了这个最高性能库的实现方法。下面我介绍一下这个性能提升的秘密。 首先,为了弄清楚Most库究竟为何如此快,我必须借...

一个灰
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部