Java集合框架：ArrayList

ArrayList定义

package java.util; public class ArrayList<E> extends AbstractList<E>         implements List<E>, RandomAccess, Cloneable, java.io.Serializable{     private static final int DEFAULT_CAPACITY = 10;     private static final Object[] EMPTY_ELEMENTDATA = {};     private transient Object[] elementData;     private int size; //其余省略 }

ArrayList概述

ArrayList以数组实现，允许重复。超出限制时会增加50%的容量（grow()方法中实现，如下所示），每次扩容都底层采用System.arrayCopy()复制到新的数组，因此最好能给出数组大小的预估值。默认第一次插入元素时创建数组的大小为10.

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

按数组下标访问元素—get(i)/set(i,e) 的性能很高，这是数组的基本优势。

public E get(int index) {         rangeCheck(index);          return elementData(index);     }     public E set(int index, E element) {         rangeCheck(index);          E oldValue = elementData(index);         elementData[index] = element;         return oldValue;     }

直接在数组末尾加入元素—add(e)的性能也高，但如果按下标插入、删除元素—add(i,e), remove(i), remove(e)，则要用System.arraycopy()来移动部分受影响的元素，性能就变差了，这是基本劣势。

public boolean add(E e) {         ensureCapacityInternal(size + 1);  // Increments modCount!!         elementData[size++] = e;         return true;     }     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++;     }     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;     }     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;     }

ArrayList中有一个方法trimToSize()用来缩小elementData数组的大小，这样可以节约内存：

public void trimToSize() {         modCount++;         if (size < elementData.length) {             elementData = Arrays.copyOf(elementData, size);         }     }

ArrayList的使用

举个简单一点的例子：

List<Integer> list = new ArrayList<>();         list.add(4);         list.add(2);         list.add(3);         list.add(5);         for(int i:list)         {             System.out.println(i);         }         System.out.println(list);

运行结果：

4 2 3 5 [4, 2, 3, 5]

可以发现 ArrayList是按插入顺序存储的 ，这也不奇怪，每次插入是在elementData[size++]处插入。

subList的使用

List<Integer> list = new ArrayList<>();         list.add(4);         list.add(2);         list.add(3);         list.add(5);         list.add(7);         list.add(5);         list.add(11);         list.add(14);         list.add(10);         list.add(9);         System.out.println(list);         List<Integer> list2 = list.subList(3, 6);         System.out.println(list2);         list2.set(2, 50);          System.out.println("============");         System.out.println(list);         System.out.println(list2);

运行结果：

[4, 2, 3, 5, 7, 5, 11, 14, 10, 9] [5, 7, 5] ============ [4, 2, 3, 5, 7, 50, 11, 14, 10, 9] [5, 7, 50]

调用ArrayList中的subList方法生成的新的list，内部引用的还是原来的数组elementData，如果改变subList中的值，主list中的值也会跟着改变。

RandomAccess？！

It is recognized that the distinction between random and sequential access is often fuzzy. For example, some List implementations provide asymptotically linear access times if they get huge, but constant access times in practice. Such a List implementation should generally implement this interface. As a rule of thumb, a List implementation should implement this interface if, for typical instances of the class, this loop:      for (int i=0, n=list.size(); i < n; i++)          list.get(i);  runs faster than this loop:      for (Iterator i=list.iterator(); i.hasNext(); )          i.next();

int length = list.size();         for(int i=0;i<length;i++)         {             System.out.println(list.get(i));         }

其实也可以加个判断，让程序通用起来：

if (list instanceof RandomAccess)         {             for (int i = 0; i < list.size(); i++)             {             }         }         else         {             Iterator<?> iterator = list.iterator();             while (iterator.hasNext())             {                 iterator.next();             }         }

因此，博主个人觉得JDK（jdk7）中有这么一段不妥之处（希望大神不要喷我）：ArrayList的toString()方法是在AbstractCollection中实现的：

public String toString() {         Iterator<E> it = iterator();         if (! it.hasNext())             return "[]";          StringBuilder sb = new StringBuilder();         sb.append('[');         for (;;) {             E e = it.next();             sb.append(e == this ? "(this Collection)" : e);             if (! it.hasNext())                 return sb.append(']').toString();             sb.append(',').append(' ');         }     }

这里没有判断RandomAccess，直接采用的是迭代器的遍历，影响了一些性能。

ArrayList和LinkedList的区别

1. ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
2. 对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
3. 对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。

ArrayList和Vector的区别

1. Vector和ArrayList几乎是完全相同的,唯一的区别在于Vector是同步类(synchronized)，属于强同步类。因此开销就比ArrayList要大，访问要慢。正常情况下,大多数的Java程序员使用ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。
2. Vector每次扩容请求其大小的2倍空间，而ArrayList是1.5倍。
3. Vector还有一个子类Stack.