List接口

概述：1.List接口是Collection的直接接口，代表的是有序的Collection；

? ? ? ? ? ?2.該接口可以對列表中的每一個(gè)元素的插入位置進(jìn)行精確的控制，同時(shí)可以根據(jù)索引訪問元素傻盟。

? ? ? ? ? ?3.實(shí)現(xiàn)接口主要有：ArrayList愕掏、LinkedList、Vector狈醉、Stack。

List接口結(jié)構(gòu)

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

List：繼承于Collection的接口。它代表著有序的隊(duì)列逊桦。

AbstractCollection：提供 Collection 接口的骨干實(shí)現(xiàn)眨猎，以最大限度地減少了實(shí)現(xiàn)此接口所需的工作。對于我們而言要實(shí)現(xiàn)一個(gè)不可修改的 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? collection强经，只需擴(kuò)展此類睡陪，并提供 iterator 和 size 方法的實(shí)現(xiàn)。

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

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

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

ArrayList：該類也是實(shí)現(xiàn)了List的接口府蔗，實(shí)現(xiàn)了可變大小的數(shù)組晋控，隨機(jī)訪問和遍歷元素時(shí)，提供更好的性能姓赤。

Iterator：迭代器赡译。

ListIterator：系列表迭代器，允許程序員按任一方向遍歷列表不铆、迭代期間修改列表蝌焚，并獲得迭代器在列表中的當(dāng)前位置

Queue：隊(duì)列。提供隊(duì)列基本的插入誓斥、獲取只洒、檢查操作。

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

Enumeration：枚舉，實(shí)現(xiàn)了該接口的對象框仔，它生成一系列元素舀武，一次生成一個(gè)。連續(xù)調(diào)用 nextElement 方法將返回一系列的連續(xù)元素离斩。

應(yīng)用場景：如果涉及到“椧眨”衷旅、“隊(duì)列”、“鏈表”等操作纵朋，請優(yōu)先考慮用List。

? ? ? ? ? ? ? ? ? 1.對于需要快速插入茄袖、刪除元素操软，則需使用LinkedList；

? ? ? ? ? ? ? ? ? 2.對于需要快速訪問元素宪祥，則需使用ArrayList聂薪；

? ? ? ? ? ? ? ? ? 3.根據(jù)單/多線程環(huán)境，使用線程非/安全的實(shí)現(xiàn)類蝗羊；

其中隊(duì)列和迭代器簡單介紹下：

Queue

分類：1.阻塞式隊(duì)列（隊(duì)列滿了以后再插入元素則會(huì)拋出異常）eg：ArrayBlockQueue藏澳、PriorityBlockingQueue、LinkedBlockingQueue

2.雙端隊(duì)列（支持在頭耀找、尾兩端插入和移除元素）eg：ArrayDeque翔悠、LinkedBlockingDeque、LinkedList

Iterator? 迭代器

簡介：迭代可以簡單地理解為遍歷野芒，是一個(gè)標(biāo)準(zhǔn)化的遍歷各類容器里面的所有對象的方法類蓄愁；

是一個(gè)典型的設(shè)計(jì)模式（把訪問邏輯從不同容器中抽象處理，隱藏容器內(nèi)部結(jié)構(gòu)狞悲，返回一個(gè)標(biāo)準(zhǔn)化的訪問方法）撮抓；

在Java中Iterator為一個(gè)接口，它只提供了迭代了基本規(guī)則摇锋；

迭代器詳解

List接口實(shí)現(xiàn)類對比

ArrayList （線程不安全）

簡介：ArrayList是一個(gè)動(dòng)態(tài)數(shù)組丹拯，也是我們最常用的集合。

特性：1.允許任何符合規(guī)則的元素插入甚至包括null荸恕，ArrayList是非同步的乖酬；

? ? ? ? ? ?2.初始容量分配為10，每次add會(huì)進(jìn)行容量檢查戚炫，不足時(shí)會(huì)進(jìn)行擴(kuò)容剑刑；

? ? ? ? ? ?3.適合快速訪問數(shù)據(jù)（通過下標(biāo)）；

缺點(diǎn)：數(shù)組是將元素在內(nèi)存中連續(xù)存放的双肤，因此增加或刪除其中一個(gè)元素都需要移動(dòng)大量元素施掏。

ArrayList源碼解析

LinkedList （線程不安全）

簡介：LinkedList是一個(gè)雙向鏈表，除了有ArrayList的基本操作還額外提供了get茅糜，remove七芭，insert等方法。

特性：1.允許所有元素包括null蔑赘，LinkedList是非同步的狸驳；

? ? ? ? ? ?2.不同位置添加數(shù)據(jù)方法：鏈頭插入预明，鏈尾插入，節(jié)點(diǎn)前插入耙箍，節(jié)點(diǎn)后插入撰糠；

? ? ? ? ? ?3.雙向鏈表查詢數(shù)據(jù)：從前往后，從后往前

? ? ? ? ? ?4.適合插入刪除操作（修改元素中指針）辩昆；

缺點(diǎn)：鏈表中的元素在內(nèi)存中不是順序存儲(chǔ)的阅酪，而是通過存在元素中的指針聯(lián)系到一起。訪問時(shí)需要從第一個(gè)元素開始汁针，直到需要的元素粘秆。

? ? ? ? ? ? （get方法是通過遍歷來實(shí)現(xiàn)的）

相比ArrayList插入刪除：1.linkedList不需要執(zhí)行元素拷貝動(dòng)作岂丘，沒有牽一發(fā)而動(dòng)全身的大動(dòng)作镜悉；

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2.查找插入位置有加速動(dòng)作即：若index < 雙向鏈表長度的1/2喘沿，則從前向后查找; 否則，從后向前查找猾骡；

LinkedList 源碼解析

Vector（ 線程安全 ）

簡介：Vector是線程安全的動(dòng)態(tài)數(shù)組瑞躺，它的操作與ArrayList幾乎一樣。

Vector源碼解析

Vector與ArrayList的比較：

Vector與ArrayList的比較

Stack （?線程安全?）

簡介：Stack繼承自Vector兴想，實(shí)現(xiàn)一個(gè)后進(jìn)先出的堆棧隘蝎。

特點(diǎn)：1.Stack提供5個(gè)額外的方法使得Vector得以被當(dāng)作堆棧使用，剛創(chuàng)建后是空棧襟企；

? ? ? ? ? ?2.push嘱么，pop，peek（獲取棧頂元素）顽悼，empty（檢測堆棧是否為空）曼振，search（檢測元素在堆棧中位置）；

詳細(xì)介紹

遍歷List

幾種遍歷方法