ArrayList和LinkedList、Vector的优缺点?

小短腿 2018-11-09 01:4630 阅读

一般在面试中可能会被问到ArrayList、LinkedList、Vector三者相关的区别!

一般来说我想大概都会回答如下的这些:

 

ArrayList底层是数组结构,查询快,增删慢,线程不安全,效率高。

LinkedList底层是链表数据结构,查询慢,增删快,线程不安全,效率高。

Vector底层是数组结构,查询快,增删慢,线程安全,效率低。

 

以上就是最基本的一个优缺点,但是他们的内部结构,具体怎么实现添加查询这一块的,我想应该有一部分人还是不太清楚。

下面我将带领一起去集合的内部看一看具体的代码实现。

 

ArrayList:

  首先是ArrayList的一个实例化,java提供了一个有参构造和无参构造。下面一起查看代码: 

    /**
     * Constructs an empty list with the specified initial capacity.
      构造具有指定初始容量的空列表。 * *
@param initialCapacity the initial capacity of the list 初始容量列表的初始容量 * @throws IllegalArgumentException if the specified initial capacity 如果指定的初始容量为负,则抛出IllegalArgumentException * is negative */ public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }

  通过上述我们可以看到,这是ArrayList的有参构造,可以自定义集合的初始化长度,否则如果输入的是0那么就使用ArrayList自带的默认的数组缓存区。

    /**
     * Constructs an empty list with an initial capacity of ten.  构造初始容量为10的空列表。
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

  使用无参构造,将会创建一个默认长度的数组。初始长度为10。

    /**
     * Default initial capacity. 默认初始容量  
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.  用于空实例的共享空数组实例
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

   * 解析add添加方法的全过程,下面的add方法相关的所有源代码,

/**
     * Appends the specified element to the end of this list.  将指定的元素追加到列表的末尾
     *
     * @param e element to be appended to this list  将追加到此列表中的e元素
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
     // 调用自动扩容存储机制,确保自动数组有存储新元素的能力。 ensureCapacityInternal(size
+ 1); // Increments modCount!!

     // 自动扩容存储机制处理后,将元素添加到集合的末尾 elementData[size++] = e; return true; }
private void ensureCapacityInternal(int minCapacity) {
    // 判断该数组是否是一个新创建的实例对象
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
       // 如果是,就设置数组的长度为默认长度 10 minCapacity
= Math.max(DEFAULT_CAPACITY, minCapacity); }      // 确保能够有储存能力 ensureExplicitCapacity(minCapacity); }
private void ensureExplicitCapacity(int minCapacity) {
     // 保存这个列表在结构上被修改的次数。 modCount
++; // overflow-conscious code
     // 如果默认的长度减去实际数组的长度大于0,那么就调用
grow()方法
    if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;  // 获取数组原始的长度
        int newCapacity = oldCapacity + (oldCapacity >> 1);  // 获取新的数组的长度 (0 + 0/2)
        if (newCapacity - minCapacity < 0)      // 如果新的值 - 最小值小于0   (0-10)
            newCapacity = minCapacity;        // 将默认值 10 赋值给 新的值
        if (newCapacity - MAX_ARRAY_SIZE > 0)    // 如果新的值 - 最大长度 大于 0  (0 - 2147483639) > 0
            newCapacity = hugeCapacity(minCapacity);  // 调用方法
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);  // 复制原本的数组,定义长度,赋值给自己,来达到自动扩容
    }

  * 总结以上,在ArrayList被无参实例化的时候就会被创建一个空的数组,在添加第一个值时,ArrayList底层的自动扩容机制将会被执行,也就是private void grow(int minCapacity)这个方法会被调用,给内部的elementData数组定义初始长度为10,然后再将值添加到数组的末尾。这里面主要就是牵涉到一个自动扩容机制,在每一次添加之前,都会去判断,当前数组长度是否有实际的存储能力,如果没有那么自动扩容机制就会根据当前数组长度+当前长度/2来计算的方式,对当前数组进行扩容。

 

linkedList:

  * 链接内部结构图

  * 查看linkedList的无参构造和有参构造

  * 无参构造

/**
     * Constructs an empty list.  // 构造一个空列表
     */
    public LinkedList() {
    }

  * 有参构造

/**
     * Constructs a list containing the elements of the specified  构造包含指定元素的列表
     * collection, in the order they are returned by the collection's 集合,按照集合返回的顺序
     * iterator. 迭代器
     *
     * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

  * 解析add添加方法:

/**
     * Appends the specified element to the end of this list.  将指定的元素追加到列表的末尾
     *
     * <p>This method is equivalent to {@link #addLast}.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
/**
     * Links e as last element. 链接做为最后一个元素
     */
    void linkLast(E e) {
     // 将最后一个节点临时存储起来
final Node<E> l = last;

     // 创建一个新的节点,设置新的节点的上一个节点和当前节点的值
final Node<E> newNode = new Node<>(l, e, null);

     // 将新创建的节点重新存储到专门用于保存最后一个节点的值的对象 last
= newNode;

     // 判断是否是第一次添加,如果是第一次添加值,那么上一个值一定是null,否则就会一个值
if (l == null)
        // 如果是第一次添加,那么我们就要将新创建的节点保存到链表的头first first
= newNode; else // 否则就设置l的下一个节点为新的节点
       l.next
= newNode;

     // 长度增加 size
++;
    // 修改次数 modCount
++; }

  * 总结以上:从源代码上我们可以看到,linkedList内部采用的实际上是通过多个节点来保存值,每个节点对象中对它的上一个节点和下一个节点继续记录,以此将所有的节点串联起来,就形成了链表。 

 

Vector:

   vector其实本质上和ArrayList是一样的,底层都是使用了数组来完成,只是vector是从jdk1.0版本开始,ArrayList是1.2版本开始,可以理解的是ArrayList其实就是用来代替Vector的。Vector和ArrayList最大的区别就是一个是线程安全,一个是线程不安全的。这个我们可以通过查看底层代码来得知。

  * 解析add代码

/**
     * Appends the specified element to the end of this Vector.  将指定的元素附加到这个向量的末尾
     * 
     * @param e element to be appended to this Vector
     * @return {@code true} (as specified by {@link Collection#add})
     * @since 1.2
     */
    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

  * 总结上述可得知:相比较ArrayList的add方法,我们可以看出,Vector的add方法添加的同步锁。

 

------------------------------------------------------   分割  -------------------------------------------------------------------

  学无止境,永远不要轻言放弃。

回复数量: 0
暂无评论~~
  请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!