集合元素在內(nèi)存如何存放
數(shù)據(jù)元素在內(nèi)存中乳讥，主要有2種存儲方式：
1颜及、順序存儲吐咳，Random Access（或直接存儲会宪，Direct Access）：
這種方式肖卧，相鄰的數(shù)據(jù)元素存放于相鄰的內(nèi)存地址中，整塊內(nèi)存地址是連續(xù)的掸鹅∪剩可以根據(jù)元素的位置直接計算出內(nèi)存地址拦赠，直接進(jìn)行讀取。讀取一個特定位置元素的平均時間復(fù)雜度為O(1)葵姥。這種數(shù)據(jù)結(jié)構(gòu)插入和刪除時比較麻煩荷鼠，查詢比較方便。正常來說榔幸，只有基于數(shù)組實現(xiàn)的集合允乐，才有這種特性。Java中以ArrayList為代表削咆；
2牍疏、鏈?zhǔn)酱鎯Γ琒equential Access：
這種方式是將數(shù)據(jù)元素放在獨立的空間中拨齐，在內(nèi)存中每個元素的內(nèi)存地址都不要求是相鄰的鳞陨。所以每個元素中需要保存下一個元素的索引，即下一個元素的內(nèi)存地址瞻惋。所以這種數(shù)據(jù)結(jié)構(gòu)插入和刪除比較方便厦滤，但是查找很麻煩，要從第一個開始遍歷歼狼，因為它無法根據(jù)元素的位置直接計算出內(nèi)存地址掏导，只能按順序讀取元素。讀取一個特定位置元素的平均時間復(fù)雜度為O(n)羽峰。主要以鏈表為代表碘菜。Java中以LinkedList為代表；
Java集合遍歷方式
1）傳統(tǒng)的for循環(huán)遍歷基于計數(shù)器
遍歷者自己在集合外部維護(hù)一個計數(shù)器限寞，然后依次讀取每一個位置的元素忍啸，直到讀取到最后一個元素后。主要就是需要按元素的位置來讀取元素履植，適合于遍歷順序存儲的數(shù)據(jù)結(jié)構(gòu)计雌；
for (int i = 0; i < list.size(); i++) {
list.get(i);
}
2）迭代器遍歷Iterator
Iterator本來是OO的一個設(shè)計模式，主要目的就是屏蔽不同數(shù)據(jù)集合的特點玫霎，統(tǒng)一遍歷集合的接口凿滤。從結(jié)構(gòu)上可以看出，迭代器模式在客戶與容器之間加入了迭代器角色庶近。迭代器角色的加入翁脆，就可以很好的避免容器內(nèi)部細(xì)節(jié)的暴露，而且也使得設(shè)計符號“單一職責(zé)原則”鼻种；
每一個具體實現(xiàn)的數(shù)據(jù)集合反番，一般都需要提供相應(yīng)的Iterator。相比于傳統(tǒng)for循環(huán)，Iterator取代了顯式的遍歷計數(shù)器罢缸。所以基于順序存儲集合的Iterator可以直接按位置訪問數(shù)據(jù)篙贸。而基于鏈?zhǔn)酱鎯系腎terator，正常的實現(xiàn)都是需要保存當(dāng)前遍歷的位置枫疆，然后根據(jù)當(dāng)前位置來向前或者向后移動指針
迭代器模式的寫法如下：
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
iterator.next();
}
3）foreach循環(huán)遍歷
foreach內(nèi)部也是采用了Iterator的方式實現(xiàn)爵川，根據(jù)反編譯的字節(jié)碼可以發(fā)現(xiàn)，foreach內(nèi)部也是采用了Iterator的方式實現(xiàn)息楔，只不過Java編譯器幫我們生成了這些代碼
優(yōu)點：代碼簡潔寝贡，不易出錯
缺點：只能做簡單的遍歷，不能在遍歷過程中操作（刪除值依、替換）數(shù)據(jù)集合
for (ElementType element : list) {
}
遍歷性能
1）傳統(tǒng)的for循環(huán)遍歷基于計數(shù)器
ArrayList按位置讀取的代碼：直接按元素位置讀取
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
LinkedList按位置讀取的代碼：如果index小于容量的一半兔甘，則從頭開始查找，否則從尾部開始查找
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
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;
}
}
2）迭代器遍歷Iterator
對于RandomAccess類型的集合來說鳞滨，如ArrayList迭代器遍歷反而因為一些額外的操作洞焙，還會增加額外的運(yùn)行時間；
對于Sequential Access的集合來說拯啦，因為Iterator內(nèi)部維護(hù)了當(dāng)前遍歷的位置澡匪，所以每次遍歷，讀取下一個位置并不需要從集合的第一個元素開始查找褒链，只要把指針向后移一位就行了唁情，這樣一來遍歷整個集合的時間復(fù)雜度就降低為O(n)；以LinkedList的迭代器為例甫匹，其內(nèi)部實現(xiàn)甸鸟，就是維護(hù)當(dāng)前遍歷的位置，然后操作指針移動就可以了
3）foreach循環(huán)遍歷
分析Java字節(jié)碼可知兵迅，foreach內(nèi)部實現(xiàn)原理是通過Iterator實現(xiàn)的抢韭，只不過這個Iterator是Java編譯器幫我們生成的，所以我們不需要再手動去編寫恍箭。但是因為每次都要做類型轉(zhuǎn)換檢查刻恭，所以花費(fèi)的時間比Iterator略長，而時間復(fù)雜度和Iterator是一樣
使用場景
1）傳統(tǒng)的for循環(huán)遍歷基于計數(shù)器
適用于遍歷順序存儲集合扯夭，讀取性能比較高如ArrayList鳍贾；不適用于遍歷鏈?zhǔn)酱鎯Φ募先鏛inkedList，時間復(fù)雜度太大交洗；
2）迭代器遍歷Iterator
對于順序存儲的數(shù)據(jù)結(jié)構(gòu)骑科，如果不是太在意時間，推薦選擇此方式构拳，畢竟代碼更加簡潔咆爽，也防止了Off-By-One的問題梁棠。
鏈?zhǔn)酱鎯Γ和扑]此種遍歷方式，平均時間復(fù)雜度降為O(n)
3）foreach循環(huán)遍歷
foreach讓代碼更加簡潔伍掀，缺點就是遍歷過程中不能操作數(shù)據(jù)集合（刪除等）掰茶，所以有些場合不使用暇藏。而且它本身就是基于Iterator實現(xiàn)的蜜笤，但是由于類型轉(zhuǎn)換的問題，所以會比直接使用Iterator慢一點盐碱，性能上相差不大
