基于JDK 1.8.0。
简介：
ArrayList 底层是通过数组实现的，相当于一个动态的数组。
特点：
- 底层实现：使用数组实现。
- 线程安全：线程不安全。
- 扩容：可以动态扩容。
- 是否可以存放null：可以存放null
- 是否有序：
- 效率：取元素比较快，时间复杂度都是O(1) ， 增加删减元素慢，会导致元素的移动。
- 是否可以重复：可以放入重复的元素。
源码分析：
ArrayList 里面最基础的两个属性 elementData 和 size。elementData 是一个对象数组，用于存放元素。size则是表示实际ArrayList里面的元素个数。
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer.
*/
private transient Object[] elementData;
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
构造函数：
ArrayList有3个构造函数
- 可以从源码看出，传入一个整形的初始容量值作为数组的长度然后new一个数组。
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
2.不传任何参数，默认10为数组长度，调用带参数的构造函数来创建。
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this(10);
}
3.传入一个Collection集合对象，然后将集合转换为Object数组。并设置size属性为elementData数组的长度。
/**
* 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 ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
在分析添加方法之前，有2个方法需要了解和分析的。一个是ensureCapacityInternal()，另一个是grow()。
ensureCapacityInternal 方法是检查当前对象数组的容量能否满足将要装的元素的最大长度。如果不能满足，则动态扩容。扩容方法则是grow方法。
/**
* 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) {
if (minCapacity > 0)
ensureCapacityInternal(minCapacity);
}
private void ensureCapacityInternal(int minCapacity) {
//修改次数+1
modCount++;
// overflow-conscious code
//如果最小容量大于当前数组的长度，就扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
grow() 方法是对ArrayList的动态扩容。操作是，计算出新的容量，创建新的数组，然后将旧的数组元素复制到新的数组， 然后使用新的数组。
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
//获取当前的数组的长度，即当前的容量。
int oldCapacity = elementData.length;
//新容量的计算 = 旧容量 + 旧容量右移1位
//右移运算=对应数字的二进制数的最右补充1位
// 相当于 十进制 / 2，但不等于，例如 1 右移1位=0
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果旧容量仍然大于新容量，则新容量=旧容量
//如果容量的计算超出了int的取值范围，就会导致溢出
//就会导致出现旧容量大于新容量的情况
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新容量大于最大数组大小的话，就调用获取巨大容量方法。
//hugeCapacity 返回的最大值其实也只是 Integer.MAX_VALUE .
//那么就是说，ArrayList的最大容量是 Integer.MAX_VALUE
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//最后调用copyOf方法创建新的数组，并且将旧数组的元素复制到新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
添加元素
添加元素方法有两种，一种是添加单个元素，一种是添加一个集合。添加单个元素使用add()方法，add()方法有1个重载。 添加集合使用addAll()方法，addAll()方法也有1个重载。
- 添加一个元素，不指定位置。虽然是直接将元素添加到数组的最尾端，不用移动数组。但是我觉得效率还是不太好，因为如果数组容量不够的时候，扩容的时候还是要将数组复制一遍。
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @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;
}
- 将元素添加到指定的位置。
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
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++;
}
3.添加一个集合，不指定位置。直接将集合转换成Object数组， 然后追加到数组的最尾端。
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the
* specified collection's Iterator. The behavior of this operation is
* undefined if the specified collection is modified while the operation
* is in progress. (This implies that the behavior of this call is
* undefined if the specified collection is this list, and this
* list is nonempty.)
*
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
//将集合转换成Oibject数组。
Object[] a = c.toArray();
//获取要添加的集合的数组的长度。
int numNew = a.length;
//确认新当前数组的容量， 如果不够，则扩容。
ensureCapacityInternal(size + numNew); // Increments modCount
//将对象数组添加到当前ArrayList数组的尾端。
System.arraycopy(a, 0, elementData, size, numNew);
//size增加。
size += numNew;
return numNew != 0;
}
- 从指定的位置添加一个集合。
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element from the
* specified collection
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
//检查位置是否在数组范围内
rangeCheckForAdd(index);
//将需要添加的集合转换成对象数组
Object[] a = c.toArray();
//获取对象数组的长度
int numNew = a.length;
//确认当前数组的容量，如果不组，则扩容。
ensureCapacityInternal(size + numNew); // Increments modCount
//确定需要移动的元素个数
int numMoved = size - index;
//如果移动的元素个数大于0，则先移动数组元素。
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//将对象数组复制添加到ArrayList的指定位置。
System.arraycopy(a, 0, elementData, index, numNew);
//添加元素个数
size += numNew;
return numNew != 0;
}
删除元素
删除元素有5个公开的方法。删除单个元素用remove() ，有1个重载。删除集合用removeAll()或者removeRange()。 清空集合使用 clear()。私有方法fastRemove()是执行删除的方法， 判断要删除的元素是否处于数组的末端。如果是则直接将元素指向null，如果不是，则移动待删除元素后的元素覆盖 待删除元素， 然后将最后一个元素指向null。
1.根据索引删除一个元素
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
//检查索引是否超出范围
rangeCheck(index);
//增加修改次数
modCount++;
//获取指定索引的元素。
E oldValue = elementData(index);
//计算出需要移动的元素个数
int numMoved = size - index - 1;
//如果需要移动的元素个数大于0，则将数组后面的元素移动覆盖这个索引元素
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//数组的总长度-1，并且将最后一个元素指向null
elementData[--size] = null; // Let gc do its work
//返回删除元素
return oldValue;
}
2.根据元素对象删除元素。
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
public boolean remove(Object o) {
//如果传过来的对象是null。
if (o == null) {
//循环当前的数组，找到等于null的元素，并删除。
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
//如果对象不是null。循环当前数组，调用equals方法找到元素，并删除。
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
//如果找到元素并删除，就会在之前返回true。如果都没有找到的话。则没有对应的元素，返回false。
return false;
}
3.removeAll方法，调用的是私有的batchRemove()方法。
public boolean removeAll(Collection<?> c) {
return batchRemove(c, false);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
4.removeRange方法删除指定范围的元素。
/**
* Removes from this list all of the elements whose index is between
* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
* Shifts any succeeding elements to the left (reduces their index).
* This call shortens the list by {@code (toIndex - fromIndex)} elements.
* (If {@code toIndex==fromIndex}, this operation has no effect.)
*
* @throws IndexOutOfBoundsException if {@code fromIndex} or
* {@code toIndex} is out of range
* ({@code fromIndex < 0 ||
* fromIndex >= size() ||
* toIndex > size() ||
* toIndex < fromIndex})
*/
protected void removeRange(int fromIndex, int toIndex) {
//修改次数加1
modCount++;
//计算出需要移动的元素。
int numMoved = size - toIndex;
//移动元素覆盖掉要删除的元素。
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// Let gc do its work
//计算出删除后的数组的大小。
int newSize = size - (toIndex-fromIndex);
//将已经不需要的元素指向null ，让垃圾收集器进行回收。
while (size != newSize)
elementData[--size] = null;
}
- 清空ArrayList。
/**
* Removes all of the elements from this list. The list will
* be empty after this call returns.
*/
public void clear() {
//修改次数加1
modCount++;
// Let gc do its work
//循环将所有数组元素指向null
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
获取元素
ArrayList的优势就在于获取元素。因为底层是使用数组实现的。所以获取任意位置的元素的时间复杂度都是 O(1)。 get() 方法是获取元素的方法。
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
//检测索引是否超出范围。
rangeCheck(index);
//根据索引直接返回数组元素。elementData方法也只是直接返回数组元素。
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
总结
ArrayList 的主要方法都没有做到线程安全。所以单线程的话就使用ArrayList是效率比较高的。
