資訊專欄INFORMATION COLUMN
摘要：底層使用的是雙向鏈表數(shù)據(jù)結(jié)構(gòu)之前為循環(huán)鏈表，取消了循環(huán)?？焖匐S機(jī)訪問就是通過元素的序號快速獲取元素對象對應(yīng)于方法。而接口就是用來標(biāo)識該類支持快速隨機(jī)訪問。僅僅是起標(biāo)識作用。，中文名為雙端隊列。不同的是，是線程安全的，內(nèi)部使用了進(jìn)行同步。
前言
學(xué)習(xí)情況記錄
時間：week 2
SMART子目標(biāo) ：Java 容器
記錄在學(xué)習(xí)Java容器 知識點中，關(guān)于List的需要重點記錄的知識點。
知識點概覽：
ArrayList 與 LinkedList對比
ArrayList 中的 RandomAccess 接口 是什么？
LinkedList 中的 Deque 接口 是什么？
老調(diào)常談 之 ArrayList 擴(kuò)容機(jī)制
ArrayList 與 Vector 對比
ArrayList 與 LinkedList對比
底層數(shù)據(jù)結(jié)構(gòu)：
ArrayList 底層使用的Object數(shù)組，默認(rèn)大小 10。
**
LinkedList 底層使用的是雙向鏈表數(shù)據(jù)結(jié)構(gòu)（JDK1.6之前為循環(huán)鏈表，JDK1.7取消了循環(huán)。注意雙向鏈表和雙向循環(huán)鏈表的區(qū)別）。LinkedList 包含了3個重要的成員：size、first、last。size是雙向鏈表中節(jié)點的個數(shù)，first和last分別指向第一個和最后一個節(jié)點的引用。
插入和刪除是否受元素位置的影響：
由于底層實現(xiàn)的影響，ArrayList 采用數(shù)組存儲，所以插入和刪除元素的時間復(fù)雜度受元素位置的影響。比如：執(zhí)行add(E e)方法的時候， ArrayList 會默認(rèn)在將指定的元素追加到此列表的末尾，這種情況時間復(fù)雜度就是O(1)。但是如果要在指定位置 i 插入和刪除元素的話（add(int index, E element)）時間復(fù)雜度就為 O(n-i)。因為在進(jìn)行上述操作的時候集合中第 i 和第 i 個元素之后的(n-i)個元素都要執(zhí)行向后位/向前移一位的操作。實際就是近似O(n)。
而LinkedList 采用鏈表存儲，所以插入，刪除元素時間復(fù)雜度不受元素位置的影響，都是近似 O（1）
是否支持快速隨機(jī)訪問：這個也是由底層實現(xiàn)決定的，LinkedList 不支持高效的隨機(jī)元素訪問，而 ArrayList 支持。快速隨機(jī)訪問就是通過元素的序號快速獲取元素對象(對應(yīng)于get(int index)方法)。
內(nèi)存空間占用：ArrayList的空間浪費主要體現(xiàn)在在list列表的結(jié)尾會預(yù)留一定的容量空間，而LinkedList的空間花費則體現(xiàn)在它的每一個元素都需要消耗比ArrayList更多的空間（因為要存放prev 指針和next 指針以及數(shù)據(jù)）。
ArrayList 中的 RandomAccess 接口 是什么？前面的圖中我們可以看到ArrayList 繼承了三個接口，后面兩個都是比較熟悉的，分別是標(biāo)識對象可復(fù)制和可序列化。
那么RandomAccess 接口代表什么呢？
前面的關(guān)于ArrayList 與 LinkedList 的對比當(dāng)中，有一點就是，
是否支持快速隨機(jī)訪問：這個也是由底層實現(xiàn)決定的，LinkedList 不支持高效的隨機(jī)元素訪問，而 ArrayList 支持。快速隨機(jī)訪問就是通過元素的序號快速獲取元素對象(對應(yīng)于get(int index)方法)。
而RandomAccess 接口 就是用來 標(biāo)識該類支持快速隨機(jī)訪問。 查看源碼可以發(fā)現(xiàn)，這個接口內(nèi)部沒有任何的定義。僅僅是起標(biāo)識作用。
比如在Collections.binarySearch()方法中，
實現(xiàn)了RandomAccess接口的List使用索引遍歷，而未實現(xiàn)RandomAccess接口的List使用迭代器遍歷。
總結(jié)一句話：實現(xiàn)RandomAccess接口的List可以通過for循環(huán)來遍歷數(shù)據(jù)比使用iterator遍歷數(shù)據(jù)更高效，未實現(xiàn)RandomAccess接口的List可以通過iterator遍歷數(shù)據(jù)比使用for循環(huán)來遍歷數(shù)據(jù)更高效。當(dāng)然對于ArrayList來說，for循環(huán)遍歷和Iterator方式遍歷差距不大，但是對于LinkedList這種沒有實現(xiàn)的來說，兩種遍歷方式效率差距就有點大了。這主要是因為底層實現(xiàn)不同。
LinkedList 中的 Deque 接口是什么？與 ArrayList 相對應(yīng)的，LinkedList 中也有一個值得好好研究的接口，那就是Deque 接口。
Deque - double-ended queue，中文名為雙端隊列。
我們都知道 Queue 是一個隊列，遵循 FIFO 準(zhǔn)則，我們也知道 Stack 是一個棧結(jié)構(gòu)，遵循 FILO 準(zhǔn)則。 而Deque 這個雙端隊列就厲害了,它既可以實現(xiàn)棧的操作，也可以實現(xiàn)隊列的操作，換句話說，實現(xiàn)了這個接口的類，既可以作為棧使用也可以作為隊列使用。
如何作為隊列使用呢？ Deque 實現(xiàn)了 Queue，所以 Queue 所有的方法 Deque 都有，下面比較的是Deque區(qū)別 Queue 的方法：
| Queue | Deque |
|---|---|
| add(e) | addLast() |
| offer(e) | offerLast() |
| remove() | removeFirst() |
| poll() | pollFirst() |
| element() | getFirst() |
| peek() | peekFirst() |
如何作為棧使用呢？ 下面我們來看看下雙端隊列作為棧 Stack使用的時候方法對應(yīng)關(guān)系。
| Stack | Deque |
|---|---|
| push(e) | addFirst(e) |
| pop() | removeFirst() |
| peek() | peekFirst() |
因為篇幅有限，具體實現(xiàn)源碼就不帶大家去分析了。
引一篇好文：搞懂 Java LinkedList 源碼
老調(diào)常談 之 ArrayList 擴(kuò)容機(jī)制這是一個很頻繁的面試點，故記錄一下。
以下是源碼部分。
從 add()方法開始入手
ensureCapacityInternal(size + 1) 確認(rèn)當(dāng)前數(shù)組可否容納 size + 1 個元素，如果不夠進(jìn)行擴(kuò)容
grow(minCapacity) 這就是具體擴(kuò)容的邏輯
新容量的大小為 oldCapacity + (oldCapacity >> 1)，也就是舊容量的1.5倍
擴(kuò)容操作 需要 調(diào)用 Arrays.copyOf()這個方法，把原數(shù)組整個復(fù)制到新數(shù)組中，這個操作代價很高，所以 很多地方包括阿里開發(fā)手冊上也會建議 在集合初始化的時候就指定好大概的容量大小，減少擴(kuò)容的次數(shù)。
ArrayList 與 Vector 對比ArrayList 與 Vector 的底層實現(xiàn)都是 Object 數(shù)組，所以兩者使用和特性上非常類似。
不同的是，
Vector 是線程安全的，內(nèi)部使用了synchronized 進(jìn)行同步。這導(dǎo)致了 Vector 性能非常不好。相比較的話，推薦用ArrayList，然后自己控制同步。
Vector 每次擴(kuò)容都是2 倍大小，而不是1.5
如果是想要達(dá)到線程安全的目的，Vector 有其他的替代方案：
使用 Collections.synchronizedList() 得到一個線程安全的ArrayList（這類的Collections.synchronized*() 就是一層Wrapper，看源碼就知道了）
也可以使用J.U.C中的 CopyOnWriteArrayList 讀寫分離，后面的內(nèi)容會有詳細(xì)介紹
參考搞懂 Java LinkedList 源碼
《碼出高效》
《瘋狂Java講義》
github cs-note
java guide
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/75364.html
摘要：而在集合中，值僅僅是一個對象罷了該對象對本身而言是無用的。將這篇文章作為集合的總結(jié)篇，但覺得沒什么好寫就回答一些面試題去了，找了一會面試題又覺得不夠系統(tǒng)。 前言 聲明，本文用的是jdk1.8 花了一個星期，把Java容器核心的知識過了一遍，感覺集合已經(jīng)無所畏懼了！！(哈哈哈....)，現(xiàn)在來總結(jié)一下吧~~ 回顧目錄： Collection總覽 List集合就這么簡單【源碼剖析】 Ma...
摘要：體現(xiàn)的就是適配器模式。數(shù)組對象集合世界中的機(jī)制機(jī)制集合世界中比較常見的錯誤檢測機(jī)制，防止在對集合進(jìn)行遍歷過程當(dāng)中，出現(xiàn)意料之外的修改，會通過異常暴力的反應(yīng)出來。而在增強(qiáng)循環(huán)中，集合遍歷是通過進(jìn)行的。 前言 學(xué)習(xí)情況記錄 時間：week 2 SMART子目標(biāo) ：Java 容器 記錄在學(xué)習(xí)Java容器 知識點中，關(guān)于List的重點知識點。 知識點概覽： 容器中的設(shè)計模式 從Array...
摘要：今天主要講解的是本文力求簡單講清每個知識點，希望大家看完能有所收獲一和回顧線程安全的和我們知道是用于替代的，是線程安全的容器。使用迭代器遍歷時不需要顯示加鎖，看看與方法的實現(xiàn)可能就有點眉目了。 前言 只有光頭才能變強(qiáng) showImg(https://segmentfault.com/img/remote/1460000016931828?w=1120&h=640); 前一陣子寫過一篇C...
摘要：線程不安全底層數(shù)據(jù)結(jié)構(gòu)是鏈表。的默認(rèn)初始化容量是，每次擴(kuò)容時候增加原先容量的一半，也就是變?yōu)樵瓉淼谋秳h除元素時不會減少容量，若希望減少容量則調(diào)用它不是線程安全的。 前言 聲明，本文用得是jdk1.8 前一篇已經(jīng)講了Collection的總覽：Collection總覽，介紹了一些基礎(chǔ)知識。 現(xiàn)在這篇主要講List集合的三個子類： ArrayList 底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組。線程不安全 ...
摘要：集合中成員很豐富，常用的集合有，，等。實現(xiàn)接口的集合主要有。集合中不能包含重復(fù)的元素，每個元素必須是唯一的。而以作為實現(xiàn)的構(gòu)造函數(shù)的訪問權(quán)限是默認(rèn)訪問權(quán)限，即包內(nèi)訪問權(quán)限。與接口不同，它是由一系列鍵值對組成的集合，提供了到的映射。 原文地址 Java集合 Java集合框架：是一種工具類，就像是一個容器可以存儲任意數(shù)量的具有共同屬性的對象。 Java集合中成員很豐富，常用的集合有Arra...
閱讀 2600·2021-09-06 15:02
閱讀 3238·2021-09-02 10:18
閱讀 2852·2019-08-30 15:44
閱讀 712·2019-08-30 15:43
閱讀 1976·2019-08-30 14:08
閱讀 2787·2019-08-30 13:16
閱讀 1439·2019-08-26 13:52
閱讀 959·2019-08-26 12:21
