最近在準(zhǔn)備Java實(shí)習(xí)生面試的過(guò)程中發(fā)現(xiàn)很多面Java基礎(chǔ)時(shí)都會(huì)設(shè)計(jì)到集合相關(guān)的東西泊业，所以準(zhǔn)備總結(jié)一下集合相關(guān)的東西。
看過(guò)很多博客，大家大多以Collection下面的幾大接口進(jìn)行集合總結(jié)的箫柳，我準(zhǔn)備以各個(gè)集合底層具體實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)為主線讼育，附帶集合的具體實(shí)現(xiàn)接口中的方法來(lái)進(jìn)行總結(jié)帐姻。
隊(duì)列：###
通常有兩種實(shí)現(xiàn)方法：
- 使用循環(huán)數(shù)組，在Java中對(duì)應(yīng)ArrayDeque類(lèi)
- 使用鏈表奶段，在java中對(duì)應(yīng)LinkedList類(lèi)饥瓷，同時(shí)該類(lèi)實(shí)現(xiàn)了Queue接口
循環(huán)數(shù)組要比鏈表更加的高效，一般優(yōu)先選擇循環(huán)數(shù)組痹籍，但循環(huán)數(shù)組是一個(gè)有限集合呢铆，容量是有限制的。如果程序當(dāng)中我們所需要容納的集合元素是無(wú)限的責(zé)需要使用LinkedList 類(lèi) 蹲缠。后面我們將闡述它們底層的具體實(shí)現(xiàn)和具體使用方法棺克，在這之前我們先了解一下集合中最重要的兩個(gè)接口Collection和Iterator悠垛。
Iterator接口#####
iterator()方法用于返回一個(gè)實(shí)現(xiàn)了Iterator接口的對(duì)象∧婧剑可以使用這個(gè)迭代器對(duì)象依次訪問(wèn)集合中的元素鼎文。該接口中包含了三個(gè)方法:
public interface Iterator<E>{
E next(); //迭代引用先后移動(dòng)，返回此次移動(dòng)越過(guò)的對(duì)象
boolean hasNext(); //表示還有沒(méi)有其他的元素
void remove(); //移除迭代子最后一次越過(guò)的元素
}
因?yàn)?strong>Collection接口擴(kuò)展了Iterable接口因俐，因此對(duì)標(biāo)準(zhǔn)庫(kù)中的任何集合都可以使用"for each"循環(huán)
for(String element : c){
//do something with element
}
在Iterator的使用當(dāng)中我認(rèn)為應(yīng)該理解注意以下幾個(gè)方面：
- Java集合類(lèi)庫(kù)中的迭代器與其它類(lèi)庫(kù)中的迭代器在概念上有著重要的區(qū)別拇惋。其它地方迭代器是根據(jù)數(shù)組索引建模的。Java迭代器中查找操作與位置變更是緊密相連的抹剩。查找一個(gè)元素的唯一方法是調(diào)用next()撑帖，而在執(zhí)行查找操作的同時(shí)，迭代器的位置隨之向前移動(dòng)澳眷。調(diào)用next()胡嘿，迭代器就越過(guò)下一個(gè)元素，并返回剛剛越過(guò)的元素的引用钳踊；
- next()方法和remove()方法是具有相互依賴(lài)性的衷敌。如果調(diào)用remove之前沒(méi)有調(diào)用next將是不合法的。會(huì)拋出一個(gè)IllegalStateException異常拓瞪。
- next方法調(diào)用到最后沒(méi)有元素時(shí)將拋出NoSuchElementException缴罗，所以我們?cè)谡{(diào)用next方法之前，應(yīng)當(dāng)先調(diào)用hasNext()方法祭埂。
PS:后面還會(huì)介紹一個(gè)listIterator()方法面氓，是list接口的一個(gè)方法，LinkedList實(shí)現(xiàn)了這個(gè)接口蛆橡，該接口還會(huì)提供向前遍歷以及添加元素等一些功能舌界，我們之后再講。
Collection接口#####
除了Map結(jié)尾的集合類(lèi)外泰演，基本上都實(shí)現(xiàn)了Collection接口呻拌，它提供了很多實(shí)用的方法，后面我們便列出一些常用的方法：
//返回一個(gè)迭代器
Iterator<E> iterator();
//返回集合中元素的個(gè)數(shù)
int size();
//集合中是否包含該元素
boolean contains(Object obj);
//該集合是否包含other集合中的所有元素
boolean containsAll(Collection<?> other);
//想集合中添加一個(gè)元素粥血，如果該調(diào)用改變了集合柏锄，返回true
boolean add(Object element);
//將other中的所有元素添加入集合
boolean addAll(Collection<? extends E> other);
//刪除集合中等于obj的對(duì)象，如果匹配對(duì)象唄刪除复亏，返回true
boolean remove(Object obj);
//刪除集合中所有other所含元素
boolean removeAll(Collection<?> other);
//刪除集合中所有元素
void clear();
//從這個(gè)集合中刪除所有與other集合中的元素不同的元素趾娃。如果由于這個(gè)調(diào)用改變了集合，返回true
boolean retainAll(Collection<?> other);
//返回這個(gè)集合的對(duì)象數(shù)組
Object[] toArray();
//返回這個(gè)集合的對(duì)象數(shù)組缔御，如果arrayToFill足夠大抬闷，就將集合中的元素填入這個(gè)數(shù)組中，剩余空間用null填補(bǔ)，否則分配一個(gè)新數(shù)組笤成，其成員類(lèi)型與arrayToFill的成員類(lèi)型相同评架，其長(zhǎng)度等于集合的大小，并填入集合元素
<T> T[] toArray(T[] arrayToFill);
現(xiàn)在我們對(duì)集合有了一個(gè)基本的了解炕泳，下面我們根據(jù)底層數(shù)據(jù)結(jié)構(gòu)來(lái)講解具體的集合纵诞。
鏈表(Link)來(lái)講解LinkedList###
在Java中，所有鏈表實(shí)際上都是雙向鏈接的(doubly linked)培遵，每個(gè)節(jié)點(diǎn)還存放著指向前驅(qū)節(jié)點(diǎn)的引用浙芙。為了方便我就直接貼上來(lái)LinkedList的API。
鏈表是一個(gè)有序集合籽腕，每個(gè)對(duì)象的位置都十分的重要嗡呼。
LinkedList.add()方法將對(duì)象添加到鏈表的尾部。但是我們常常需要講一個(gè)元素添加到鏈表的中間皇耗。由于迭代器是描述集合中的位置南窗，集合類(lèi)庫(kù)提供了子接口ListIterator，其中是包含add()方法的
上面就是ListIterator所包含的方法郎楼，次對(duì)象可由LinkedList的listIterator()方法獲取万伤，該方法是list接口中的，而LinkedList便實(shí)現(xiàn)了該接口所有有此方法呜袁。我們?cè)谑褂眠^(guò)程中需要注意：
- add方法只依賴(lài)于迭代器的位置壕翩，而remove方法依賴(lài)于迭代器的狀態(tài)，如果將我們的迭代器比作光標(biāo)傅寡，則add()方法便將元素插入到光標(biāo)前，remove方法便是我們的backspace操作北救。
- 多個(gè)迭代器同時(shí)訪問(wèn)一個(gè)集合荐操，如果迭代器發(fā)現(xiàn)它的集合被另一個(gè)迭代器修改了，就會(huì)拋出一個(gè)Concurrent ModificationException異常珍策，為了避免發(fā)生并發(fā)修改異常托启，我們可以根據(jù)需要給容器附加許多的迭代器，但是這些迭代器智能讀取列表攘宙。另外屯耸，再單獨(dú)附加一個(gè)既能讀又能寫(xiě)的迭代器。
- 鏈表是不支持隨機(jī)訪問(wèn)的蹭劈，如果要查找一個(gè)元素疗绣，就必須從頭開(kāi)始查找，下面有一種效率很低的做法铺韧，盡管get()方法做了微小的優(yōu)化多矮，當(dāng)索引大于size()/2就從列表尾端開(kāi)始搜索元素
for(int i = 0 ; i< list.size() ; i++){
do something with list.get(i);//因?yàn)樽霾坏骄彺嫖恢眯畔⒌牟僮鳎悦看蝕et都要從頭開(kāi)始
}
先總結(jié)到這兒吧，以后有關(guān)List的一些特性放到ArrayList的分析中去
