JDK源码-List系列

List

• List是一个有序的集合.使用者可以直接通过下标来获取元素.
• List与Set不同,它允许重复元素的存在.
• List继承与Collections,它的主要实现有ArrayList,LinkedList,Vector等等.
• 集合在遍历的同时,进行插入删除操作会造成错误.

ArrayList

• List的一个实现类,同时也继承了接口RandomAccess,Cloneable, java.io.Serializable.它是具有fail-fast机制.

• ArrayList默认的容量大小为10

/**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

• ArrayList提供了两个默认的空数据存储对象.调用无参构造器的时候,真正存储数据的elementData对象将会赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA；调用有参的构造器时,elementData赋值为EMPTY_ELEMENTDATA.那么,为甚么要这样做?他是为了,在数据添加并且进行扩容的时候,知道当前容器扩容的大小.当elementData为DEFAULTCAPACITY_EMPTY_ELEMENTDATA时,就会自动扩容到DEFAULT_CAPACITY或者传入minCapacity(扩容大小)；而当elementData为EMPTY_ELEMENTDATA时,好,这个时候elementData的大小已经是确定的了,直接根据elementData.length扩容至其1.5倍即可.

/**
     * 在有参构造时,被调用
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 在无参构造时,被调用
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

• ArrayList对外提供的扩容方法:

/**
     * Increases the capacity of this <tt>ArrayList</tt> instance, if
     * necessary, to ensure that it can hold at least the number of elements
     * specified by the minimum capacity argument.
     *
     * @param   minCapacity   the desired minimum capacity
     */
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

• ArrayList对外提供了将容器大小转为当前容器存储元素个数大小的方法.

/**
     * Trims the capacity of this <tt>ArrayList</tt> instance to be the
     * list's current size.  An application can use this operation to minimize
     * the storage of an <tt>ArrayList</tt> instance.
     */
    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

• ArrayList无法保证线程安全,需要使用者自己保证线程安全.

LinkedList

• 底层通过双向链表机制实现.
• 插入或者删除元素时,时间复杂度为O(1)；查询元素时时间复杂度为O(n)；