/** * 数组容量检查，不够时则进行扩容 */ public void ensureCapacity( int minCapacity) { modCount++; // 当前数组的长度 int oldCapacity = elementData .length; // 最小需要的容量大于当前数组的长度则进行扩容 if (minCapacity > oldCapacity) { Object oldData[] = elementData; // 新扩容的数组长度为旧容量的1.5倍+1 int newCapacity = (oldCapacity * 3)/2 + 1; // 如果新扩容的数组长度还是比最小需要的容量小，则以最小需要的容量为长度进行扩容 if (newCapacity < minCapacity) newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: // 进行数据拷贝，Arrays.copyOf底层实现是System.arrayCopy() elementData = Arrays.copyOf( elementData, newCapacity); } }
/** * 根据索引位置删除元素 */ public E remove( int index) { // 数组越界检查 RangeCheck(index);
modCount++; // 取出要删除位置的元素，供返回使用 E oldValue = (E) elementData[index]; // 计算数组要复制的数量 int numMoved = size - index - 1; // 数组复制，就是将index之后的元素往前移动一个位置 if (numMoved > 0) System. arraycopy(elementData, index+1, elementData, index, numMoved); // 将数组最后一个元素置空（因为删除了一个元素，然后index后面的元素都向前移动了，所以最后一个就没用了），好让gc尽快回收 // 不要忘了size减一 elementData[--size ] = null; // Let gc do its work
return oldValue; }
/** * 根据元素内容删除，只删除匹配的第一个 */ public boolean remove(Object o) { // 对要删除的元素进行null判断 // 对数据元素进行遍历查找，知道找到第一个要删除的元素，删除后进行返回，如果要删除的元素正好是最后一个那就惨了，时间复杂度可达O(n) 。。。 if (o == null) { for (int index = 0; index < size; index++) // null值要用==比较 if (elementData [index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) // 非null当然是用equals比较了 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++; // 原理和之前的add一样，还是进行数组复制，将index后的元素向前移动一个位置，不细解释了， int numMoved = size - index - 1; if (numMoved > 0) System. arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size ] = null; // Let gc do its work }
/** * 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; }
/** * 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; }
/** * 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; }
/** * 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. * * @return <tt> true</tt> if this list contains no elements */ public boolean isEmpty() { return size == 0; }
/* * @desc ArrayList遍历方式和效率的测试程序。 * * @author skywang */ public class ArrayListRandomAccessTest {
public static void main(String[] args) { List list = new ArrayList(); for (int i=0; i<100000; i++) list.add(i); //isRandomAccessSupported(list); iteratorThroughRandomAccess(list) ; iteratorThroughIterator(list) ; iteratorThroughFor2(list) ;
}
private static void isRandomAccessSupported(List list) { if (list instanceof RandomAccess) { System.out.println("RandomAccess implemented!"); } else { System.out.println("RandomAccess not implemented!"); }
}
public static void iteratorThroughRandomAccess(List list) {
long startTime; long endTime; startTime = System.currentTimeMillis(); for (int i=0; i<list.size(); i++) { list.get(i); } endTime = System.currentTimeMillis(); long interval = endTime - startTime; System.out.println("iteratorThroughRandomAccess：" + interval+" ms"); }
public static void iteratorThroughIterator(List list) {
long startTime; long endTime; startTime = System.currentTimeMillis(); for(Iterator iter = list.iterator(); iter.hasNext(); ) { iter.next(); } endTime = System.currentTimeMillis(); long interval = endTime - startTime; System.out.println("iteratorThroughIterator：" + interval+" ms"); }
public static void iteratorThroughFor2(List list) {
long startTime; long endTime; startTime = System.currentTimeMillis(); for(Object obj:list) ; endTime = System.currentTimeMillis(); long interval = endTime - startTime; System.out.println("iteratorThroughFor2：" + interval+" ms"); } }
运行结果：
1 2 3
iteratorThroughRandomAccess：3 ms iteratorThroughIterator：8 ms iteratorThroughFor2：5 ms
the first element is: 5 Arraylist size=: 4 ArrayList contains 3 is: false next is: 5 next is: 10 next is: 2 next is: 4 str: 5 str: 10 str: 2 str: 4 ArrayList is empty: true
