ArrayList
ArrayList是一種變長集合，基于定長數(shù)組實現(xiàn)，允許空值和重復(fù)元素，是線程不安全的集合。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
構(gòu)造函數(shù)
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
查找 get()
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
ArrayList的查找比較簡單，因為是數(shù)組，所以時間復(fù)雜度是O（1）的。
插入 add()
插入提供了兩個API分別是插入元素序列的隊尾，另一個是插入指定位置
/** 在元素序列尾部插入 */
public boolean add(E e) {
// 1. 檢測是否需要擴容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 2. 將新元素插入序列尾部
elementData[size++] = e;
return true;
}
/** 在元素序列 index 位置處插入 */
public void add(int index, E element) {
rangeCheckForAdd(index);
// 1. 檢測是否需要擴容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 2. 將 index 及其之后的所有元素都向后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 3. 將新元素插入至 index 處
elementData[index] = element;
size++;
}
在插入隊尾的時候：
- 是否需要擴容
- 插入隊尾
如果是插入指定位置，則
- 判斷容量是否足夠
- 把需要插入位置后面的元素向后移動一位
- 將新元素插入
判斷擴容以及擴容邏輯
/** 計算最小容量 */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
/** 擴容的入口方法 */
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/** 擴容的核心方法 */
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// newCapacity = oldCapacity + oldCapacity / 2 = oldCapacity * 1.5
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 擴容
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// 如果最小容量超過 MAX_ARRAY_SIZE，則將數(shù)組容量擴容至 Integer.MAX_VALUE
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
可以看出，當(dāng)需要擴容的時候則按照原先數(shù)組的1.5倍進(jìn)行擴容（ oldCapacity + (oldCapacity >> 1)）
刪除元素
/** 刪除指定位置的元素 */
public E remove(int index) {
rangeCheck(index);
modCount++;
// 返回被刪除的元素值
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
// 將 index + 1 及之后的元素向前移動一位，覆蓋被刪除值
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 將最后一個元素置空，并將 size 值減1
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
E elementData(int index) {
return (E) elementData[index];
}
/** 刪除指定元素，若元素重復(fù)，則只刪除下標(biāo)最小的元素 */
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
// 遍歷數(shù)組，查找要刪除元素的位置
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
/** 快速刪除，不做邊界檢查，也不返回刪除的元素值 */
private void fastRemove(int index) {
modCount++;
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
}
- 獲取指定位置 index 處的元素值
- 將 index + 1 及之后的元素向前移動一位
- 將最后一個元素置空，并將 size 值減 1
- 返回被刪除值，完成刪除操作
當(dāng)添加大量元素后，緊接著刪除了大量元素后，Arraylist并沒有對于多余的數(shù)組長度進(jìn)行縮減，但是對外暴露了api進(jìn)行釋放多余空間，提高空間的利用率
/** 將數(shù)組容量縮小至元素數(shù)量 */
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
最后，在遍歷過程中刪除添加元素，有可能導(dǎo)致意料之外的結(jié)果，所以應(yīng)該使用迭代器方法進(jìn)行刪除添加，這點有很多方法和介紹可以在網(wǎng)絡(luò)上找到答案
LinkedList
LinkedList相對于ArrayList繼承關(guān)系就復(fù)雜的多
LinkedList
LinkedList繼承自AbstractSequentialList,AbstractSequentialList提供了一套用于順序訪問的接口，通過繼承此類，僅需要實現(xiàn)部分代碼就可以擁有完整的一套訪問某種序列表（鏈表）的接口
public E get(int index) {
try {
return listIterator(index).next();
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
public void add(int index, E element) {
try {
listIterator(index).add(element);
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
// 留給子類實現(xiàn)
public abstract ListIterator<E> listIterator(int index);
所以只要繼承類實現(xiàn)了 listIterator 方法，它不需要再額外實現(xiàn)什么即可使用。對于隨機訪問集合類一般建議繼承 AbstractList 而不是 AbstractSequentialList。LinkedList 和其父類一樣，也是基于順序訪問。所以 LinkedList 繼承了 AbstractSequentialList，但 LinkedList 并沒有直接使用父類的方法，而是重新實現(xiàn)了一套的方法。
另外，LinkedList 還實現(xiàn)了 Deque (double ended queue)，Deque 又繼承自 Queue 接口。這樣 LinkedList 就具備了隊列的功能。比如，我們可以這樣使用：
Queue<T> queue = new LinkedList<>();
除此之外我們還可以實現(xiàn)一些其他的數(shù)據(jù)結(jié)構(gòu)，比如棧
查找 get()
LinkedList基于鏈表，所以查找的時間復(fù)雜度為O(N).
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
/*
* 則從頭節(jié)點開始查找，否則從尾節(jié)點查找
* 查找位置 index 如果小于節(jié)點數(shù)量的一半，
*/
if (index < (size >> 1)) {
Node<E> x = first;
// 循環(huán)向后查找，直至 i == index
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
可以看到，鏈表的查找顯示判斷index處于的位置，如果處于前半部分則查找前半部分，如果是處于后半部分，則從后半部分開始查找。由于隨機訪問的效率很低，應(yīng)該避免使用LinkedLsit來進(jìn)行大數(shù)據(jù)量下的隨機訪問。
插入
/** 在鏈表尾部插入元素 */
public boolean add(E e) {
linkLast(e);
return true;
}
/** 在鏈表指定位置插入元素 */
public void add(int index, E element) {
checkPositionIndex(index);
// 判斷 index 是不是鏈表尾部位置，如果是，直接將元素節(jié)點插入鏈表尾部即可
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
/** 將元素節(jié)點插入到鏈表尾部 */
void linkLast(E e) {
final Node<E> l = last;
// 創(chuàng)建節(jié)點，并指定節(jié)點前驅(qū)為鏈表尾節(jié)點 last，后繼引用為空
final Node<E> newNode = new Node<>(l, e, null);
// 將 last 引用指向新節(jié)點
last = newNode;
// 判斷尾節(jié)點是否為空，為空表示當(dāng)前鏈表還沒有節(jié)點
if (l == null)
first = newNode;
else
l.next = newNode; // 讓原尾節(jié)點后繼引用 next 指向新的尾節(jié)點
size++;
modCount++;
}
/** 將元素節(jié)點插入到 succ 之前的位置 */
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
// 1. 初始化節(jié)點，并指明前驅(qū)和后繼節(jié)點
final Node<E> newNode = new Node<>(pred, e, succ);
// 2. 將 succ 節(jié)點前驅(qū)引用 prev 指向新節(jié)點
succ.prev = newNode;
// 判斷尾節(jié)點是否為空，為空表示當(dāng)前鏈表還沒有節(jié)點
if (pred == null)
first = newNode;
else
pred.next = newNode; // 3. succ 節(jié)點前驅(qū)的后繼引用指向新節(jié)點
size++;
modCount++;
}
LinkedList的插入操作實際就是鏈表的插入操作，我們知道往鏈表中插入一個數(shù)據(jù)的話，需要斷開鏈然后使前一個節(jié)點連接到新節(jié)點，然后用新節(jié)點連接后一個節(jié)點，這樣就成功插入，刪除的原理類似。同樣將節(jié)點處的連接斷開再連接前后節(jié)點就實現(xiàn)了刪除操作
