Java集合工具类之List - ArrayList & LinkedList
?
3.2 ArrayList与Vector一样，ArrayList的基本数据结构也是一个可变（动态）数组，数组的元素可以是任意对象。
ArrayList的构造器有两种：
public ArrayList()
默认构造器的数组的长度是10
public ArrayList(int initialCapacity)
指定ArrayList的初始化大小很重要，ArrayList当添加元素的数量大于初始化（或上一次）数组的大小时，数组自动扩容成oldSize*3/2+1,新数组的元素是从老的数组copy而来的。
?
1) ArrayList使用时，最好能够预期需要存放元素的个数，这样可以避免数组长度频繁的改变而引起数据的copy带来的开销，同时会引起内存大小的增加。
2）使用ArrayList需要知道ArrayList是非线程安全的。因此，在使用时，最好是考虑这个对象会不会因为多个线程访问该ArrayList对象，如果确认多个线程访问，则可以用Vector或者CopyOnWriteArrayList来代替ArrayList。
?
?
?
3.3 LinkedListLinkedList的基本数据结构是双向循环链表。链表的优点是插入和删除快，而查找或者修改比较慢。因为插入操作不会像ArrayList那样基于数组的数据结构，当插入时，超过原数组尺寸时，会将原数组的尺寸变成原来的3*size/2+1,然后将原来数组的元素拷贝到新数组中，基于链表的操作只需将目标元素的尾部链接到原来链表的尾部就可以了。删除机制是同样的，基于数组的ArrayList，要删除元素，需要将该元素后面所有的元素向前move一位。
?
构造器：
private transient Entry<E> header = new Entry<E>(null, null, null);
?
//初始花一个空的header链表，并将首尾相连成一个双向循环链表
public LinkedList() {
??????? header.next = header.previous = header;
}
/**
* 核心方法之一：获取index位置的链表信息。此方法在get，remove，add，set都会用到
* 此处用到了二分查找来提高效率，如果index
*是在链表的前半段，则从头开始遍历，如果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;
}
?
/**
* 核心方法之一：将新的e元素，add在指定entry的前面
?*/
private Entry<E> addBefore(E e, Entry<E> entry) {
??? Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
??? newEntry.previous.next = newEntry;
??? newEntry.next.previous = newEntry;
??? size++;
??? modCount++;
??? return newEntry;
}
/**
* 将指定元素放在header之前，实际上就是放在链表的尾部
?*/
public boolean add(Ee) {
??? addBefore(e, header);
??????? return true;
}
/**
* 找到指定位置的元素，并将指定元素放在查找处的前面
?*/
?
public void add(int index, E element){
??????? addBefore(element, (index==size ? header : entry(index)));
}
?
LinkedList的双向性，可以轻松做一个Stack和Queue：
public class LinkedListQueue<E> extendsLinkedList<E>{
???
??? //Like poll/remove
??? public E dequeue(){
?????? return this.removeFirst();
??? }
???
??? //Like offer/add
??? public void enqueue(E e){
?????? this.add(e);
??? }
???
??? //Like peek
??? public E getHeader(){
?????? return this.getFirst();
??? }
???
??? public boolean empty(){
?????? return this.size()==0;
??? }
}
