ArrayList的实现原理浅析
本文简单分析一下JDK1.7的ArrayList源码，看一下其内部的结构以及典型方法的实现
ArrayList内部结构
查看ArrayList的源码，发现其继承自AbstractList，实现了List，RandomAccess，Cloneable以及Serializable接口，如：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.SerializableArrayList包含一个数组对象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;方法add的实现
源代码
/**
* 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
ensureCapacityInternal方法
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;
}addAll的步骤
- 将Collection转换成数组
- 扩大数组容量，新容量为原来的容量size+新添加的元素个数
- 使用System.arraycopy，将新添加的元素复制到指定位置~
- 数组大小size加上新元素的个数，即 size += numNew;
其它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的基础上，需要判断位置添加了指定位置是否在有效的长度之内等判断~
remove方法
按照下标索引删除remove(index)
/**
* 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;
}从上述方法可以看出，按照指定位置删除主要包含如下几个步骤：
- 检查index不大于size
/**
* 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));
}- 修改次数加一（modCount++）
- 获取指定index的元素值，并计算需要移动的元素个数
E oldValue = elementData(index);
int numMoved = size - index - 1;- 将指定index后的所有元素都往前挪动一个位置（使用System.arrayCopy）
- 将最后一个元素置为null值，然后元素个数size减1
按照对象删除remove(object)
/**
* 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值，并修改当前元素个数的值
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);
return elementData(index);
}ArrayList的get方法很简单， 先判断index是否有效，然后直接按照index获取元素elementData[index]即可
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}set方法
源代码
/**
* 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的方法包含如下几个步骤：
- 检查index是否有效
- 获取原来的值elementData(index)
- 更新index位置的元素值（elementData[index] = element;）
- 最后返回旧的元素值
indexOf
源代码
/**
* 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(); } }listIterator方法
源代码
/**
* 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等等
区别
- iterator()方法在set和list接口中都有定义，但是ListIterator（）仅存在于list接口中（或实现类中）；
- ListIterator有add()方法，可以向List中添加对象，而Iterator不能
- ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历，但是ListIterator有hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历。Iterator就不可以。
- ListIterator可以定位当前的索引位置，nextIndex()和previousIndex()可以实现。Iterator没有此功能。
- 都可实现删除对象，但是ListIterator可以实现对象的修改，set()方法可以实现。Iierator仅能遍历，不能修改。
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实例
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);
}
}这里就不一一列举了。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-04-20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录