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