本文简单分析一下JDK1.7的ArrayList源码,看一下其内部的结构以及典型方法的实现
ArrayList内部结构
查看ArrayList的源码,发现其继承自AbstractList,实现了List,RandomAccess,Cloneable以及Serializable接口,如:
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList包含一个数组对象Object[]
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
* DEFAULT_CAPACITY when the first element is added.
*/
private transient Object[] elementData;
源代码
/**
* 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;
}
add的步骤
add包含如下几个部分: 1) - 确保数组是否有足够的容量,如果不够,则扩容 2) - 将需要添加的元素存放在elementData[size]上,然后size+1 3) - modCount加1
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
如果 elementData == EMPTY_ELEMENTDATA,则需要确定数组的最小容量大小。
其中,DEFAULT_CAPACITY 和EMPTY_ELEMENTDATA 内容如下:
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
确定大小之后,调用ensureExplicitCapacity方法,看是否需要扩容ensureExplicitCapacity方法
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
ensureExplicitCapacity完成modCount加1的操作,然后看是否需要扩容,如果扩容则调用grow方法
grow方法
/**
* 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;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
grow方法中,数组的大小将扩展到1.5倍,然后使用Arrays.copyOf完成数组的扩容和复制
添加第一个元素的时候,ArrayList中的数组会被初始为默认值10
如使用如下示例:
import java.util.ArrayList;import java.util.List;
public class ArrayListExample {
public static void main(String[] args) { List<String> words = new ArrayList<>(); words.add("Hello"); words.add("Java"); System.out.println(words); }
}
新建一个ArrayList,数组为[]
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
当添加一个元素之后,
elemenData初始化为默认的大小,长度为10
方法addAll的实现
源代码
/**
* 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) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
其它add方法的实现
指定位置添加一个元素
/**
* 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++;
}
/**
* 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;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
在指定位置上添加一个或者多个元素,在add的基础上,需要判断位置添加了指定位置是否在有效的长度之内等判断~
/**
* 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;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
从上述方法可以看出,按照指定位置删除主要包含如下几个步骤:
/**
* Checks if the given index is in range. If not, throws an appropriate
* runtime exception. This method does *not* check if the index is
* negative: It is always used immediately prior to an array access,
* which throws an ArrayIndexOutOfBoundsException if index is negative.
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E oldValue = elementData(index);
int numMoved = size - index - 1;
/**
* 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) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
按照指定对象的移除,在代码中,区分删除的元素是否为null值,然后循环遍历数组,如果元素值和删除的值内容一致,则调用fastRemove方法进行删除,fastRemove方法内容如下:
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
fastRemove的删除方式和remove(index)的思路一致
remove(index)删除元素后返回原先指定位置index的值elementData[index] remove(object)删除元素后返回true或者false,如果有匹配元素,删除返回true,否则返回false
按照范围删除元素removeRange
ArrayList类中还包含了一个protected方法,删除指定范围内的元素。如:
/**
* 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) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
该方法和remove(index)的思路类似,将后面的元素往前拷贝,将后续的元素置为null值,并修改当前元素个数的值
源代码
/**
* 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);
return elementData(index);
}
ArrayList的get方法很简单, 先判断index是否有效,然后直接按照index获取元素elementData[index]即可
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
源代码
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
set的方法包含如下几个步骤:
源代码
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
indexOf区分null值和非null值,非null值,使用eqauls比较~ indexOf从第一个元素(index =0),循环遍历数组,找到匹配值返回元素的所在数组的下标位置,如果没有找到元素则返回-1。
与之对应的是lastIndexOf方法,唯一的区别是从后往前找
/**
* Returns the index of the last occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the highest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
contains方法
源代码
/**
* Returns <tt>true</tt> if this list contains the specified element.
* More formally, returns <tt>true</tt> if and only if this list contains
* at least one element <tt>e</tt> such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this list is to be tested
* @return <tt>true</tt> if this list contains the specified element
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
contains方法,用于判断ArrayList中是否包含指定的元素。
其调用了indexOf方法
clear方法
源代码
/**
* Removes all of the elements from this list. The list will
* be empty after this call returns.
*/
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
clear方法很简单,所有元素置空,并且将size置为0
iterator方法
源代码
/**
* Returns an iterator over the elements in this list in proper sequence.
*
* <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
*
* @return an iterator over the elements in this list in proper sequence
*/
public Iterator<E> iterator() {
return new Itr();
}
ArrayList中iterator方法返回的是一个内部类Itr,其实现了Iterator接口的hasNext, next以及remove方法:
/** * An optimized version of AbstractList.Itr */ private class Itr implements Iterator<E> { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount;
public boolean hasNext() { return cursor != size; }
@SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i]; }
public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification();
try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } }
final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }
源代码
/**
* Returns a list iterator over the elements in this list (in proper
* sequence).
*
* <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
*
* @see #listIterator(int)
*/
public ListIterator<E> listIterator() {
return new ListItr(0);
}
ArrayList中的listIterator方法,也是采用了内部类ListItr, 其继承内部类Itr,并且还实现了ListIterator接口,也就是说,其功能比Iterator更加强大,除了hasNext, next以及remove方法之外,它还具有add、set等方法。
/**
* An optimized version of AbstractList.ListItr
*/
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
... ...
}
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
public class ArrayListExample {
public static void main(String[] args) {
List<String> words = new ArrayList<>();
words.add("Hello");
words.add("Java");
//[Hello, Java]
System.out.println(words);
ListIterator<String> listIter = words.listIterator();
listIter.add("new");
//[new, Hello, Java]
System.out.println(words);
/**
* ListIterator的set方法示例
*/
listIter = words.listIterator();
while(listIter.hasNext()) {
String element = listIter.next();
if("new".equals(element)) {
listIter.set("new-set");
}
}
//[new-set, Hello, Java]
System.out.println(words);
}
}
Iterator vs ListIterator
Iterator接口包含hasNext, next以及remove方法
public interface ListIterator<E> extends Iterator<E> {
}
ListIterator接口继承自Iterator接口,具备更多的方法,如add,set,previous等等
区别
subList方法
源代码
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
subList主要包含两个步骤:
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > size)
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
}
SubList类如下:
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
... ...
}
public class SubListExample {
public static void main(String[] args) {
List<String> words = new ArrayList<>();
words.add("one");
words.add("two");
words.add("three");
words.add("four");
words.add("five");
System.out.println("words==>" + words);
List<String> subList = words.subList(2, 4);
System.out.println("subList==>" + subList);
/**
* 修改subList的值的
*/
subList.set(0, "11111");
System.out.println("subList设值后的words内容");
System.out.println("words==>" + words);
}
}
输出结果
words==>[one, two, three, four, five]
subList==>[three, four]
subList设值后的words内容
words==>[one, two, 11111, four, five]
从上述代码输出结果,可以看出,如果修改返回的SubList的内容,原列表也会变化~
再来看一下subList方法,可以看到new SubList的构造参数中包含了this,也就是原列表对象
toArray
源代码
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
toArray使用Arrays.copyOf以及System.arraycopy来完成
示例
public class ListToArrayExample {
public static void main(String[] args) {
List<String> words = new ArrayList<>();
words.add("Hello");
words.add("Java");
String[] arrayWords = words.toArray(new String[0]);
//[Hello, Java]
System.out.println(Arrays.toString(arrayWords));
}
}
除了上述提到的一些方法之外,ArrayList还包含诸如trimeToSize()方法等,如:
/**
* 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 = Arrays.copyOf(elementData, size);
}
}
这里就不一一列举了。