一：總述：
主要講解3個集合
1.ArrayList:
底層是數組，線程不安全；
2.LinkedList:
底層是連結清單，線程不安全；
3.Vector
底層資料結構是數組。線程安全；
二：ArrayList解析
首先，我們來看一下ArrayList的屬性：
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;//初始化容量值
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};//指定ArrayList的容量為0時，傳回該空數組
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//與上個屬性的差別是：該數組是預設傳回的，而上個屬性是指定容量為0時傳回
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access//第一次儲存元素時，數組将會擴容
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;//ArrayList的實際大小 根據上面我們可以清晰的發現：ArrayList底層其實就是一個數組，ArrayList中有擴容這麼一個概念，正因為它擴容，是以它能夠實作“動态”增長
2.2構造方法
/**
* 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
*/
//指定初始化長度initCapacity
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.
*/
//否則傳回的是：DEFAULTCAPACITY_EMPTY_ELEMENTDATA
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;
}
} 2.3 Add()方法
源碼如下：
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
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++;
} 2.3.1 Add(E e)
步驟：
- 檢查是否需要擴容
- 插入元素
首先，我們來看看這個方法：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
} 該方法很短，我們可以根據方法名就猜到他是幹了什麼：
- 确認list容量，嘗試容量加1，看看有無必要
- 添加元素
接下來我們來看看這個小容量(+1)是否滿足我們的需求：
private void ensureCapacityInternal(int minCapacity) {
//想要得到的最小的容量
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//确定明确的容量
ensureExplicitCapacity(minCapacity);
} private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//如果最小容量比數組長度大，則用用grow擴容
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
} 接下來看grow是如何擴容的
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//擴容1.5倍
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);//擴容完後調用copyOf方法把原數組的值存入新數組
} 再來看是怎麼把原數組的值放入新數組
/**
* Copies the specified array, truncating or padding with nulls (if necessary)
* so the copy has the specified length. For all indices that are
* valid in both the original array and the copy, the two arrays will
* contain identical values. For any indices that are valid in the
* copy but not the original, the copy will contain <tt>null</tt>.
* Such indices will exist if and only if the specified length
* is greater than that of the original array.
* The resulting array is of the class <tt>newType</tt>.
*
* @param <U> the class of the objects in the original array
* @param <T> the class of the objects in the returned array
* @param original the array to be copied
* @param newLength the length of the copy to be returned
* @param newType the class of the copy to be returned
* @return a copy of the original array, truncated or padded with nulls
* to obtain the specified length
* @throws NegativeArraySizeException if <tt>newLength</tt> is negative
* @throws NullPointerException if <tt>original</tt> is null
* @throws ArrayStoreException if an element copied from
* <tt>original</tt> is not of a runtime type that can be stored in
* an array of class <tt>newType</tt>
* @since 1.6
*/
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
} 到目前為止，我們就可以知道
add(E e)
的基本實作了：
- 首先去檢查一下數組的容量是否足夠
- 足夠：直接添加
- 不足夠：擴容
- 擴容到原來的1.5倍
- 第一次擴容後，如果容量還是小于minCapacity，就将容量擴充為minCapacity。
2.3.2：add(int index, E element)
步驟：
- 檢查角标
- 空間檢查，如果有需要進行擴容
- 插入元素
我們來看看插入的實作：
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);//檢查是否越界
ensureCapacityInternal(size + 1); // Increments modCount!!//擴容
System.arraycopy(elementData, index, elementData, index + 1,
size - index);//調用arraycopy進行插入
elementData[index] = element;
size++;
} 注：arraycopy是用c++來編寫的
2.4：get()
- 檢查角标
- 傳回元素
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
} // 檢查角标
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 傳回元素
E elementData(int index) {
return (E) elementData[index];
} 2.5:set()方法
步驟：
- 檢查角标
- 替代元素
- 傳回舊值
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
rangeCheck(index);
//将值進行替代，傳回舊值
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
} 2.6:remove()方法
步驟：
- 檢查角标
- 删除元素
- 計算出需要移動的個數，并移動
- 設定為null，讓Gc回收
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
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;
} 2.7:總述
- ArrayList是基于動态數組實作的，在增删時候，需要數組的拷貝複制（使用的是System.arrayCopy()效率最高的數組拷貝方法）。
- ArrayList的預設初始化容量是10，每次擴容時候增加原先容量的一半，也就是變為原來的1.5倍
- 删除元素時不會減少容量，若希望減少容量則調用trimToSize()
- 它不是線程安全的。它能存放null值。
三：Vector與ArrayList的差別
1.Vector底層也是數組，與ArrayList最大的差別就是：同步(線程安全),Vector的每個方法都是同步的 （相對效率較低）
2.在要求非同步的情況下，我們一般都是使用ArrayList來替代Vector的了,如果想要ArrayList實作同步，可以使用Collections的方法：
List list =Collections.synchronizedList(new ArrayList(...));
，就可以實作同步了
3.ArrayList是以1.5倍擴容，Vector是以2倍擴容
以上的結論可以在源碼中得到驗證
四：LinkedList解析
此處放一張全家桶
LinkedList底層是雙向連結清單
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
} 4.1：構造方法
/**
* Constructs an empty list.
*/
public LinkedList() {
}
/**
* 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 LinkedList(Collection<? extends E> c) {
this();
addAll(c);
} 4.2： add()方法
public boolean add(E e) {
linkLast(e);
return true;
}
//往連結清單的最後添加元素
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
} 4.3：remove()方法
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If this list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns {@code true} if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return {@code true} if this list contained the specified element
*/
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
//删除元素
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
//判斷元素是否存在裡面
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
} /**
* Unlinks non-null node x.
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
} 4.4：get()方法
public E get(int index) {
checkElementIndex(index);
return node(index).item;
} node（）方法
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
//下标小于長度的一半，從頭部開始周遊
if (index < (size >> 1)) {
Node<E> x = first;
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;
}
} 4.5:set方法
set方法和get方法其實差不多，根據下标來判斷是從頭周遊還是從尾周遊
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
} 具體請參考源碼
五：總結
ArrayList：
- 底層實作是數組
- ArrayList的預設初始化容量是10，每次擴容時候增加原先容量的一半，也就是變為原來的1.5倍
- 在增删時候，需要數組的拷貝複制(C++實作)
LinkedList：
- 底層實作是雙向連結清單[雙向連結清單友善實作往前周遊]
Vector：
- 底層是數組，現在已少用，被ArrayList替代，原因有兩個：
- Vector所有方法都是同步，有性能損失。
- Vector初始length是10 超過length時 以100%比率增長，相比于ArrayList更多消耗記憶體。
總的來說：查詢多用ArrayList，增删多用LinkedList。
ArrayList增删慢不是絕對的(在數量大的情況下，已測試)：
- 如果增加元素一直是使用
add()
- 一直删除末尾的元素也是ArrayList要快【不用複制移動位置】
- 至于如果删除的是中間的位置的話，還是ArrayList要快！
但一般來說：增删多還是用LinkedList，因為上面的情況是極端的~