Collection、List接口
1、繼承結(jié)構(gòu)
2、方法
Collection實現(xiàn)類
1、繼承結(jié)構(gòu)
類圖：
2、相關類
（1）AbstractCollection
Collection接口的骨架式實現(xiàn)類，最小化實現(xiàn)Collection接口的代價。
（2）AbstractList
List接口的骨架式實現(xiàn)類，最小化實現(xiàn)List接口的代價。**“隨機訪問”**數(shù)據(jù)存儲。
提供了iterator()、listIterator()方法的實現(xiàn)。
重要屬性：
protected transient int modCount;【修改次數(shù)，迭代器和列表迭代器使用】
如果該字段的值發(fā)生意外變化，迭代器(或列表迭代器)將拋出ConcurrentModificationException，以響應next、remove、previous、set、add操作。這提供了快速故障行為，而不是在迭代期間面對并發(fā)修改時的不確定性行為。
AbstractSequentialList（子類）
List接口的框架實現(xiàn)，**“順序訪問”**數(shù)據(jù)存儲。
其它接口
RandomAccess【java.util】
List實現(xiàn)使用的標記接口，表明它們支持快速隨機訪問(通常是常量時間)。
該接口的主要目的是允許泛型算法改變其行為，以便在應用于隨機或順序訪問列表時提供良好的性能。
操作隨機訪問列表(如ArrayList)的最佳算法在應用于順序訪問列表(如LinkedList)時可以產(chǎn)生二次行為。鼓勵泛型列表算法在應用算法之前檢查給定列表是否是該接口的實例。
Cloneable【java.lang】
標記接口。
一個類實現(xiàn)了Cloneable接口，表明調(diào)用Object.clone()方法對該類的實例進行逐個字段的復制是合法的。在沒有實現(xiàn)Cloneable接口的實例上調(diào)用Object的clone方法將導致拋出CloneNotSupportedException異常。
按照約定，實現(xiàn)這個接口的類應該重寫Object.clone()方法，表明是public，而Object.clone()方法是protected。
這個接口不包含clone方法。因此，不可能僅僅因為對象實現(xiàn)了這個接口就克隆它。即使以反射方式調(diào)用clone方法，也不能保證它一定會成功。
Serializable【java.io】
標記接口。Serializable接口沒有方法或字段，僅用于標識可序列化的語義。
具體實現(xiàn)類
1、Vector
- 可增長的對象數(shù)組，使用索引訪問：
capacity、capacityIncremnt
Stack
繼承自Vector類，擴展Vector類實現(xiàn)LIFO功能：
- push、pop
- peek
- search
- empty
LIFO功能：
2、ArrayList
List接口的可調(diào)整數(shù)組實現(xiàn)。
不同步：
- Collections.synchronizedList(new ArrayList(…));
實現(xiàn)所有可選列表操作，并允許所有元素，包括null。除了實現(xiàn)List接口之外，這個類還提供了一些方法來操作內(nèi)部用于存儲列表的數(shù)組的大小。(大致相當于Vector，但不同步。)
-
Cloneable：Object.clone()
-
Iterable：forEach(Consumer<? super E> action)
-
Collection：removeIf(Predicate<? super E> filter)
-
AbstractList：removeRange(int fromIndex, int toIndex)
-
增加方法：
- ensureCapacity(int minCapacity)
-
trimToSize()
時間復雜度：
-
size、isEmpty、get、set、iterator和listIterator操作在常量時間內(nèi)運行。
-
add在平攤常數(shù)時間內(nèi)運行，即添加n個元素需要O(n)時間。
-
所有其他操作都在線性時間內(nèi)運行(粗略地說)。
與LinkedList實現(xiàn)相比，常數(shù)因子較低。
每個ArrayList實例都有一個capacity，用于存儲列表中元素的數(shù)組的大小。它總是至少和列表大小一樣大。當元素被添加到ArrayList中時，它的容量會自動增長。
在添加大量元素之前使用ensureCapacity操作來增加ArrayList實例的容量。這可能會減少增量再分配的數(shù)量。
分析源碼：
（1）構(gòu)造函數(shù)
//存儲數(shù)據(jù)：Object數(shù)組elementData
//構(gòu)造函數(shù)（空參）：賦值空數(shù)組
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/*構(gòu)造函數(shù)（含參：容器大?。? 判斷initialCapacity > 0：創(chuàng)建對應大小的一個Object數(shù)組；
= 0 ：賦值一個空數(shù)組
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 空數(shù)組
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
}
}
/*構(gòu)造函數(shù)（使用集合Collection的子類對象）
*/
public ArrayList(Collection<? extends E> c) {
//將參數(shù)轉(zhuǎn)換成數(shù)組
Object[] a = c.toArray();
//數(shù)組長度不為0
//參數(shù)類型判斷：ArrayList直接賦值；Arrays.copyOf()方法拷貝
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
//轉(zhuǎn)換的數(shù)組長度為0：賦值空數(shù)組
elementData = EMPTY_ELEMENTDATA;
}
}
（2）數(shù)組大小擴展
// 減少不必要的空間消耗
public void trimToSize() {
//處理數(shù)++
modCount++;
//容器中元素個數(shù) VS 存儲數(shù)據(jù)數(shù)組長度
if (size < elementData.length) {
//容器空 ? 空數(shù)組 : Arrays.copyOf()
elementData = (size == 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);
}
}
public void ensureCapacity(int minCapacity) {
//minCapacity>底層數(shù)組長度【需要擴容】
//!(底層數(shù)組不空 && minCapacity<=10)【底層數(shù)組空：第一次】
if (minCapacity > elementData.length&& !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA && minCapacity <= DEFAULT_CAPACITY)) {
//操作數(shù)++
modCount++;
//增加
grow(minCapacity);
}
}
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
private Object[] grow() {
return grow(size + 1);
}
（3）代碼
ArrayList<String> al = new ArrayList<>();
al.add("hello");
構(gòu)造函數(shù)：創(chuàng)建一個空數(shù)組
add()方法：【底層：空數(shù)組】=>擴容到長度為DEFAULT_CAPACITY（10）的數(shù)組
假設當前底層數(shù)組中已經(jīng)添加了10個元素，現(xiàn)在繼續(xù)調(diào)用add()添加一個元素：數(shù)組擴容1.5倍
3、LinkedList
Deque接口（子接口）
Queue接口（父接口）
源碼分析
（1）雙向鏈表
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;
}
}
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
//構(gòu)造函數(shù)
public LinkedList() {}
（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、CopyOnWriteArrayList【COW并發(fā)容器，寫時復制容器<讀寫分離>】
文章來源：http://www.zghlxwxcb.cn/news/detail-860772.html
底層：Object數(shù)組
文章來源地址http://www.zghlxwxcb.cn/news/detail-860772.html
到了這里，關于Java基礎_集合類_List的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
