Linkedlist 概述
Linkedlist集合 底層試下你的數(shù)據(jù)結(jié)構(gòu)是雙向鏈表（hashmap中的鏈表結(jié)構(gòu)是單向鏈表），linkedlist集合中允許元素為null（arrayList中也允許元素為空，但是hashmap中只允許有一個(gè)元素為空，并且一定存放在第一個(gè)桶內(nèi)）,Likedlist由于實(shí)現(xiàn)了List接口，所以其是允許存入重復(fù)的元素的，但是set集合就不允許元素重復(fù)。LinkedList不是線程安全的，ArrayList也不是線程安全的，hashmap也不是線程安全的。既然聊到了線程不安全的問(wèn)題，那就聊一下copyonwrite思想吧。
Copyonwrite
寫入時(shí)復(fù)制（CopyOnWrite）思想
寫入時(shí)復(fù)制（CopyOnWrite，簡(jiǎn)稱COW）思想是計(jì)算機(jī)程序設(shè)計(jì)領(lǐng)域中的一種優(yōu)化策略。其核心思想是，如果有多個(gè)調(diào)用者（Callers）同時(shí)要求相同的資源（如內(nèi)存或者是磁盤上的數(shù)據(jù)存儲(chǔ)），他們會(huì)共同獲取相同的指針指向相同的資源，直到某個(gè)調(diào)用者視圖修改資源內(nèi)容時(shí)，系統(tǒng)才會(huì)真正復(fù)制一份專用副本（private copy）給該調(diào)用者，而其他調(diào)用者所見到的最初的資源仍然保持不變。這過(guò)程對(duì)其他的調(diào)用者都是透明的（transparently）。此做法主要的優(yōu)點(diǎn)是如果調(diào)用者沒(méi)有修改資源，就不會(huì)有副本（private copy）被創(chuàng)建，因此多個(gè)調(diào)用者只是讀取操作時(shí)可以共享同一份資源。
（通俗點(diǎn)就是讀的時(shí)候沒(méi)有變化，改的時(shí)候負(fù)責(zé)原來(lái)的數(shù)據(jù)，然后再副本里面修改，再將原數(shù)據(jù)指向副本中去）
我們可以看到，在set方法中，我們首先是獲得了當(dāng)前數(shù)組的一個(gè)拷貝獲得一個(gè)新的數(shù)組，然后在這個(gè)新的數(shù)組上完成我們想要的操作。當(dāng)操作完成之后，再把原有數(shù)組的引用指向新的數(shù)組。并且在此過(guò)程中，我們只擁有一個(gè)事實(shí)不可變對(duì)象，即容器中的array。這樣一來(lái)就很巧妙地體現(xiàn)了CopyOnWrite思想。其實(shí)這也是讀寫分離的一種體現(xiàn)。當(dāng)線程在對(duì)線程進(jìn)行讀或者寫的操作時(shí)，其實(shí)操作的是不同的容器。這么一來(lái)我們可以對(duì)容器進(jìn)行并發(fā)的讀，而不需要加鎖。
（證明了在讀的時(shí)候不需要加鎖，但是在寫的時(shí)候是有鎖的，重入鎖）
LinkedList 雙向鏈表實(shí)現(xiàn)及成員變量
LinkedList中為什么要有first,last呢?其實(shí)就是雙向鏈表的首尾結(jié)點(diǎn)。然后我們知道鏈表的查詢速度較慢，但是引入了尾結(jié)點(diǎn)的話，我們可以根據(jù)index的大小進(jìn)行二分查找。size記錄著其中的元素總數(shù)。
LinkedList作為stack,queue使用
由于linkedlist實(shí)現(xiàn)了queue接口，所以他可以作為隊(duì)列來(lái)使用，隊(duì)列使用的是先進(jìn)先出原則，所以我們可以看到linkedlist中有比如offer,add等等的接口，但是呢offer接口插入時(shí)，如果已經(jīng)滿了不會(huì)報(bào)錯(cuò)，只會(huì)返回fase。但是add會(huì)報(bào)錯(cuò)，我們實(shí)現(xiàn)隊(duì)列這種接口的時(shí)候也要按照約定，返回fasle，而不是直接報(bào)錯(cuò)，類似的還有remove和poll等等。
ArrayList和LinkedList區(qū)別
? 1. ArrayList是實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，而LinkedList是基于鏈表的數(shù)據(jù)結(jié)構(gòu)；
?? 2.?對(duì)于隨機(jī)訪問(wèn)get和set，ArrayList要優(yōu)于LinkedList，因?yàn)長(zhǎng)inkedList要移動(dòng)指針；
（數(shù)組的存儲(chǔ)是內(nèi)存連續(xù)的，然而鏈表的并不是連續(xù)的）
??? 3.?對(duì)于添加和刪除操作add和remove，一般大家都會(huì)說(shuō)LinkedList要比ArrayList快，因?yàn)锳rrayList要移動(dòng)數(shù)據(jù)。但是實(shí)際情況并非這樣，對(duì)于添加或刪除，LinkedList和ArrayList并不能明確說(shuō)明誰(shuí)快誰(shuí)慢，下面會(huì)詳細(xì)分析。
從源碼可以看出，ArrayList想要get(int index)元素時(shí)，直接返回index位置上的元素，而LinkedList需要通過(guò)for循環(huán)進(jìn)行查找，雖然LinkedList已經(jīng)在查找方法上做了優(yōu)化，比如index < size / 2，則從左邊開始查找，反之從右邊開始查找，但是還是比ArrayList要慢。這點(diǎn)是毋庸置疑的。ArrayList想要在指定位置插入或刪除元素時(shí)，主要耗時(shí)的是System.arraycopy動(dòng)作，會(huì)移動(dòng)index后面所有的元素；LinkedList主耗時(shí)的是要先通過(guò)for循環(huán)找到index，然后直接插入或刪除。
???? 當(dāng)數(shù)據(jù)量較小時(shí)，測(cè)試程序中，大約小于30的時(shí)候，兩者效率差不多，沒(méi)有顯著區(qū)別；當(dāng)數(shù)據(jù)量較大時(shí)，大約在容量的1/10處開始，LinkedList的效率就開始沒(méi)有ArrayList效率高了，特別到一半以及后半的位置插入時(shí)，LinkedList效率明顯要低于ArrayList，而且數(shù)據(jù)量越大，越明顯。
