Java 集合:Collection,List,ArrayList,Vector,LinkedList(实现方式,对比)

Collection 与 List



Collection 是 Java 集合的一个根接口,JDK 没有它的实现类。
内部仅仅做 add(),remove(),contains(),size() 等方法的声明。

List 接口是Collection 接口的一个子类,在Collection 基础上扩充了方法。同时可以对每个元素插入的位置进行精确的控制,它的主要实现类有 ArrayList,Vector,LinkedList

LIST接口实现的类:插入值允许为空,也允许重复。

ArrayLIst



ArrayList实现了List接口,意味着可以插入空值,也可以插入重复的值,非同步,它是 基于数组的一个实现。

部分成员变量如下:

//默认初始值
private static final int DEFAULT_CAPACITY = 10
//存放数据的数组
transient Object[] elementData;                               

**这里可以看出,elementData提示了是基于数组的实现,DEFAULT_CAPACITY指定了默认容器为10.
下面重点理解add()方法,这将有助于理解ArrayList的应用场景和性能消耗:**

add()

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++;
    if(minapacity - elementData.length > 0)
        grow(minCapacity);
}
private void grow(int minCapacity){
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if(newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if((newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

这里可以看到,进行一个 add()方法,首先通过 ensureCapacityInternal(size + 1); 判断需不需要扩容;然后再进行 elementData[size++] = e。 插入的时间复杂度O(1)。是非常高效的。(But,这不是在固定位置插入的情况下),如果在固定位置插入,那么代码:

public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

System.arraycopy(elementData, index, elementData, index + 1, size - index); 这个可以看出,这时候就是比较低效的了。

那么网上很多说 ArrayList 不适合 增删操作非常多的操作,这是怎么回事呢?首先可以看到这句话: elementData = Arrays.copyOf(elementData, newCapacity); 需要知道的是, Arrays.copyOf 函数的内部实现是再创建一个数组,然后把旧的数组的值一个个复制到新数组中。当经常增加操作的时候,容量不够的时候,就会进行上述的扩容操作,这样性能自然就下来了。或者说,当我们在固定位置进行增删的时候,都会进行 System.arraycopy(elementData, index, elementData, index + 1, size - index); 也是非常低效的。

分析了低效出现的原因,那么我们就可以知道:如果我们需要经常进行特定位置的增删操作,那么最好还是不要用这个了,但是,如果我们基本上没有固定位置的增删操作,最好是要预估数据量的大小,然后再初始化最小容量,这样可以有效的避免扩容。如下代码:

ArrayList arrayList = new ArrayList(20);

总结:

  1. ArrayList 可以插入空值,也可以插入重复值
  2. ArrayList 是基于数组的时候,所以很多数组的特性也直接应用到了 ArrayList。
  3. ArrayList 的性能消耗主要来源于扩容和固定位置的增删。
  4. ArrayList 创建的时候 需要考虑是否要初始化最小容量,以此避免扩容带来的消耗。

Vector



上述的 ArrayList 不是线程安全的。那么 Vector 就可以看作是 ArrayList 的一个线程安全版本。由于也是实现了 List 接口,所以也是 可以插入空值,可以插入重复的值。

内部成员变量:

protected Object[] elementData;
public Vector() {
    this(10);
}

可以看到,也是基于 数组的实现,初始化也是 10 个容量。 那么,再来看看 add()方法是否和 ArrayList 相同。

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

可以看到,和 ArrayList 也是一样的,只是加了 synchronized 进行同步, 其实很多其他方法都是通过加 synchronized 来实现同步。

总结:

  1. 可以插入空值,也可以插入重复值
  2. 也是基于数组的时候,所以很多数组的特性也直接应用到了 VVector。
  3. 性能消耗也主要来源于 扩容。
  4. 创建的时候 需要考虑是否要初始化最小容量,以此避免扩容带来的消耗。
  5. 相当于 ArrayList 的线程安全版本,实现同步的方式 是通过 synchronized。

LinkedList



LinkedList 实现了 List 接口,所以LinkedList 也可以放入重复的值,也可以放入空值。LinkedList不支持同步。LinkedList 不同于ArrayList 和Vector,它是使用链表的数据结构,不再是数组。

成员变量:

transient int size = 0;    //数量
transient Node<E> first;   //首节点
transient Node<E> last;    //最后节点  

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}     

那么,在进行 add() 方法的时候:

public boolean add(E e) {
    linkLast(e);
    return true;
}
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}    

当进行增删的时候,只需要改变指针,并不会像数组那样出现整体数据的大规模移动,复制等消耗性能的操作。

ArrayList,Vector,LinkedList 的整体对比



实现方式:

  • ArrayList,Vector 是基于数组的实现。
  • LinkedList 是基于链表的实现。

同步问题:

  • ArrayList,LinkedList 不是线程安全的。
  • Vector 是线程安全的,实现方式是在方法中加 synchronized 进行限定。

适用场景和性能消耗:

  • ArrayList 和 Vector 由于是基于数组的实现,所以在固定位置插入,固定位置删除这方面会直接是 O(n)的时间复杂度,另外可能会出现扩容的问题,这是非常消耗性能的。
  • LinkedList 不会出现扩容的问题,所以比较适合增删的操作。但是由于不是数组的实现,所以在 定位方面必须使用 遍历的方式,这也会有 O(n)的时间复杂度
时间: 2024-10-02 02:01:34

Java 集合:Collection,List,ArrayList,Vector,LinkedList(实现方式,对比)的相关文章

java集合框架05——ArrayList和LinkedList的区别

本文为博主原创文章,转载请注明出处:http://blog.csdn.net/eson_15/article/details/51145788 前面已经学习完了List部分的源码,主要是ArrayList和LinkedList两部分内容,这一节主要总结下List部分的内容. List概括         先来回顾一下List在Collection中的的框架图:     从图中我们可以看出:         1. List是一个接口,它继承与Collection接口,代表有序的队列.       

Java基础-16总结List的子类,ArrayList,Vector,LinkedList,泛型,增强for循环,静态导入,可变参数

你需要的是什么,直接评论留言. 获取更多资源加微信公众号"Java帮帮" (是公众号,不是微信好友哦) 还有"Java帮帮"今日头条号,技术文章与新闻,每日更新,欢迎阅读 学习交流请加Java帮帮交流QQ群553841695 分享是一种美德,分享更快乐! 1:List的子类(掌握) (1)List的子类特点 ArrayList: 底层数据结构是数组,查询快,增删慢 线程不安全,效率高 Vector: 底层数据结构是数组,查询快,增删慢 线程安全,效率低 Linked

Java 集合系列06之 Vector详细介绍(源码解析)和使用示例

概要 学完ArrayList和LinkedList之后,我们接着学习Vector.学习方式还是和之前一样,先对Vector有个整体认识,然后再学习它的源码:最后再通过实例来学会使用它.第1部分 Vector介绍第2部分 Vector数据结构第3部分 Vector源码解析(基于JDK1.6.0_45)第4部分 Vector遍历方式第5部分 Vector示例 转载请注明出处:http://www.cnblogs.com/skywang12345/p/3308833.html   第1部分 Vecto

【Java集合系列】---ArrayList

开篇前言--ArrayList中的基本方法 前面的博文中,小编主要简单介绍java集合的总体架构,在接下来的博文中,小编将详细介绍里面的各个类,通过demo.对比,来对java集合类进行更加深入的理解和认识,希望可以帮助有有需要的小伙伴们`(*∩_∩*)′,不足之处,还请小伙伴们多多指教哦`(*∩_∩*)′.今天这篇博文,小编主要介绍List接口中的ArrayList集合,ArrayList即数组列表,so,她肯定和数组有一定的关系,我们知道List集合的特征有两个,一个是有序:第二个List里

java集合框架03——ArrayList和源码分析

   上一章学习了Collection的架构,并阅读了部分源码,这一章开始,我们将对Collection的具体实现进行详细学习.首先学习List.而ArrayList又是List中最为常用的,因此本章先学习ArrayList.先对ArrayList有个整体的认识,然后学习它的源码,深入剖析ArrayList. 1. ArrayList简介     首先看看ArrayList与Collection的关系:     ArrayList的继承关系如下: [java] view plain copy  

Java集合-Collection

原文链接   作者:Jakob Jenkov  译者:祖强 Collection接口是 (java.util.Collection)是Java集合类的顶级接口之一.所以不能直接实例化一个Collection,但是可以实例化它的一个子类,你或许经常把这些子类作为一个Collection统一探讨.在这篇文章中,你将看到如何处理. 下面是本文的一个主题列表: Collection子类 增加和移除元素 检测一个Collection是否包含一个确定的元素 Collection大小 遍历一个Collecti

Java集合源码剖析:LinkedList源码剖析

LinkedList简介 LinkedList是基于双向循环链表(从源码中可以很容易看出)实现的,除了可以当做链表来操作外,它还可以当做栈.队列和双端队列来使用. LinkedList同样是非线程安全的,只在单线程下适合使用. LinkedList实现了Serializable接口,因此它支持序列化,能够通过序列化传输,实现了Cloneable接口,能被克隆. LinkedList源码剖析 LinkedList的源码如下(加入了比较详细的注释): package java.util; publi

Java集合学习(五) LinkedList详细介绍(源码解析)和使用示例

前面,我们已经学习了ArrayList,并了解了fail-fast机制.这一章我们接着学习List的实现类--LinkedList. 和学习ArrayList一样,接下来呢,我们先对LinkedList有个整体认识,然后再学习它的源码:最后再通过实例来学会使用LinkedList. 第1部分 LinkedList介绍 LinkedList简介 LinkedList 是一个继承于AbstractSequentialList的双向链表.它也可以被当作堆栈.队列或双端队列进行操作. LinkedLis

深入Java集合系列之二:LinkedList

前言 LinkedList底层使用的双端链表,即每个节点既包含指向其后继的引用也包括指向其前驱的引用,LinkedList实现了List接口,继承了AbstractSequentialList类,在频繁进行插入以及删除的情况下效率较高. LinkedList使用较多的是add.get和remove,源码的分析也将对这三个方法进行分析. add方法 先看add方法: public boolean add(E e) { //把e放在链表的最后一个位置 linkLast(e); return true

Java基础-15总结对象数组,集合Collection,集合List

你需要的是什么,直接评论留言. 获取更多资源加微信公众号"Java帮帮" (是公众号,不是微信好友哦) 还有"Java帮帮"今日头条号,技术文章与新闻,每日更新,欢迎阅读 学习交流请加Java帮帮交流QQ群553841695 分享是一种美德,分享更快乐! 1:对象数组(掌握) (1)数组既可以存储基本数据类型,也可以存储引用类型.它存储引用类型的时候的数组就叫对象数组. (2)案例: 用数组存储5个学生对象,并遍历数组. package cn.itcast_01;