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)；
