集合框架 List篇（1）---ArrayList、LinkedList

List
-----------
1.ArrayList（jdk1.5以前版本中Vector）
2.LinkedList（jdk1.5以前版本中Stack）
3.CopyOnWriteArrayList

------------------------------

ArrayList是数组的实现形式(内部存储结构是一个数组)：

public class ArrayList <E> extends AbstractList<E>  implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

  private transient Object[] elementData;//存储元素的数组

//ArrayList的构造方法

public ArrayList(int initialCapacity) {//initialCapacity表示要创建的数组的容量
         super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        this.elementData = new Object[initialCapacity];//创建initialCapacity长度的数组
    }

    /**
     *默认的构造 容量为10

     */
    public ArrayList() {
       this(10);
    }

    /**
     * 通过传入集合变量的形式初始化创建list的数组

     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
           elementData = Arrays.copyOf(elementData, size, Object[].class);
     }

-----------------------------

//添加新的元素到数组末尾时，如果超过了当前容量，就要对数组进行扩容，扩充为原来大小的1.5倍，

//由于扩容牵涉到整个数组的copy，对性能影响较大，所以如果知道要存放容量的大小，尽量在创建ArrayList时指定

 public void ensureCapacity(int minCapacity) {
 modCount++;
 int oldCapacity = elementData.length;
 if (minCapacity > oldCapacity) {
     Object oldData[] = elementData;
     int newCapacity = (oldCapacity * 3)/2 + 1;
         if (newCapacity < minCapacity)
                   newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
          elementData = Arrays.copyOf(elementData, newCapacity);
 }

}

-----------------------------------

//get方法实现很简单，就是指定到数组的index下标处，效率很高

public E get(int index) {
 RangeCheck(index);

 return (E) elementData[index];
}

------

添加元素后扩容情况的效果图：



//添加元素的方法，注意先调用ensureCapacity，保证有足够的容量（如果不足就扩容，上面有该方法介绍）

//由于add方法添加元素时，可能导致扩容操作，这也影响了其效率

public boolean add(E e) {
  ensureCapacity(size + 1);  

  elementData[size++] = e;
  return true;
}

-----

删除元素的效果图：

//删除元素的remove操作，牵涉到删除位置index后边元素的copy，所以ArrayList的remove操作效率不高

public E remove(int index) {
 RangeCheck(index);

 modCount++;
 E oldValue = (E) elementData[index];

 int numMoved = size - index - 1;//删除位置后边的元素个数
   if (numMoved > 0)//把要删除位置index后边的元素重新copy到数组的index处及以后
     System.arraycopy(elementData, index+1, elementData, index,  numMoved);

   elementData[--size] = null; // 把最后一个位置的元素置空，便于垃圾回收

    return oldValue;
 }

------------------

ensureCapacity

说明：ArrayList就是一个数组实现，适用于，  查找操作较多，而修改操作（add和delete）较少的情况，由于实现较为简单，就不再过多介绍，如果想更详细了解其实现，可以查看其源码。

下面要介绍的LinkedList适用于：查找较少，修改较多的情况（这与LinkedList的链式结构是有关系的）。

-------------------------------

LinkedList是链表结构的实现形式(内部存储结构是一个链表形式)：



存储结构图示

LinkedList的类结构

public class LinkedList <E>    extends AbstractSequentialList<E>    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList的成员变量

private transient Entry<E> header = new Entry<E>(null, null, null);//链表的头结点
 private transient int size = 0;//链表中元素的个数

LinkedList的构造方法

   

/**
     * 构造一个空链表
     */
    public LinkedList() {
        header.next = header.previous = header;
    }

    /**
     * 通过传入一个集合初始化新链表

     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

addAll方法

 public boolean addAll(int index, Collection<? extends E> c) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew==0)
            return false;
        modCount++;

        Entry<E> successor = (index==size ? header : entry(index));//后继结点，如果index==size时，后继结点指向header头结点
        Entry<E> predecessor = successor.previous;//前驱结点
        for (int i=0; i<numNew; i++) {//把集合元素连成一个双向子链表
            Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
            predecessor.next = e;
            predecessor = e;
         }
         successor.previous = predecessor;//“原始的后继结点"的前驱指向新子链表的最后一个结点

         size += numNew;//更新size大小
        return true;
    }

LinkedList的节点存储结构

private static class Entry<E> {//以内部类的形式定义Entry
 E element;//元素值
 Entry<E> next;//后继
 Entry<E> previous;//前驱

 Entry(E element, Entry<E> next, Entry<E> previous) {
     this.element = element;
     this.next = next;
     this.previous = previous;
 }
}

------------------------

LinkedList的get操作

//get操作，调用entry(index)方法，获得位置index位置的Entry对象
public E get(int index) {
    return entry(index).element;
}
//通过index得到指定位置的Entry结点
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)) {//优化了查找操作，如果index<size/2就从头结点向后遍历
       for (int i = 0; i <= index; i++)
          e = e.next;
   } else {//否则，向前遍历
       for (int i = size; i > index; i--)
          e = e.previous;
   }
   return e;
}

LinkedList的add操作

添加新元素到链表的末端，图示如下：

//add操作，把元素添加到链表的未段
public boolean add(E e) {
   addBefore(e, header);
   return true;
}

//把新元素e添加到entry的前面，当entry为header头结点时，相当于添加到链表的末端，如上图所示
private Entry<E> addBefore(E e, Entry<E> entry) {
   Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);//以entry作为后继，以entry的前驱作为前驱
   newEntry.previous.next = newEntry;//更新引用
   newEntry.next.previous = newEntry;
   size++;//元素个数 加1
   modCount++;//修改次数 加1

  return newEntry;
}

----------------------------

LinkedList的delete操作

删除元素E3，图示如下：

//remove操作，先调用entry(index)方法（上面有介绍）获得Entry对象，然后调用remove(entry)
public E remove(int index) {
    return remove(entry(index));
}
//执行删除操作
private E remove(Entry<E> e) {
   if (e == header)
      throw new NoSuchElementException();

   E result = e.element;
   e.previous.next = e.next;//改变e前驱结点的next引用
   e.next.previous = e.previous;//改变e后继结点的previous引用
   e.next = e.previous = null;//把e置空，便于GC回收
   e.element = null;

   size--;//元素个数 减1
   modCount++;//修改次数 加1

  return result;
}

----------

另外，由于LinkedList实现了双向队列Deque接口，所以也具有队列的相关操作，可以当做一个队列使用。