?

在編寫java程序中琐馆，我們最常用的除了八種基本數(shù)據(jù)類型，String對象外還有一個集合類譬胎，在我們的的程序中到處充斥著集合類的身影带迟！java中集合大家族的成員實(shí)在是太豐富了磕蛇，有常用的ArrayList景描、HashMap、HashSet秀撇，也有不常用的Stack伏伯、Queue，有線程安全的Vector捌袜、HashTable说搅，也有線程不安全的LinkedList、TreeMap等等虏等！

???????上面的圖展示了整個集合大家族的成員以及他們之間的關(guān)系弄唧。下面就上面的各個接口、基類做一些簡單的介紹(主要介紹各個集合的特點(diǎn)霍衫。區(qū)別)候引，更加詳細(xì)的介紹會在不久的將來一一講解。

一敦跌、Collection接口

???????Collection接口是最基本的集合接口澄干，它不提供直接的實(shí)現(xiàn)逛揩，Java SDK提供的類都是繼承自Collection的“子接口”如List和Set。Collection所代表的是一種規(guī)則麸俘，它所包含的元素都必須遵循一條或者多條規(guī)則辩稽。如有些允許重復(fù)而有些則不能重復(fù)、有些必須要按照順序插入而有些則是散列从媚，有些支持排序但是有些則不支持逞泄。

???????在Java中所有實(shí)現(xiàn)了Collection接口的類都必須提供兩套標(biāo)準(zhǔn)的構(gòu)造函數(shù)，一個是無參拜效，用于創(chuàng)建一個空的Collection喷众，一個是帶有Collection參數(shù)的有參構(gòu)造函數(shù)，用于創(chuàng)建一個新的Collection紧憾，這個新的Collection與傳入進(jìn)來的Collection具備相同的元素到千。

二、List接口

???????List接口為Collection直接接口赴穗。List所代表的是有序的Collection父阻，即它用某種特定的插入順序來維護(hù)元素順序。用戶可以對列表中每個元素的插入位置進(jìn)行精確地控制望抽，同時可以根據(jù)元素的整數(shù)索引（在列表中的位置）訪問元素，并搜索列表中的元素履婉。實(shí)現(xiàn)List接口的集合主要有：ArrayList煤篙、LinkedList、Vector毁腿、Stack辑奈。

2.1、ArrayList

ArrayList是一個動態(tài)數(shù)組已烤，也是我們最常用的集合鸠窗。它允許任何符合規(guī)則的元素插入甚至包括null。每一個ArrayList都有一個初始容量（10）胯究，該容量代表了數(shù)組的大小稍计。隨著容器中的元素不斷增加，容器的大小也會隨著增加裕循。在每次向容器中增加元素的同時都會進(jìn)行容量檢查臣嚣，當(dāng)快溢出時，就會進(jìn)行擴(kuò)容操作剥哑。所以如果我們明確所插入元素的多少硅则，最好指定一個初始容量值，避免過多的進(jìn)行擴(kuò)容操作而浪費(fèi)時間株婴、效率怎虫。

???????size、isEmpty、get大审、set蘸际、iterator 和 listIterator 操作都以固定時間運(yùn)行。add 操作以分?jǐn)偟墓潭〞r間運(yùn)行饥努，也就是說捡鱼，添加 n 個元素需要 O(n) 時間（由于要考慮到擴(kuò)容，所以這不只是添加元素會帶來分?jǐn)偣潭〞r間開銷那樣簡單）酷愧。

ArrayList擅長于隨機(jī)訪問驾诈。同時ArrayList是非同步的。

ArrayList詳解：

一溶浴、ArrayList概述

????? ArrayList是實(shí)現(xiàn)List接口的動態(tài)數(shù)組乍迄，所謂動態(tài)就是它的大小是可變的。實(shí)現(xiàn)了所有可選列表操作士败，并允許包括 null 在內(nèi)的所有元素闯两。除了實(shí)現(xiàn) List 接口外，此類還提供一些方法來操作內(nèi)部用來存儲列表的數(shù)組的大小谅将。

????? 每個ArrayList實(shí)例都有一個容量漾狼，該容量是指用來存儲列表元素的數(shù)組的大小。默認(rèn)初始容量為10饥臂。隨著ArrayList中元素的增加逊躁，它的容量也會不斷的自動增長。在每次添加新的元素時隅熙，ArrayList都會檢查是否需要進(jìn)行擴(kuò)容操作稽煤，擴(kuò)容操作帶來數(shù)據(jù)向新數(shù)組的重新拷貝，所以如果我們知道具體業(yè)務(wù)數(shù)據(jù)量囚戚，在構(gòu)造ArrayList時可以給ArrayList指定一個初始容量酵熙，這樣就會減少擴(kuò)容時數(shù)據(jù)的拷貝問題。當(dāng)然在添加大量元素前驰坊，應(yīng)用程序也可以使用ensureCapacity操作來增加ArrayList實(shí)例的容量匾二，這可以減少遞增式再分配的數(shù)量。

???注意拳芙，ArrayList實(shí)現(xiàn)不是同步的假勿。如果多個線程同時訪問一個ArrayList實(shí)例，而其中至少一個線程從結(jié)構(gòu)上修改了列表态鳖，那么它必須保持外部同步转培。所以為了保證同步，最好的辦法是在創(chuàng)建時完成浆竭，以防止意外對列表進(jìn)行不同步的訪問：

List?list?=?Collections.synchronizedList(new?ArrayList(...));

二浸须、ArrayList源碼分析????

????? ArrayList我們使用的實(shí)在是太多了惨寿，非常熟悉，所以在這里將不介紹它的使用方法删窒。ArrayList是實(shí)現(xiàn)List接口的裂垦，底層采用數(shù)組實(shí)現(xiàn)，所以它的操作基本上都是基于對數(shù)組的操作肌索。

????? 2.1蕉拢、底層使用數(shù)組

????? transient？诚亚？為java關(guān)鍵字晕换，為變量修飾符，如果用transient聲明一個實(shí)例變量站宗，當(dāng)對象存儲時闸准，它的值不需要維持。Java的serialization提供了一種持久化對象實(shí)例的機(jī)制梢灭。當(dāng)持久化對象時夷家，可能有一個特殊的對象數(shù)據(jù)成員，我們不想用serialization機(jī)制來保存它敏释。為了在一個特定對象的一個域上關(guān)閉serialization库快，可以在這個域前加上關(guān)鍵字transient。當(dāng)一個對象被序列化的時候钥顽，transient型變量的值不包括在序列化的表示中义屏，然而非transient型的變量是被包括進(jìn)去的。

????? 這里Object[] elementData耳鸯，就是我們的ArrayList容器，下面介紹的基本操作都是基于該elementData變量來進(jìn)行操作的膀曾。

????? 2.2县爬、構(gòu)造函數(shù)

???? ArrayList提供了三個構(gòu)造函數(shù)：

???? ArrayList()：默認(rèn)構(gòu)造函數(shù)，提供初始容量為10的空列表添谊。

???? ArrayList(int initialCapacity)：構(gòu)造一個具有指定初始容量的空列表财喳。

???? ArrayList(Collection c)：構(gòu)造一個包含指定 collection 的元素的列表，這些元素是按照該 collection 的迭代器返回它們的順序排列的斩狱。

????? 2.3耳高、新增

????? ArrayList提供了add(E e)、add(int index, E element)所踊、addAll(Collection c)泌枪、addAll(int index, Collection c)、set(int index, E element)這個五個方法來實(shí)現(xiàn)ArrayList增加秕岛。

add(E e)：將指定的元素添加到此列表的尾部碌燕。

這里ensureCapacity()方法是對ArrayList集合進(jìn)行擴(kuò)容操作误证，elementData(size++) = e，將列表末尾元素指向e修壕。

add(int index, E element)：將指定的元素插入此列表中的指定位置愈捅。

????? 在這個方法中最根本的方法就是System.arraycopy()方法，該方法的根本目的就是將index位置空出來以供新數(shù)據(jù)插入慈鸠，這里需要進(jìn)行數(shù)組數(shù)據(jù)的右移蓝谨，這是非常麻煩和耗時的，所以如果指定的數(shù)據(jù)集合需要進(jìn)行大量插入（中間插入）操作青团，推薦使用LinkedList譬巫。

addAll(Collection c)：按照指定 collection 的迭代器所返回的元素順序，將該 collection 中的所有元素添加到此列表的尾部壶冒。

這個方法無非就是使用System.arraycopy()方法將C集合(先準(zhǔn)換為數(shù)組)里面的數(shù)據(jù)復(fù)制到elementData數(shù)組中缕题。這里就稍微介紹下System.arraycopy()，因?yàn)橄旅孢€將大量用到該方法胖腾。該方法的原型為：public static voidarraycopy(Object?src, int srcPos,?Object?dest, int destPos, int length)烟零。它的根本目的就是進(jìn)行數(shù)組元素的復(fù)制。即從指定源數(shù)組中復(fù)制一個數(shù)組咸作，復(fù)制從指定的位置開始锨阿，到目標(biāo)數(shù)組的指定位置結(jié)束。將源數(shù)組src從srcPos位置開始復(fù)制到dest數(shù)組中记罚，復(fù)制長度為length墅诡，數(shù)據(jù)從dest的destPos位置開始粘貼。

addAll(int index, Collection c)：從指定的位置開始桐智，將指定 collection 中的所有元素插入到此列表中末早。

set(int index, E element)：用指定的元素替代此列表中指定位置上的元素。

????? 2.4说庭、刪除

??????ArrayList提供了remove(int index)然磷、remove(Object o)、removeRange(int fromIndex, int toIndex)刊驴、removeAll()四個方法進(jìn)行元素的刪除姿搜。

remove(int index)：移除此列表中指定位置上的元素。

remove(Object o)：移除此列表中首次出現(xiàn)的指定元素（如果存在）捆憎。

????? 其中fastRemove()方法用于移除指定位置的元素舅柜。如下

????? removeRange(int fromIndex, int toIndex)：移除列表中索引在fromIndex（包括）和toIndex（不包括）之間的所有元素。

removeAll()：是繼承自AbstractCollection的方法躲惰，ArrayList本身并沒有提供實(shí)現(xiàn)致份。

????? 2.5、查找

????? ArrayList提供了get(int index)用讀取ArrayList中的元素础拨。由于ArrayList是動態(tài)數(shù)組知举，所以我們完全可以根據(jù)下標(biāo)來獲取ArrayList中的元素瞬沦，而且速度還比較快，故ArrayList長于隨機(jī)訪問雇锡。

???? 2.6逛钻、擴(kuò)容

????? 在上面的新增方法的源碼中我們發(fā)現(xiàn)每個方法中都存在這個方法：ensureCapacity()，該方法就是ArrayList的擴(kuò)容方法锰提。在前面就提過ArrayList每次新增元素時都會需要進(jìn)行容量檢測判斷曙痘，若新增元素后元素的個數(shù)會超過ArrayList的容量，就會進(jìn)行擴(kuò)容操作來滿足新增元素的需求立肘。所以當(dāng)我們清楚知道業(yè)務(wù)數(shù)據(jù)量或者需要插入大量元素前边坤，我可以使用ensureCapacity來手動增加ArrayList實(shí)例的容量，以減少遞增式再分配的數(shù)量谅年。

????? 在這里有一個疑問茧痒，為什么每次擴(kuò)容處理會是1.5倍吨艇，而不是2.5牵舱、3腺阳、4倍呢赫冬？通過google查找，發(fā)現(xiàn)1.5倍的擴(kuò)容是最好的倍數(shù)聘萨。因?yàn)橐淮涡詳U(kuò)容太大(例如2.5倍)可能會浪費(fèi)更多的內(nèi)存(1.5倍最多浪費(fèi)33%晨仑，而2.5被最多會浪費(fèi)60%藕帜，3.5倍則會浪費(fèi)71%……)意乓。但是一次性擴(kuò)容太小樱调，需要多次對數(shù)組重新分配內(nèi)存，對性能消耗比較嚴(yán)重届良。所以1.5倍剛剛好笆凌，既能滿足性能需求，也不會造成很大的內(nèi)存消耗士葫。

????? 處理這個ensureCapacity()這個擴(kuò)容數(shù)組外乞而，ArrayList還給我們提供了將底層數(shù)組的容量調(diào)整為當(dāng)前列表保存的實(shí)際元素的大小的功能。它可以通過trimToSize()方法來實(shí)現(xiàn)为障。該方法可以最小化ArrayList實(shí)例的存儲量晦闰。

2.2放祟、LinkedList

???????同樣實(shí)現(xiàn)List接口的LinkedList與ArrayList不同鳍怨，ArrayList是一個動態(tài)數(shù)組，而LinkedList是一個雙向鏈表跪妥。所以它除了有ArrayList的基本操作方法外還額外提供了get鞋喇，remove，insert方法在LinkedList的首部或尾部眉撵。

???????由于實(shí)現(xiàn)的方式不同侦香，LinkedList不能隨機(jī)訪問落塑，它所有的操作都是要按照雙重鏈表的需要執(zhí)行。在列表中索引的操作將從開頭或結(jié)尾遍歷列表（從靠近指定索引的一端）罐韩。這樣做的好處就是可以通過較低的代價在List中進(jìn)行插入和刪除操作憾赁。

與ArrayList一樣，LinkedList也是非同步的散吵。如果多個線程同時訪問一個List龙考，則必須自己實(shí)現(xiàn)訪問同步。一種解決方法是在創(chuàng)建List時構(gòu)造一個同步的List：

List list = Collections.synchronizedList(new LinkedList(...));

LinkedList詳解：

一矾睦、概述

?????? LinkedList與ArrayList一樣實(shí)現(xiàn)List接口晦款，只是ArrayList是List接口的大小可變數(shù)組的實(shí)現(xiàn)，LinkedList是List接口鏈表的實(shí)現(xiàn)枚冗』航Γ基于鏈表實(shí)現(xiàn)的方式使得LinkedList在插入和刪除時更優(yōu)于ArrayList，而隨機(jī)訪問則比ArrayList遜色些赁温。

???????LinkedList實(shí)現(xiàn)所有可選的列表操作坛怪，并允許所有的元素包括null。

除了實(shí)現(xiàn) List 接口外束世，LinkedList 類還為在列表的開頭及結(jié)尾 get酝陈、remove 和 insert 元素提供了統(tǒng)一的命名方法。這些操作允許將鏈接列表用作堆棧毁涉、隊(duì)列或雙端隊(duì)列沉帮。

???????此類實(shí)現(xiàn) Deque 接口，為 add贫堰、poll 提供先進(jìn)先出隊(duì)列操作穆壕，以及其他堆棧和雙端隊(duì)列操作。

???????所有操作都是按照雙重鏈接列表的需要執(zhí)行的其屏。在列表中編索引的操作將從開頭或結(jié)尾遍歷列表（從靠近指定索引的一端）喇勋。

同時，與ArrayList一樣此實(shí)現(xiàn)不是同步的偎行。

（以上摘自JDK 6.0 API）川背。

二、源碼分析

2.1蛤袒、定義

? ? ? ?首先我們先看LinkedList的定義：

從這段代碼中我們可以清晰地看出LinkedList繼承AbstractSequentialList熄云，實(shí)現(xiàn)List、Deque妙真、Cloneable缴允、Serializable。其中AbstractSequentialList提供了 List 接口的骨干實(shí)現(xiàn)珍德，從而最大限度地減少了實(shí)現(xiàn)受“連續(xù)訪問”數(shù)據(jù)存儲（如鏈接列表）支持的此接口所需的工作,從而以減少實(shí)現(xiàn)List接口的復(fù)雜度练般。Deque一個線性 collection矗漾，支持在兩端插入和移除元素，定義了雙端隊(duì)列的操作薄料。

2.2敞贡、屬性

???????在LinkedList中提供了兩個基本屬性size、header摄职。

???????其中size表示的LinkedList的大小嫡锌，header表示鏈表的表頭，Entry為節(jié)點(diǎn)對象琳钉。

???????上面為Entry對象的源代碼势木，Entry為LinkedList的內(nèi)部類，它定義了存儲的元素歌懒。該元素的前一個元素啦桌、后一個元素，這是典型的雙向鏈表定義方式及皂。

2.3甫男、構(gòu)造方法

???????LinkedList提高了兩個構(gòu)造方法：LinkedLis()和LinkedList(Collection c)。

???????LinkedList()構(gòu)造一個空列表验烧。里面沒有任何元素板驳，僅僅只是將header節(jié)點(diǎn)的前一個元素、后一個元素都指向自身碍拆。

???????LinkedList(Collection c)： 構(gòu)造一個包含指定 collection 中的元素的列表若治，這些元素按其 collection 的迭代器返回的順序排列。該構(gòu)造函數(shù)首先會調(diào)用LinkedList()感混，構(gòu)造一個空列表端幼，然后調(diào)用了addAll()方法將Collection中的所有元素添加到列表中。以下是addAll()的源代碼：

???????在addAll()方法中弧满，涉及到了兩個方法婆跑，一個是entry(int index)，該方法為LinkedList的私有方法庭呜，主要是用來查找index位置的節(jié)點(diǎn)元素滑进。

???????從該方法有兩個遍歷方向中我們也可以看出LinkedList是雙向鏈表，這也是在構(gòu)造方法中為什么需要將header的前募谎、后節(jié)點(diǎn)均指向自己扶关。

???????如果對數(shù)據(jù)結(jié)構(gòu)有點(diǎn)了解，對上面所涉及的內(nèi)容應(yīng)該問題近哟，我們只需要清楚一點(diǎn)：LinkedList是雙向鏈表驮审，其余都迎刃而解鲫寄。

由于篇幅有限吉执，下面將就LinkedList中幾個常用的方法進(jìn)行源碼分析疯淫。

2.4、增加方法

???????add(E e): 將指定元素添加到此列表的結(jié)尾戳玫。

該方法調(diào)用addBefore方法熙掺，然后直接返回true，對于addBefore()而已咕宿，它為LinkedList的私有方法币绩。

???????在addBefore方法中無非就是做了這件事：構(gòu)建一個新節(jié)點(diǎn)newEntry，然后修改其前后的引用府阀。

???????LinkedList還提供了其他的增加方法：

add(int index, E element)：在此列表中指定的位置插入指定的元素缆镣。

addAll(Collection c)：添加指定 collection 中的所有元素到此列表的結(jié)尾，順序是指定 collection 的迭代器返回這些元素的順序试浙。

addAll(int index, Collection c)：將指定 collection 中的所有元素從指定位置開始插入此列表董瞻。

AddFirst(E e): 將指定元素插入此列表的開頭。

addLast(E e): 將指定元素添加到此列表的結(jié)尾田巴。

2.5钠糊、移除方法

???????remove(Object o)：從此列表中移除首次出現(xiàn)的指定元素（如果存在）。該方法的源代碼如下：

???????該方法首先會判斷移除的元素是否為null壹哺，然后迭代這個鏈表找到該元素節(jié)點(diǎn)抄伍，最后調(diào)用remove(Entry e)，remove(Entry e)為私有方法管宵，是LinkedList中所有移除方法的基礎(chǔ)方法截珍，如下：

???????其他的移除方法：

clear()： 從此列表中移除所有元素。

remove()：獲取并移除此列表的頭（第一個元素）箩朴。

remove(int index)：移除此列表中指定位置處的元素笛臣。

remove(Objec o)：從此列表中移除首次出現(xiàn)的指定元素（如果存在）。

removeFirst()：移除并返回此列表的第一個元素隧饼。

removeFirstOccurrence(Object o)：從此列表中移除第一次出現(xiàn)的指定元素（從頭部到尾部遍歷列表時）沈堡。

removeLast()：移除并返回此列表的最后一個元素。

removeLastOccurrence(Object o)：從此列表中移除最后一次出現(xiàn)的指定元素（從頭部到尾部遍歷列表時）燕雁。

2.5诞丽、查找方法

???????對于查找方法的源碼就沒有什么好介紹了，無非就是迭代拐格，比對僧免，然后就是返回當(dāng)前值。

get(int index)：返回此列表中指定位置處的元素捏浊。

getFirst()：返回此列表的第一個元素懂衩。

getLast()：返回此列表的最后一個元素。

indexOf(Object o)：返回此列表中首次出現(xiàn)的指定元素的索引，如果此列表中不包含該元素浊洞，則返回 -1牵敷。

lastIndexOf(Object o)：返回此列表中最后出現(xiàn)的指定元素的索引，如果此列表中不包含該元素法希，則返回 -1枷餐。

2.3、Vector

???????與ArrayList相似苫亦，但是Vector是同步的毛肋。所以說Vector是線程安全的動態(tài)數(shù)組。它的操作與ArrayList幾乎一樣屋剑。

Vector詳解

一润匙、Vector簡介

??????? Vector可以實(shí)現(xiàn)可增長的對象數(shù)組。與數(shù)組一樣唉匾，它包含可以使用整數(shù)索引進(jìn)行訪問的組件趁桃。不過，Vector的大小是可以增加或者減小的肄鸽，以便適應(yīng)創(chuàng)建Vector后進(jìn)行添加或者刪除操作卫病。

????????Vector實(shí)現(xiàn)List接口，繼承AbstractList類典徘，所以我們可以將其看做隊(duì)列蟀苛，支持相關(guān)的添加、刪除逮诲、修改帜平、遍歷等功能。

????????Vector實(shí)現(xiàn)RandmoAccess接口梅鹦，即提供了隨機(jī)訪問功能裆甩，提供提供快速訪問功能。在Vector我們可以直接訪問元素齐唆。

????????Vector 實(shí)現(xiàn)了Cloneable接口嗤栓，支持clone()方法，可以被克隆箍邮。

????????Vector提供了四個構(gòu)造函數(shù)：

????????在成員變量方面茉帅，Vector提供了elementData , elementCount， capacityIncrement三個成員變量锭弊。其中

????????elementData ："Object[]類型的數(shù)組"堪澎，它保存了Vector中的元素。按照Vector的設(shè)計(jì)elementData為一個動態(tài)數(shù)組味滞，可以隨著元素的增加而動態(tài)的增長樱蛤，其具體的增加方式后面提到（ensureCapacity方法）钮呀。如果在初始化Vector時沒有指定容器大小，則使用默認(rèn)大小為10.

elementCount：Vector對象中的有效組件數(shù)昨凡。

????????capacityIncrement：向量的大小大于其容量時爽醋，容量自動增加的量。如果在創(chuàng)建Vector時土匀，指定了capacityIncrement的大小形用；則就轧，每次當(dāng)Vector中動態(tài)數(shù)組容量增加時>，增加的大小都是capacityIncrement田度。如果容量的增量小于等于零妒御，則每次需要增大容量時，向量的容量將增大一倍镇饺。

????????同時Vector是線程安全的乎莉！

二、源碼解析

????????對于源碼的解析奸笤，LZ在這里只就增加（add）刪除（remove）兩個方法進(jìn)行講解惋啃。

2.1增加：add(E e)

????????add(E e)：將指定元素添加到此向量的末尾。??

????????這個方法相對而言比較簡單监右，具體過程就是先確認(rèn)容器的大小边灭，看是否需要進(jìn)行擴(kuò)容操作，然后將E元素添加到此向量的末尾健盒。

????????對于Vector整個的擴(kuò)容過程绒瘦，就是根據(jù)capacityIncrement確認(rèn)擴(kuò)容大小的，若capacityIncrement <= 0 則擴(kuò)大一倍扣癣，否則擴(kuò)大至capacityIncrement 惰帽。當(dāng)然這個容量的最大范圍為Integer.MAX_VALUE即，2^32 - 1父虑，所以Vector并不是可以無限擴(kuò)充的该酗。

2.2、remove(Object o)

????????因?yàn)閂ector底層是使用數(shù)組實(shí)現(xiàn)的士嚎，所以它的操作都是對數(shù)組進(jìn)行操作垂涯，只不過其是可以隨著元素的增加而動態(tài)的改變?nèi)萘看笮。鋵?shí)現(xiàn)方法是是使用Arrays.copyOf方法將舊數(shù)據(jù)拷貝到一個新的大容量數(shù)組中航邢。Vector的整個內(nèi)部實(shí)現(xiàn)都比較簡單耕赘，這里就不在重述了。

三膳殷、Vector遍歷

????????Vector支持4種遍歷方式操骡。

3.1九火、隨機(jī)訪問

????????因?yàn)閂ector實(shí)現(xiàn)了RandmoAccess接口，可以通過下標(biāo)來進(jìn)行隨機(jī)訪問册招。

3.2岔激、迭代器

3.3、for循環(huán)

3.4是掰、Enumeration循環(huán)

2.4虑鼎、Stack

???????Stack繼承自Vector，實(shí)現(xiàn)一個后進(jìn)先出的堆棧键痛。Stack提供5個額外的方法使得Vector得以被當(dāng)作堆棧使用炫彩。基本的push和pop 方法絮短，還有peek方法得到棧頂?shù)脑亟ぃ琫mpty方法測試堆棧是否為空，search方法檢測一個元素在堆棧中的位置丁频。Stack剛創(chuàng)建后是空棧杉允。

Stack詳解：

在Java中Stack類表示后進(jìn)先出（LIFO）的對象堆棧。棧是一種非常常見的數(shù)據(jù)結(jié)構(gòu)席里，它采用典型的先進(jìn)后出的操作方式完成的叔磷。每一個棧都包含一個棧頂，每次出棧是將棧頂?shù)臄?shù)據(jù)取出奖磁，如下：

????????Stack通過五個操作對Vector進(jìn)行擴(kuò)展世澜，允許將向量視為堆棧。這個五個操作如下：

????????Stack繼承Vector署穗，他對Vector進(jìn)行了簡單的擴(kuò)展：

view plai

????????Stack的實(shí)現(xiàn)非常簡單寥裂，僅有一個構(gòu)造方法，五個實(shí)現(xiàn)方法（從Vector繼承而來的方法不算與其中）案疲，同時其實(shí)現(xiàn)的源碼非常簡單

????????Stack的源碼很多都是基于Vector

List總結(jié)

一封恰、List接口概述

List接口，成為有序的Collection也就是序列褐啡。該接口可以對列表中的每一個元素的插入位置進(jìn)行精確的控制诺舔，同時用戶可以根據(jù)元素的整數(shù)索引（在列表中的位置）訪問元素，并搜索列表中的元素备畦。 下圖是List接口的框架圖：

????????通過上面的框架圖低飒，可以對List的結(jié)構(gòu)了然于心，其各個類懂盐、接口如下：

????????Collection：Collection 層次結(jié)構(gòu) 中的根接口褥赊。它表示一組對象，這些對象也稱為 collection 的元素莉恼。對于Collection而言拌喉，它不提供任何直接的實(shí)現(xiàn)速那，所有的實(shí)現(xiàn)全部由它的子類負(fù)責(zé)。

????????AbstractCollection：提供 Collection 接口的骨干實(shí)現(xiàn)尿背，以最大限度地減少了實(shí)現(xiàn)此接口所需的工作端仰。對于我們而言要實(shí)現(xiàn)一個不可修改的 collection，只需擴(kuò)展此類田藐，并提供 iterator 和 size 方法的實(shí)現(xiàn)荔烧。但要實(shí)現(xiàn)可修改的 collection，就必須另外重寫此類的 add 方法（否則汽久，會拋出 UnsupportedOperationException）鹤竭，iterator 方法返回的迭代器還必須另外實(shí)現(xiàn)其 remove 方法。

? ? ? ? Iterator：迭代器回窘。

????????ListIterator：系列表迭代器诺擅，允許程序員按任一方向遍歷列表市袖、迭代期間修改列表啡直，并獲得迭代器在列表中的當(dāng)前位置。

????????List：繼承于Collection的接口苍碟。它代表著有序的隊(duì)列酒觅。

????????AbstractList：List 接口的骨干實(shí)現(xiàn)，以最大限度地減少實(shí)現(xiàn)“隨機(jī)訪問”數(shù)據(jù)存儲（如數(shù)組）支持的該接口所需的工作微峰。

????????Queue：隊(duì)列舷丹。提供隊(duì)列基本的插入、獲取蜓肆、檢查操作颜凯。

????????Deque：一個線性 collection，支持在兩端插入和移除元素仗扬。大多數(shù) Deque 實(shí)現(xiàn)對于它們能夠包含的元素?cái)?shù)沒有固定限制症概，但此接口既支持有容量限制的雙端隊(duì)列，也支持沒有固定大小限制的雙端隊(duì)列早芭。

????????AbstractSequentialList：提供了 List 接口的骨干實(shí)現(xiàn)彼城，從而最大限度地減少了實(shí)現(xiàn)受“連續(xù)訪問”數(shù)據(jù)存儲（如鏈接列表）支持的此接口所需的工作。從某種意義上說退个，此類與在列表的列表迭代器上實(shí)現(xiàn)“隨機(jī)訪問”方法募壕。

????????LinkedList：List 接口的鏈接列表實(shí)現(xiàn)。它實(shí)現(xiàn)所有可選的列表操作语盈。

????????ArrayList：List 接口的大小可變數(shù)組的實(shí)現(xiàn)舱馅。它實(shí)現(xiàn)了所有可選列表操作，并允許包括 null 在內(nèi)的所有元素刀荒。除了實(shí)現(xiàn) List 接口外习柠，此類還提供一些方法來操作內(nèi)部用來存儲列表的數(shù)組的大小匀谣。

????????Vector：實(shí)現(xiàn)可增長的對象數(shù)組。與數(shù)組一樣资溃，它包含可以使用整數(shù)索引進(jìn)行訪問的組件武翎。

????????Stack：后進(jìn)先出（LIFO）的對象堆棧。它通過五個操作對類 Vector 進(jìn)行了擴(kuò)展 溶锭，允許將向量視為堆棧宝恶。

????????Enumeration：枚舉，實(shí)現(xiàn)了該接口的對象趴捅，它生成一系列元素垫毙，一次生成一個。連續(xù)調(diào)用 nextElement 方法將返回一系列的連續(xù)元素拱绑。

二综芥、使用場景

????????學(xué)習(xí)知識的根本目的就是使用它。每個知識點(diǎn)都有它的使用范圍猎拨。集合也是如此膀藐，在Java中集合的家族非常龐大，每個成員都有最適合的使用場景红省。在剛剛接觸List時额各，LZ就說過如果涉及到“棧”吧恃、“隊(duì)列”虾啦、“鏈表”等操作，請優(yōu)先考慮用List痕寓。至于是那個List則分如下：

????????1傲醉、對于需要快速插入、刪除元素呻率，則需使用LinkedList硬毕。

????????2、對于需要快速訪問元素筷凤，則需使用ArrayList昭殉。

????????3、對于“單線程環(huán)境”或者“多線程環(huán)境藐守，但是List僅被一個線程操作”挪丢，需要考慮使用非同步的類，如果是“多線程環(huán)境卢厂，切List可能同時被多個線程操作”乾蓬，考慮使用同步的類（如Vector）。

2.1ArrayList慎恒、LinkedList性能分析

????????在List中我們使用最普遍的就是LinkedList和ArrayList任内，同時我們也了解了他們兩者之間的使用場景和區(qū)別撵渡。

????????運(yùn)行結(jié)果:

????????從上面的運(yùn)行結(jié)果我們可以清晰的看出ArrayList、LinkedList死嗦、Vector增加趋距、刪除、遍歷的效率問題越除。下面我就插入方法add(int index, E element),delete节腐、get方法各位如有興趣可以研究研究。

????????首先我們先看三者之間的源碼：

????????ArrayList

????????rangeCheckForAdd摘盆、ensureCapacityInternal兩個方法沒有什么影響翼雀，真正產(chǎn)生影響的是System.arraycopy方法，該方法是個JNI函數(shù)孩擂，是在JVM中實(shí)現(xiàn)的狼渊。聲明如下：

???????事實(shí)上我們只需要了解該方法會移動index后面的所有元素即可，這就意味著ArrayList的add(int index, E element)方法會引起index位置之后所有元素的改變类垦，這真是牽一處而動全身狈邑。

LinkedList

????????該方法比較簡單，插入位置在末尾則調(diào)用linkLast方法护锤，否則調(diào)用linkBefore方法官地，其實(shí)linkLast酿傍、linkBefore都是非常簡單的實(shí)現(xiàn)烙懦，就是在index位置插入元素，至于index具體為知則有node方法來解決赤炒，同時node對index位置檢索還有一個加速作用氯析，如下：

????????所以linkedList的插入動作比ArrayList動作快就在于兩個方面。

1:linkedList不需要執(zhí)行元素拷貝動作莺褒，沒有牽一發(fā)而動全身的大動作掩缓。

2:查找插入位置有加速動作即：若index < 雙向鏈表長度的1/2，則從前向后查找; 否則遵岩，從后向前查找你辣。

????????Vector

????????Vector的實(shí)現(xiàn)機(jī)制和ArrayList一樣，同樣是使用動態(tài)數(shù)組來實(shí)現(xiàn)的尘执，所以他們兩者之間的效率差不多舍哄，add的源碼也一樣，如下：

????????上面是針對ArrayList誊锭、LinkedList表悬、Vector三者之間的add（int index,E element)方法的解釋，解釋了LinkedList的插入動作要比ArrayList丧靡、Vector的插入動作效率為什么要高出這么多蟆沫！至于delete籽暇、get兩個方法LZ就不多解釋了。

2.2饭庞、Vector和ArrayList的區(qū)別