文章目錄
-
- 1：List接口常用實作類的對比
- 2：ArrayList源碼分析
-
- 2.1：Jdk7下源碼分析：
- 2.2：JDK8下源碼分析：
- 3：LinkedList源碼分析
- 4：Vector源碼分析
- 5：List接口中的常用方法
1：List接口常用實作類的對比
1.1：
ArrayList：作為List接口的主要實作類;線程不安全，效率高；底層使用Object[ ] elementData 存儲。
LinkedList：對于頻繁的插入、删除操作，使用此效率比ArrayList高；因為其底層使用雙向連結清單存儲。
Vector：作為List接口的古老實作類；線程安全的，效率低；底層使用Object[ ] elementData 存儲。
1.2：ArrayList、LinkedList、Vector三者的相同點：
以上三個類都實作了List接口，并且存儲有序的，可重複的資料。
2：ArrayList源碼分析
2.1：Jdk7下源碼分析：
1）數組初始化機制
public ArrayList() {
this(initialCapacity:10); //調用本類的重寫構造
}
public ArrayList(int initialCapacity) {
super();
//如果輸入初始容量小于0，抛出異常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
//建立一個大小為initialCapacity的數組，也就是長度為的數組
this.elementData = new Object[initialCapacity];
}
2）add方法底層源碼
public boolean add(E e) {
//調用ensureCapacityInternal()方法
ensureCapacityInternal(size + 1);
//将元素e指派給elementData[size] 然後size++
elementData[size++] = e;
return true;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//快速失敗機制
//如果目前插入後的容量比數組長度大，調用grow方法進行擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//grow()方法進行擴容
private void grow(int minCapacity) {
//儲存老的數組容量
int oldCapacity = elementData.length;
//新的數組容量 1.5倍擴容
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果是空數組的情況
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//檢測數組是否超過最大容量
if (newCapacity - MAX_ARRAY_SIZE > 0)//MAX_ARRAY_SIZE這個值不是整形的最大值，而是數組的最大容量。
newCapacity = hugeCapacity(minCapacity);//把最大值賦給newCapacity
//數組擴容
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
//異常處理
if (minCapacity < 0)
throw new OutOfMemoryError();
//如果數組容量超過最大數組容量，傳回整型的最大值，否則傳回最大數組容量
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
建議開發中使用帶有參數的構造器：List list = new ArrayList(50);
2.2：JDK8下源碼分析：
與JDK7下的源碼進行對比，JDK下的變化：
ArrayList lise = new ArrayList(); //底層Object[ ] elementData初始化為{}，并沒有建立長度為10的數組。list.add(123) 而當第一次調用add()時，底層才建立了長度為10的數組，并将資料123 添加到elementData[ ]中。
後續的添加和擴容操作與JDK7無異。都是使用 grow() 方法進行擴容。
3：LinkedList源碼分析
LinkedList list = new LinkedList()：内部聲明了Node類型的first和lst屬性，預設值為null，list.add(123) //将123封裝到Node中，建立了Node對象。其中，Node定義為：
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;
}
}
雙向連結清單添加元素具體操作（尾插）
void linkLast(E e){
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, next:null );
last = newNode;
if(l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
4：Vector源碼分析
在Vector中，JDK7和JDK8中通過Vector()構造器建立對象時，底層建立了一個長度為10的數組，在擴容方面，差別于ArrayList，預設擴容為原來的數組長度的2倍。
private void grow(int minCapacity) {
//原Vector容量值
int oldCapacity = elementData.length;
//如果有給capacityIncrement設定增長系數的話，就加上該系數值來擴容，否則将原先的數組容量變為2*oldCapacity
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
//如果重新的設定的容量值還要小于最小要求的容量值得話
if (newCapacity - minCapacity < 0)
//就将最小的容量值指派給新的容量
newCapacity = minCapacity;
//如果誰知道的新容量值比限制的最大容量還要大的話
if (newCapacity - MAX_ARRAY_SIZE > 0)
//重新設定大小
newCapacity = hugeCapacity(minCapacity);
//将原先數組的元素淺拷貝到一個新的數組
elementData = Arrays.copyOf(elementData, newCapacity);
}
5：List接口中的常用方法
1)void add(int index, Object ele):在index位置插入ele元素
2)boolean addAll(int index, Collection eles):從index位置開始将eles中的所有元素添加進來
3)Object get(int index):擷取指定index位置的元素
4)int indexOf(Object obj):傳回obj在集合中首次出現的位置 ，如果沒有就傳回-1
5)int lastIndexOf(Object obj):傳回obj在目前集合中末次出現的位置 ，如果沒有就傳回-1
6)Object remove(int index):移除指定index位置的元素，并傳回此元素
相當于一個隊列，因為remove()某個元素後，此元素後邊的所有元素都會向前移動
注意：Collection中的remove是删除某個元素，這裡是方法的重載而不是方法的重寫 ，因為方法名一樣，但形參類型不一樣，在List中也可以按照對象去删除
7)Object set(int index, Object ele):設定指定index位置的元素為ele
8)List subList(int fromIndex, int toIndex):傳回從[fromIndex到toIndex )位置的子集合，本身的list沒有變化
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)