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

沒錯，這就是鏈表!!!

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

插入節(jié)點

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

比如有同事插隊到第四個位置去：

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

雙向鏈表

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

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

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

當需要插入元素時，只需要： 
1.找到該位置上的節(jié)點

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

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

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

刪除元素也一樣： 

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

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

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

1.和ArrayList相比不用考慮擴容問題 。

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

不足之處多多包涵。