文档章节

ArrayList、LinkedList、Vestor区别

Clarence_D
 Clarence_D
发布于 2017/05/16 18:50
字数 1571
阅读 65
收藏 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
博文 129
码字总数 103146
作品 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和LinkedList的区别

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

1314Stone
2017/11/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Ubuntu18.04 安装MySQL

1.安装MySQL sudo apt-get install mysql-server 2.配置MySQL sudo mysql_secure_installation 3.设置MySQL非root用户 设置原因:配置过程为系统root权限,在构建MySQL连接时出现错误:ERROR...

AI_SKI
今天
2
0
3.6 rc脚本(start方法) 3.7 rc脚本(stop和status方法) 3.8 rc脚本(以daemon方式启动)

3.6-3.7 rc脚本(start、stop和status方法) #!/usr/bin/env python# -*- coding: utf-8 -*-# [@Version](https://my.oschina.net/u/931210) : python 2.7# [@Time](https://my.oschina.......

隐匿的蚂蚁
今天
3
0
Cnn学习相关博客

CNN卷积神经网络原理讲解+图片识别应用(附源码) 笨方法学习CNN图像识别系列 深度学习图像识别项目(中):Keras和卷积神经网络(CNN) 卷积神经网络模型部署到移动设备 使用CNN神经网络进行...

-九天-
昨天
4
0
flutter 底部输入框 聊天输入框 Flexible

想在页面底部放个输入框,结果键盘一直遮住了,原来是布局问题 Widget build(BuildContext context) { return Scaffold( appBar: AppBar( title: Text("评论"), ...

大灰狼wow
昨天
4
0
Kernel I2C子系统

备注:所有图片来源于网络 1,I2C协议: 物理拓扑: I2C总线由两根信号线组成,一条是时钟信号线SCL,一条是数据信号线SDA。一条I2C总线可以接多个设备,每个设备都接入I2C总线的SCL和SDA。I...

yepanl
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部