一剑肯、集合的繼承關(guān)系
Collection是繼承自Iterable
二撕氧、什么是Iterable
1 . Iterable是可迭代的意思
2 . Iterable是一個(gè)接口
3 . 我們看一下官方解釋：Implementing this interface allows an object to be the target of the "for-each loop" statement.
簡(jiǎn)單意思就是：實(shí)現(xiàn)此接口息拜，讓對(duì)象允許成為"for-each loop"的目標(biāo)。
相信什么是"for-each"大家都知道
4 . 里面有三個(gè)方法：
- 1 Iterator<T> iterator()；生成一個(gè)迭代器
Iterator<T> iterator();
- 2 default void forEach(Consumer<? super T> action)蔚舀；根據(jù)action對(duì)內(nèi)部元素進(jìn)行遍歷
default void forEach(Consumer<? super T> action) {
//判斷動(dòng)作是否為空
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
- 3 創(chuàng)建一個(gè)分割器（Spliterator）附较，這里先不了解吃粒。
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
那么我們簡(jiǎn)單定義一下，實(shí)現(xiàn)此接口的類會(huì)成為一個(gè)可迭代的容器拒课。
三徐勃、什么是Collection
1 . 通過(guò)注釋我們可以知道Collection是所有集合的根接口
2 . Collection中包含了很多處理容器中各種元素的方法，比如：增加捕发，移除疏旨，比較（兩個(gè)集合），轉(zhuǎn)換（數(shù)組或者其他）
那么我們可以簡(jiǎn)單定義一下扎酷，這個(gè)Collection接口就是給實(shí)現(xiàn)它的容器提供基本規(guī)范的方法檐涝；
四、什么是List
1 .List是List家族的頂級(jí)接口
2 .List是一個(gè)有序集合序列（在我看來(lái)線性表）
3 .從List中的各種方法看來(lái)，List就是用來(lái)規(guī)范List家族的接口
4 .List家族的成員都必須實(shí)現(xiàn)這個(gè)接口谁榜，實(shí)現(xiàn)其中的方法幅聘，成為L(zhǎng)ist的一員
5 .List家族有四個(gè)成員ArrayList、LinkList窃植、Victor帝蒿、Stack
這里簡(jiǎn)單總結(jié)一下，這些接口都是用于規(guī)范的巷怜，并沒(méi)有實(shí)現(xiàn)具體邏輯葛超。
五、ArryList是如何實(shí)現(xiàn)的
接下來(lái)我們要看ArryList的源碼了延塑，但是在看源碼之前我們要理清思路绣张，我們重點(diǎn)看什么？
- 1 ArryList的重要方法关带，添加侥涵，移除，擴(kuò)張宋雏，比較等等還有與其相關(guān)的屬性
- 2 ArryList的迭代器
1 . ArryList的迭代器芜飘，ArryList中有一個(gè)內(nèi)部類專門實(shí)現(xiàn)了迭代器接口
private class Itr implements Iterator<E> {}
2 . 雖然List已經(jīng)有了一個(gè)基本的迭代器，但是List對(duì)這個(gè)基本的迭代器的功能并不滿足磨总，所以下面有產(chǎn)生了一個(gè)List專門用的迭代器：
private class ListItr extends Itr implements ListIterator<E> {}
3嗦明、初此之外，ArrayList覆寫(xiě)了父類和List接口的方法舍败，添加招狸，移除，擴(kuò)張邻薯，比較等等裙戏。
- 1 ArrayList是通過(guò)數(shù)組實(shí)現(xiàn)
- 2 ArrayList擴(kuò)張是數(shù)組的copyOf()方法，第一次擴(kuò)張數(shù)組大小變?yōu)?0厕诡，后面如果要擴(kuò)張的話累榜，大小變?yōu)橐郧暗?.5倍
- 3 對(duì)ArrayList的中操作迭代器會(huì)改變ArrayList的成員變量，但是如果只對(duì)ArrayList操作灵嫌，則沒(méi)有影響迭代器
- 4 ArrayList里面的元素是無(wú)序的（沒(méi)有按大小順序排列）壹罚，他是根據(jù)插入元素的先后順序排列的
源碼分析
ArrayList的源碼比較清晰，這里只討論是如何自動(dòng)擴(kuò)張的寿羞。
我們知道ArrayList是基于數(shù)組的猖凛，數(shù)組有什么不好的地方呢？對(duì)了绪穆，就是一旦生成了就大小固定無(wú)法擴(kuò)展了辨泳，那么ArrayList是如何自動(dòng)擴(kuò)張的呢虱岂？
首先看向add()方法：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
這里有一個(gè)調(diào)用了ensureCapacityInternal()方法，翻譯一下：確保容量?jī)?nèi)部菠红，那這個(gè)方法是干什么的呢第岖？我們跟蹤查看一下。
private void ensureCapacityInternal(int minCapacity) {
//判斷當(dāng)前使用的數(shù)組是否為空數(shù)組
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//最小的容量為DEFAULT_CAPACITY和size+1的更大者
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
從第二行看起试溯，elementData是一個(gè)全局變量蔑滓，用來(lái)表示ArrayList當(dāng)前正在使用的數(shù)組，當(dāng)前正在使用的數(shù)組是否是空數(shù)組遇绞，如果是空數(shù)組的話键袱，最小容量就是DEFAULT_CAPACITY（10）和size+1的更大者。
好了看看第六行摹闽，又調(diào)用了一個(gè)ensureExplicitCapacity（）方法杠纵，解釋一下：確保明確的容量，我們?cè)俑櫜榭垂澈В葧?huì)兒再回來(lái)。
private void ensureExplicitCapacity(int minCapacity) {
//ArrayList的結(jié)構(gòu)變化增加了一次
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//一定會(huì)執(zhí)行
grow(minCapacity);
}
modCount是什么铝量？ ArrayList 發(fā)生結(jié)構(gòu)變化的次數(shù)倘屹。
接下來(lái)看看第6行：如果最小容量大于當(dāng)前正在使用的數(shù)組的容量，就執(zhí)行 grow（）方法慢叨，我們繼續(xù)追蹤grow()方法
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//新的容量是舊的容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
// 新容量小于最小容量的話纽匙，就把最小容量賦值給新容量
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
//新容量大于數(shù)組最大容量，就把整數(shù)的最大值賦值給新容量
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
重點(diǎn)來(lái)了拍谐，看向第13行烛缔，數(shù)組實(shí)際擴(kuò)張的辦法，通過(guò)Arrays的靜態(tài)方法copyOf（）轩拨。我們追蹤一下這個(gè)方法：
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
啊哈践瓷，又調(diào)用了它的三個(gè)參數(shù)的重載方法，我們繼續(xù)追蹤：
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;
}
完成了亡蓉，就是直接new一個(gè)新的數(shù)組晕翠，然后再把舊的數(shù)組的數(shù)據(jù)復(fù)制回去。
接下來(lái)我們要返回到add（）方法中完成最后的步驟了：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
給當(dāng)前正在使用的數(shù)elementData添加元素砍濒，這里有個(gè)問(wèn)題淋肾，size中的是什么呢？大家可以猜猜哦爸邢。樊卓。
六、LinkList是如何實(shí)現(xiàn)的
我們先看一下LinkList的繼承關(guān)系
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}
我們可以看見(jiàn)LinkList比ArrayList多實(shí)現(xiàn)了一個(gè)接口Deque<E>杠河，那么這個(gè)接口是什么呢碌尔？我們來(lái)看看
public interface Deque<E> extends Queue<E> {}
通過(guò)注釋我們可以發(fā)現(xiàn)這個(gè)接口是一個(gè)線性雙端隊(duì)列浇辜，它支持容量限制的雙端隊(duì)列。
在這里我們對(duì)LinkList有了一點(diǎn)了解七扰。接下來(lái)我們看看LinkList的注釋奢赂。
* Doubly-linked list implementation of the {@code List} and {@code Deque}
* interfaces. Implements all optional list operations, and permits all
* elements (including {@code null}).
大致意思是：LinkList是一個(gè)雙鏈表，可以操作所有元素
1颈走、LinkList與ArrayList不同膳灶，他是雙鏈表
2、LinkList的擴(kuò)張與刪除就是結(jié)點(diǎn)的增加和刪除
3立由、集合中的元素是也是無(wú)序的轧钓，他是根據(jù)插入結(jié)點(diǎn)的位置來(lái)排列的
4、判斷是從頭結(jié)點(diǎn)插入還是從尾結(jié)點(diǎn)開(kāi)始插入做了優(yōu)化
源碼分析
為什么說(shuō)LinkList是雙鏈表呢锐膜？
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
LinkList定義了一個(gè)頭結(jié)點(diǎn)和一個(gè)尾結(jié)點(diǎn)毕箍。Node是LinkList的內(nèi)部類，我們看看他這個(gè)結(jié)點(diǎn)是怎么實(shí)現(xiàn)的：
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;
}
}
首先Node是一個(gè)私有的靜態(tài)泛型類道盏，它有三個(gè)全局變量而柑，第一個(gè)變量是結(jié)點(diǎn)儲(chǔ)存的元素，后面兩個(gè)變量分別是當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)荷逞，很簡(jiǎn)單媒咳。
接下來(lái)我們看看LinkList的插入結(jié)點(diǎn)的方法add（）
public boolean add(E e) {
//直接插入默認(rèn)插入到尾部
linkLast(e);
return true;
}
public void add(int index, E element) {
//檢查這個(gè)索引是否超出鏈表的邊界
checkPositionIndex(index);
if (index == size)
//鏈表為空的時(shí)候或者想要插入到尾部的時(shí)候直接插入到尾部
linkLast(element);
else
linkBefore(element, node(index));
}
我們可以看見(jiàn) LinkList的add（）有兩個(gè)重載方法。
直接插入話种远，默認(rèn)是插入到尾部的涩澡。
如果過(guò)通過(guò)索引插入的話，我們看向第15行：
這里執(zhí)行了linkBefore（）方法坠敷，插入之前的查找工作妙同，傳入了需要插入的元素和node（）這個(gè)方法的返回值
我們先看看node（）這個(gè)方法是干什么的：
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;
}
}
這里代碼很簡(jiǎn)單，如果請(qǐng)求插入的索引小于size的一半則從頭開(kāi)始遍歷膝迎，反之則從尾部開(kāi)始遍歷粥帚。返回的也是一個(gè)節(jié)點(diǎn)
然后我們看看linkBefore（）方法：
/**
* Inserts element e before non-null Node succ.//把我們要插入的元素插入到suuc這個(gè)節(jié)點(diǎn)之前
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
這部分代碼的意思就是把我們需要插入的節(jié)點(diǎn)插入到我們用node（）方法找到的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)那里。
好了LinkList的源碼主要也是分析add（）方法限次。
