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

沒錯，這就是鏈表!!!

同事之間靠自己的手抓住下一個同事的肩膀來構(gòu)成關(guān)系。跑到天涯海角，都能找到你。鏈表中的每一個節(jié)點(diǎn)靠記錄上一個/下一個節(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ì)列時，需要從第一個同事開始一直向下找到想要插隊(duì)的位置，然后自己的手搭在右邊同事的肩上，再將左邊同事的手搭在自己肩膀上，就入隊(duì)成功了。有同事出隊(duì)也一樣。

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

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

雙向鏈表

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

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

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

當(dāng)需要插入元素時，只需要： 
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)會消耗時間，優(yōu)于ArrayList的消耗時間和空間。 
3.訪問元素慢于ArrayList。 

不足之處多多包涵。