java 集合类-ArrayList

Java集合类
一 List接口
常用的实现类 ArrayList和 LinkedList。
1）ArrayList: 底层实现的方法时： 动态数组 。
ArrayList、LinkedList比较：
1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
2.对于随机访问，ArrayList觉得优于LinkedList。LinkedList需要不断移动指针引用。
3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。

先看 ArrayList
看源码：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer.
     */
    private transient E[] elementData;

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

ArrayList继承了AbstractList抽象类，实现List 等接口。
elementData:用来存储add方法等添加的数据数组。
size：数组中有效数据的个数。

ArrayList构造方法：

   // 由调用者指定集合初始容量，即是elementData数组长度
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = (E[])new Object[initialCapacity];
    }

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    //默认则为 10
    public ArrayList() {
       this(10);
    }

下面是ArrayList的add源码：

 //添加数据
    public boolean add(E o) {
         //确保有足够的容量能存放添加的数据
         ensureCapacity(size + 1);  // Increments modCount!!
         //把数据放入数组中，size+1；
         elementData[size++] = o;
         return true;
    }

    public void ensureCapacity(int minCapacity) {
         modCount++;
         int oldCapacity = elementData.length;
         //当集合需要的最小容量不够时，即minCapacity > oldCapacity时；
          //集合中数组长度扩展为1.5倍+1；
           if (minCapacity > oldCapacity) {
             Object oldData[] = elementData;
             int newCapacity = (oldCapacity * 3)/2 + 1;
    	    if (newCapacity < minCapacity)
             newCapacity = minCapacity;
             //扩展生成新的数组 elementData 
             elementData = (E[])new Object[newCapacity];
             //将原先的oldData 数组数据 copy至 elementData 
             System.arraycopy(oldData, 0, elementData, 0, size);
          }
    }

下面是ArrayList的删除源码：

 
    public E remove(int index) {
        //检查集合中是否存在该索引
        RangeCheck(index);
        modCount++;
        E oldValue = elementData[index];
        int numMoved = size - index - 1;
        if (numMoved > 0)
        //对index索引后面的数据分别向前移动一位。
        System.arraycopy(elementData, index+1, elementData, index,
			     numMoved);
        elementData[--size] = null; // Let gc do its work

        return oldValue;
    }

LinkedList 删除方法：

    

    public E remove(int index) {
        return remove(entry(index));
    }
    //删除方法，只需要将删除元素左右两边的引用关联上即可。
    private Entry<E> entry(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+size);
        Entry<E> e = header;
        if (index < (size >> 1)) {
            for (int i = 0; i <= index; i++)
                e = e.next;
        } else {
            for (int i = size; i > index; i--)
                e = e.previous;
        }
        return e;
    }

    private E remove(Entry<E> e) {
	if (e == header)
	    throw new NoSuchElementException();

        E result = e.element;
        //关联删除节点左右两边的节点。
         //如上图：若第一个节点被删除，则将header与第二个节点关联上。形成新链表。
        e.previous.next = e.next;
        e.next.previous = e.previous;
        e.next = e.previous = null;
        e.element = null;
        size--;
        modCount++;
        return result;
    }