[学习交流] 【上海校区】java集合系列——List集合之ArrayList介绍（二）

一：List概述
List是 java.util包下面的类，从 java集合系列——java集合概述（一）中可以知道，List继承了Collection 接口！
List本身也是一个接口，它的实现有ArrayList 、LinkedList、Vector和CopyOnWriteArrayList等！
下面总结分析ArrayList核心的概念和实现原理！

二：List的几个实现类ArrayList类分析（我分析的是jdk1.7.0_79版本）
1：ArrayList的简介

ArrayList基于数组实现，是一个动态的数组队列。但是它和Java中的数组又不一样，它的容量可以自动增长，类似于C语言中动态申请内存，动态增长内存！
ArrayList继承了AbstractList，实现了RandomAccess、Cloneable和Serializable接口！
public class ArrayList<E> extends AbstractList<E>
 implements List<E>, RandomAccess, Cloneable, java.io.Serializable
1
2
集成了AbstractList，AbstractList又继承了AbstractCollection实现了List接口，它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能！
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
/**
 * Sole constructor. (For invocation by subclass constructors, typically
 * implicit.)
 */
protected AbstractList() {
}
1
2
3
4
5
6
7
实现了RandomAccess接口，提供了随机访问功能，实际上就是通过下标序号进行快速访问。
实现了Cloneable接口，即覆盖了函数clone()，能被克隆。
实现了Serializable接口，支持序列化，也就意味了ArrayList能够通过序列化传输。
2： ArrayList的继承关系
ArrayLList API

java.lang.Object
java.util.AbstractCollection<E>
 java.util.AbstractList<E>
 java.util.ArrayList<E>

All Implemented Interfaces:
Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>, RandomAccess
Direct Known Subclasses:
AttributeList, RoleList, RoleUnresolvedList
1
2
3
4
5
6
7
8
9

3：ArrayList方法（API）

// Collection中定义的API
boolean add(E object)
boolean addAll(Collection<? extends E> collection)
void clear()
boolean contains(Object object)
boolean containsAll(Collection<?> collection)
boolean equals(Object object)
int hashCode()
boolean isEmpty()
Iterator<E> iterator()
boolean remove(Object object)
boolean removeAll(Collection<?> collection)
boolean retainAll(Collection<?> collection)
int size()
<T> T[] toArray(T[] array)
Object[] toArray()
// AbstractCollection中定义的API
void add(int location, E object)
boolean addAll(int location, Collection<? extends E> collection)
E get(int location)
int indexOf(Object object)
int lastIndexOf(Object object)
ListIterator<E> listIterator(int location)
ListIterator<E> listIterator()
E remove(int location)
E set(int location, E object)
List<E> subList(int start, int end)
// ArrayList新增的API
Object clone()
void ensureCapacity(int minimumCapacity)
void trimToSize()
void removeRange(int fromIndex, int toIndex)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
4：ArrayList的源码分析

public class ArrayList<E> extends AbstractList<E>
 implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
//属性
/**
 * 默认初始容量 = 10
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 用于空实例的共享空数组实例。
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 *存储ArrayList的元素的数组缓冲区。
 * ArrayList的容量是该数组缓冲区的长度。任何
 *空的ArrayList与elementData == EMPTY_ELEMENTDATA将被扩展为
 *添加第一个元素时的DEFAULT_CAPACITY。
 */
private transient Object[] elementData;//注：被transient关键字修饰的变量不再能被序列化，一个静态变量不管是否被transient修饰，均不能被序列化。

/**
 * ArrayList的大小（它包含的元素数量）。
 *
 * @serial
 */
private int size;

//构造函数

/**
 * Constructs an empty list with the specified initial capacity.
 * 构造具有指定初始容量的空列表。
 *
 * @param initialCapacity the initial capacity of the list
 * initialCapacity 列表的初始容量
 * @throws IllegalArgumentException if the specified initial capacity
 * is negative
 * IllegalArgumentException如果指定的初始容量是负数
 */
public ArrayList(int initialCapacity) {
 super();
 if (initialCapacity < 0)
 throw new IllegalArgumentException("Illegal Capacity: "+
 initialCapacity);
 this.elementData = new Object[initialCapacity];
}

/**
 * Constructs an empty list with an initial capacity of ten.
 * 构造一个初始容量为10的空列表。
 */
public ArrayList() {
 super();
 this.elementData = EMPTY_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
 * c 其元素将被放置到此列表中的集合
 * @throws NullPointerException if the specified collection is null
 * 如果指定的集合为null，则为NullPointerException
 */
public ArrayList(Collection<? extends E> c) {
 elementData = c.toArray();
 size = elementData.length;
 // c.toArray might (incorrectly) not return Object[] (see 6260652)
 // c.toArray可能（不正确）不返回Object []（请参阅6260652）
 if (elementData.getClass() != Object[].class)//判断是否返回Object[].class，若没有返回，则使用Arrays.copyOf 进行转换
 elementData = Arrays.copyOf(elementData, size, Object[].class);
}

/**
 * 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.
 *将此<tt> ArrayList </ tt>实例的容量修改为列表的当前大小。
 *应用程序可以使用此操作最小化<tt> ArrayList </ tt>实例的存储。
 */
public void trimToSize() {
 modCount++;//在java.util.AbstractList<E>中定义，用于计算对数组的操作次数
 if (size < elementData.length) {
 elementData = Arrays.copyOf(elementData, size);
 }
}

 /**
 * 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.
 * 如有必要，增加此<tt> ArrayList </ tt>实例的容量，以确保由最小容量参数指定。
 * @param minCapacity the desired minimum capacity
 * minCapacity 所需的最小容量
 */
public void ensureCapacity(int minCapacity) {
 int minExpand = (elementData != EMPTY_ELEMENTDATA)
 // any size if real element table
 ? 0
 // larger than default for empty table. It's already supposed to be at default size.
 // 大于默认值为空表。它应该是默认大小。
 : DEFAULT_CAPACITY;

 if (minCapacity > minExpand) { //minCapacity > minExpand 则设置
 ensureExplicitCapacity(minCapacity);
 }
}
//确保集合内部的容量
 private void ensureCapacityInternal(int minCapacity) {
 if (elementData == EMPTY_ELEMENTDATA) {
 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
 }

 ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
 modCount++;

 // overflow-conscious code
 if (minCapacity - elementData.length > 0)
 grow(minCapacity);
}

 /**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 *一些虚拟机保留数组中的一些标题字。
 *尝试分配较大的数组可能会导致OutOfMemoryError：请求的数组大小超过VM限制
 * 注：怕超过VM限制，所以只用 Integer.MAX_VALUE - 8 设置MAX_ARRAY_SIZE的值！
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * 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
 * minCapacity 所需的最小容量
 */
private void grow(int minCapacity) {
 // overflow-conscious code 溢出-察觉代码
 int oldCapacity = elementData.length; //旧的容量大小
 int newCapacity = oldCapacity + (oldCapacity >> 1); //oldCapacity >> 1 : >> 右移相当于 oldCapacity/2
 if (newCapacity - minCapacity < 0)
 newCapacity = minCapacity;
 if (newCapacity - MAX_ARRAY_SIZE > 0)
 newCapacity = hugeCapacity(minCapacity);//看下面的hugeCapacity()方法，数组的最大容量不会超过MAX_ARRAY_SIZE
 // minCapacity is usually close to size, so this is a win:
 // minCapacity通常接近于大小，所以这是一个win：

 elementData = Arrays.copyOf(elementData, newCapacity);//复制到一个新的数组
}

 private static int hugeCapacity(int minCapacity) {
 if (minCapacity < 0) // overflow
 throw new OutOfMemoryError();
 return (minCapacity > MAX_ARRAY_SIZE) ?
 Integer.MAX_VALUE :
 MAX_ARRAY_SIZE;
}

/**
 * Returns the number of elements in this list.
 * 返回此列表中的元素数。获取集合的大小
 *
 * @return the number of elements in this list
 * 此列表中的元素数
 */
public int size() {
 return size;
}

/**
 * Returns <tt>true</tt> if this list contains no elements.
 * 判断是否为空，如果集合为没有包含任何元素，返回 true ！
 * @return <tt>true</tt> if this list contains no elements
 */
public boolean isEmpty() {
 return size == 0;
}

/**
 *如果此列表包含指定的元素，则返回true。更正式地，
 *当且仅当这个列表包含至少一个元素e使得（o == null？e == *null：o.equals（e））时，
 *返回true。
 * @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;
}

/**
 *返回此列表中指定元素的第一次出现的索引，如果此列表不包含元素，
 *则返回-1。更正式地，返回最低索引i，使得（o == null？get（i）== null：o.equals（get（i））），
 *或-1，如果没有这样的索引。
 *
 *返回：此列表中指定元素的第一次出现的索引，如果此列表不包含元素，则为-1
 */
public int indexOf(Object o) {
 if (o == null) {
 for (int i = 0; i < size; i++)
 if (elementData==null)
 return i;
 } else {
 for (int i = 0; i < size; i++)
 if (o.equals(elementData))
 return i;
 }
 return -1;
}

/**
 * 返回此列表中指定元素的最后一次出现的索引，如果此列表不包含元素，
 *则返回-1。更正式地，返回最高索引i，使得（o == null？get（i）== null：o.equals（get（i））），
 *或-1如果没有这样的索引。
 *
 *返回：此列表中指定元素的最后一次出现的索引，如果此列表不包含元素，则为-1
 */
public int lastIndexOf(Object o) {
 if (o == null) {
 for (int i = size-1; i >= 0; i--)
 if (elementData==null)
 return i;
 } else {
 for (int i = size-1; i >= 0; i--)
 if (o.equals(elementData))
 return i;
 }
 return -1;
}

/**
 * Returns a shallow copy of this <tt>ArrayList</tt> instance. (The
 * elements themselves are not copied.)
 * 返回此<tt> ArrayList </ tt>实例的浅拷贝。（元素本身不被复制。）
 * @return a clone of this <tt>ArrayList</tt> instance
 */
public Object clone() { //实现了Cloneable接口，覆盖了函数clone()，能被克隆。
 try {
 @SuppressWarnings("unchecked")
 ArrayList<E> v = (ArrayList<E>) super.clone();
 v.elementData = Arrays.copyOf(elementData, size);
 v.modCount = 0;
 return v;
 } catch (CloneNotSupportedException e) {
 // this shouldn't happen, since we are Cloneable
 // 这不应该发生，因为我们是克隆的
 throw new InternalError();
 }
}

 /**
 * 以正确的顺序返回包含此列表中所有元素的数组（从第一个元素到最后一个元素）。
 *
 * This method acts as bridge between array-based and collection-based
 * APIs.
 * 此方法充当基于阵列和基于集合的API之间的桥梁
 * @return an array containing all of the elements in this list in
 * proper sequence
 * 一个包含正确顺序的列表中所有元素的数组
 */
public Object[] toArray() {
 return Arrays.copyOf(elementData, size);//使用Arrays工具类
}

/**
 * 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);
}

/**
 * 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;
}

/**
 * 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!! 增加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++;
}

/**
 * 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,

//public static native void arraycopy(Object src, int srcPos,
// Object dest, int destPos,int length);
//调用了本地的方法 : 将指定源数组的数组从指定位置开始复制到目标数组的指定位置。

 elementData[--size] = null; // clear to let GC do its work 设置为 null ，让gc去回收

 return oldValue;
}

/**
 * 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
 * 从列表中删除指定元素的第一次出现（如果存在）。
 *如果列表不包含元素，则不会更改。更正式地，删除具有最低索引i的元素，使得（如果这样的元素存在）
 *（o == null？get（i）== *null：o.equals（get（i）））。 *如果此列表包含指定的元素（或等效地，如果此列表作为调用的结果更改），则返回true。
 *
 * @param o element to be removed from this list, if present
 * @return <tt>true</tt> if this list contained the specified element 如果包含返回 true
 */
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;
}

/*
 * 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
}

/**
 * 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 = null;

 size = 0;
}

 /**
 * 将指定集合中的所有元素以指定集合的Iterator返回的顺序追加到此列表的末尾。 *如果在操作正在进行时修改指定的集合，则此操作的行为是未定义的。 *（这意味着如果指定的集合是此列表，则此调用的行为是未定义的，并且此列表不是空的。）
 * @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;
}
/*
*将指定集合中的所有元素插入到此列表中，从指定位置开始。
*
*/
 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;
}

/**
 * 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).
 *从此列表中删除其索引在fromIndex（包含）和toIndex（排除）之间的所有元素。
 *将任何后续元素向左移（减少其索引）。
 */
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 = null;
 }
 size = newSize;
}

/**
 * 检查给定的索引是否在范围内。如果没有，则抛出一个适当的运行时异常。
 * 私有方法
 */
private void rangeCheck(int index) {
 if (index >= size)
 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
 * A version of rangeCheck used by add and addAll.
 * 由add和addAll使用的rangeCheck的版本。
 * 私有方法
 */
private void rangeCheckForAdd(int index) {
 if (index > size || index < 0)
 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
 * Removes from this list all of its elements that are contained in the
 * specified collection.
 * 从此列表中删除包含在指定集合中的所有元素。
 * @param c collection containing elements to be removed from this list
 * @return {@code true} if this list changed as a result of the call
 * 如果此列表由于调用而更改则返回true
 */
public boolean removeAll(Collection<?> c) {
 return batchRemove(c, false);
}

/**
 * Retains only the elements in this list that are contained in the
 * specified collection. In other words, removes from this list all
 * of its elements that are not contained in the specified collection.
 *仅保留此列表中包含在指定集合中的元素。换句话说，
 *从此列表中删除未包含在指定集合中的所有元素。
 * @param c collection containing elements to be retained in this list
 * @return {@code true} if this list changed as a result of the call
 * 如果此列表由于调用而更改则返回true
 */
public boolean retainAll(Collection<?> c) {
 return batchRemove(c, true);
}
//批量移除
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.
 //保留与AbstractCollection的行为兼容性，即使c.contains（）抛出。
 if (r != size) {
 System.arraycopy(elementData, r,
 elementData, w,
 size - r);
 w += size - r;
 }
 if (w != size) {
 // clear to let GC do its work
 for (int i = w; i < size; i++)
 elementData = null;
 modCount += size - w;
 size = w;
 modified = true;
 }
 }
 return modified;
}

/**
 * 将ArrayList实例的状态保存到流（即，序列化它）。
 */
private void writeObject(java.io.ObjectOutputStream s)
 throws java.io.IOException{
 // Write out element count, and any hidden stuff
 //写出元素数量和任何隐藏的东西
 int expectedModCount = modCount;
 s.defaultWriteObject();

 // Write out size as capacity for behavioural compatibility with clone()
 s.writeInt(size);

 // Write out all elements in the proper order.
 for (int i=0; i<size; i++) {
 s.writeObject(elementData);
 }

 if (modCount != expectedModCount) {
 throw new ConcurrentModificationException();
 }
}
 /**
 * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
 * deserialize it).
 *从流重构 ArrayList 实例（即，反序列化它）。
 */
private void readObject(java.io.ObjectInputStream s)
 throws java.io.IOException, ClassNotFoundException {
 elementData = EMPTY_ELEMENTDATA;

 // Read in size, and any hidden stuff
 //读出元素数量和任何隐藏的东西
 s.defaultReadObject();

 // Read in capacity 读入容量
 s.readInt(); // ignored

 if (size > 0) {
 // be like clone(), allocate array based upon size not capacity
 ensureCapacityInternal(size);

 Object[] a = elementData;
 // Read in all elements in the proper order.
 for (int i=0; i<size; i++) {
 a = s.readObject();
 }
 }
}

 /**
 *对列表中的元素返回一个列表迭代器（以正确的顺序），
 *从列表中指定的位置开始。指定的索引指示由初始调用返回到next的第一个元素。
 *对上一个的初始调用将返回具有指定索引减1的元素。
 *
 *返回的列表迭代器是fail-fast的。
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public ListIterator<E> listIterator(int index) {
 if (index < 0 || index > size)
 throw new IndexOutOfBoundsException("Index: "+index);
 return new ListItr(index);
}

/**
 * Returns a list iterator over the elements in this list (in proper
 * sequence).
 *返回此列表中的元素（按正确顺序）的列表迭代器。
 * The returned list iterator is <a href="#fail-fast">fail-fast</a>.
 *返回的列表迭代器是fail-fast的。
 * @see #listIterator(int)
 */
public ListIterator<E> listIterator() {
 return new ListItr(0);
}

/**
 * Returns an iterator over the elements in this list in proper sequence.
 *以正确的顺序返回此列表中的元素的迭代器。
 * The returned iterator is <a href="#fail-fast">fail-fast</a>.
 *返回的列表迭代器是fail-fast的。
 * @return an iterator over the elements in this list in proper sequence
 */
public Iterator<E> iterator() {
 return new Itr();
}

/**
 * An optimized version of AbstractList.Itr
 * 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();
 }
}

/**
 * An optimized version of AbstractList.ListItr
 * 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;
 }

 @SuppressWarnings("unchecked")
 public E previous() {
 checkForComodification();
 int i = cursor - 1;
 if (i < 0)
 throw new NoSuchElementException();
 Object[] elementData = ArrayList.this.elementData;
 if (i >= elementData.length)
 throw new ConcurrentModificationException();
 cursor = i;
 return (E) elementData[lastRet = i];
 }

 public void set(E e) {
 if (lastRet < 0)
 throw new IllegalStateException();
 checkForComodification();

 try {
 ArrayList.this.set(lastRet, e);
 } catch (IndexOutOfBoundsException ex) {
 throw new ConcurrentModificationException();
 }
 }

 public void add(E e) {
 checkForComodification();

 try {
 int i = cursor;
 ArrayList.this.add(i, e);
 cursor = i + 1;
 lastRet = -1;
 expectedModCount = modCount;
 } catch (IndexOutOfBoundsException ex) {
 throw new ConcurrentModificationException();
 }
 }
}

//subList 以及后面的代码不在做分析，实际情况中很少用到，需要的时候，请自行看源码分析
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
5：总结

ArrayList 本质实现方法是用数组！是非同步的！

初始化容量 = 10 ，最大容量不会超过 MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8！

indexOf和lastIndexOf 查找元素，若元素不存在，则返回-1！

当ArrayList容量不足以容纳全部元素时，ArrayList会重新设置容量：新的容量=“(原始容量x3)/2 ”。

ArrayList的克隆函数，即是将全部元素克隆到一个数组中。

ArrayList实现java.io.Serializable的方式。当写入到输出流时，先写入“容量”，再依次写入“每一个元素”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。

从代码中可以看出，当容量不够时，每次增加元素，都要将原来的元素拷贝到一个新的数组中，非常之耗时，也因此建议在事先能确定元素数量的情况下，才使用ArrayList，否则建议使用LinkedList。

ArrayList的实现中大量地调用了Arrays.copyof()和System.arraycopy()方法。具体分析见第一篇参考文章

ArrayList基于数组实现，可以通过下标索引直接查找到指定位置的元素，因此查找效率高，但每次插入或删除元素，就要大量地移动元素，插入删除元素的效率低。

在查找给定元素索引值等的方法中，源码都将该元素的值分为null和不为null两种情况处理，ArrayList中允许元素为null。
---------------------
【转载】
作者：每天都在变得更好的阿飞
原文：https://blog.csdn.net/u010648555/article/details/57415966

小影姐姐 · 小影姐姐

不二晨 · 不二晨

魔都黑马少年梦 · 魔都黑马少年梦

帐号		自动登录	找回密码
密码			加入黑马

[学习交流] 【上海校区】java集合系列——List集合之ArrayList介绍（二）

3 个回复