LinkedList作為ArrayList的老弟，也繼承了父親List的特點(diǎn):有序，允許存null值，允許重復(fù)值。和大哥ArrayList相比，LinkedList底層靠鏈表存儲(chǔ)元素，不用考慮數(shù)組擴(kuò)容，刪除插入元素所帶來的資源消耗的問題。但在訪問元素上就沒有數(shù)組直接通過索引這么方便了，大家根據(jù)不同的業(yè)務(wù)場(chǎng)景來選擇不同的集合。那什么又是鏈表呢？ 

沒錯(cuò)，這就是鏈表!!!

同事之間靠自己的手抓住下一個(gè)同事的肩膀來構(gòu)成關(guān)系。跑到天涯海角，都能找到你。鏈表中的每一個(gè)節(jié)點(diǎn)靠記錄上一個(gè)/下一個(gè)節(jié)點(diǎn)位于內(nèi)存中的地址來維護(hù)節(jié)點(diǎn)之間的關(guān)系，節(jié)點(diǎn)在內(nèi)存中的位置也可以是不固定，分散的，這點(diǎn)和數(shù)組不同。

插入節(jié)點(diǎn)

當(dāng)有新的同事插入隊(duì)列時(shí)，需要從第一個(gè)同事開始一直向下找到想要插隊(duì)的位置，然后自己的手搭在右邊同事的肩上，再將左邊同事的手搭在自己肩膀上，就入隊(duì)成功了。有同事出隊(duì)也一樣。

比如有同事插隊(duì)到第四個(gè)位置去：

插入刪除元素，需要從第一個(gè)元素開始一直向下找到該位置上的節(jié)點(diǎn)再做操作。和數(shù)組比較起來，數(shù)組是犧牲時(shí)間和空間，而鏈表是犧牲時(shí)間，最壞從第一個(gè)找到最后一個(gè)時(shí)間復(fù)雜度O(n)。對(duì)于鏈表節(jié)點(diǎn)會(huì)多使用內(nèi)存的情況，個(gè)人認(rèn)為單向鏈表需要多使用一塊內(nèi)存來記錄下一個(gè)節(jié)點(diǎn)的位置，而數(shù)組本身也是存儲(chǔ)記錄對(duì)象的內(nèi)存地址的，個(gè)人覺得兩者相比并沒有誰更節(jié)約。歡迎大家提出自己的看法。

雙向鏈表

刪除和插入元素都需要從第一個(gè)開始向下尋找，當(dāng)元素越來越多時(shí)，性能肯定會(huì)越來越不好。上面新同事插隊(duì)到以四個(gè)位置，如果從最后一個(gè)同事開始向前找位置，會(huì)快跟多。問題的根本在于，每個(gè)節(jié)點(diǎn)只記錄下一個(gè)節(jié)點(diǎn)的位置。節(jié)點(diǎn)只能找到自己后面的節(jié)點(diǎn)，找不到自己前面的節(jié)點(diǎn)。所以前輩們又發(fā)明了雙向鏈表:節(jié)點(diǎn)之間緊緊相扣。

同時(shí)每個(gè)節(jié)點(diǎn)還需要一塊空間來記錄前面節(jié)點(diǎn)的位置。LinkedList底層就是用雙向鏈表來實(shí)現(xiàn)的。

插入刪除元素時(shí)，會(huì)根據(jù)索引的位置，優(yōu)先選擇是從頭開始還是從尾開始找。最壞次數(shù)，當(dāng)前鏈表大小的一半，當(dāng)然這是犧牲些許內(nèi)存所換來的。

當(dāng)需要插入元素時(shí)，只需要： 
1.找到該位置上的節(jié)點(diǎn)

2.插入節(jié)點(diǎn)的前驅(qū)為該位置節(jié)點(diǎn)的前驅(qū)，插入節(jié)點(diǎn)的后驅(qū)為該位置節(jié)點(diǎn)

3.該位置的前驅(qū)節(jié)點(diǎn)的next指向插入節(jié)點(diǎn)

4.該位置節(jié)點(diǎn)的pre指向插入節(jié)點(diǎn)

刪除元素也一樣： 

1.找到該位置上的節(jié)點(diǎn)

2.將該位置節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的next，指向該位置節(jié)點(diǎn)的后驅(qū)節(jié)點(diǎn)

3.將該位置節(jié)點(diǎn)的后驅(qū)節(jié)點(diǎn)的pre，指向該位置節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)

1.和ArrayList相比不用考慮擴(kuò)容問題 。

2.刪除和插入節(jié)點(diǎn)會(huì)消耗時(shí)間，優(yōu)于ArrayList的消耗時(shí)間和空間。 
3.訪問元素慢于ArrayList。 

不足之處多多包涵。