鏈表：通過“指針”將零散的內(nèi)存塊聯(lián)系起來。
常見鏈表結構：單鏈表、循環(huán)鏈表和雙鏈表。

單鏈表

1.頭結點記錄鏈表基地址。
2.尾結點指向空地址NULL。

單鏈表.jpg

對比數(shù)組學習單鏈表

1.數(shù)組插入、刪除（在保證內(nèi)存數(shù)據(jù)連續(xù)性的情況下）需要數(shù)據(jù)搬移時間復雜度O(n)。
2.鏈表插入刪除如上圖所示，只需要考慮相鄰指針的改變時間復雜度為O(1)。
3.隨機訪問某個位置的元素鏈表沒數(shù)組高效。需要遍歷結點。使勁按復雜度數(shù)組時O(1)，鏈表是O(n)。
4.數(shù)組采用連續(xù)的內(nèi)存空間，可借助CPU的緩存機制，預讀數(shù)據(jù)，這樣效率更高，而鏈表是不連續(xù)的，沒法有效預讀。
5.數(shù)組申請空間過大，可能出現(xiàn)OutOfMemeory。過小，需要重新申請更大內(nèi)存，拷貝原數(shù)組，費時。 
6.鏈表天然支持動態(tài)擴容沒大小限制。這和數(shù)組區(qū)別很大。
7.鏈表更適合插入刪除操作頻繁的場景。
7.對鏈表頻繁的插入刪除操作會導致內(nèi)存申請和釋放，造成內(nèi)存碎片化。在java中可能會頻繁導致GC。

循環(huán)鏈表

在單鏈表基礎上尾結點指針指向頭結點。

循環(huán)鏈表.png

雙向鏈表

對比單鏈表學習雙向鏈表

1.雙向鏈表有前驅和后繼兩個指針。單鏈表沒有前驅。
2.雙向鏈表比單鏈表所以內(nèi)存空間更大。
3.雙向鏈表支持雙向遍歷。
4.雙向鏈表找到前驅時間復雜度O(1)。

雙向鏈表.png

對比單鏈表和雙向鏈表的插入刪除操作。

刪除操作（雙鏈表有優(yōu)勢的地方）：

1.刪除結點中“等于某個給定值的結點”。
      單鏈表和雙鏈表都需要從頭結點依次遍歷，直到找到給定值的結點。然后刪除。時間復雜度O(n)。
2.刪除給定指針指向的結點。
      刪除某個結點要獲取其前驅結點，然而單鏈表需要從頭遍歷找到，直到p->next=q，才找到，而雙鏈表有前驅結點的信息。所以這種情況下單鏈表刪除時間復雜度為O(n)（查詢加刪除）。雙鏈表時間復雜度則為O(1)。

總結：在某個指定結點前面刪除結點雙鏈表比單鏈表有很大優(yōu)勢。同理，插入數(shù)據(jù)也是這樣。

查詢操作（雙鏈表優(yōu)勢的地方---特殊場景）

1.對于有序鏈表，進行查詢操作，可以記錄上次查找的位置p,每次查找都根據(jù)要查找的值與p的大小關系，覺得往前還是往后查找，能減少一半的查詢量。java中l(wèi)inkedHashMap就用到了雙向鏈表這種結構。

經(jīng)典應用方式：頁面置換算法。

LRU頁面置換算法.png

實現(xiàn)思路：

1.基于有序單鏈表。
2.如果此數(shù)據(jù)之前已經(jīng)被緩存在鏈表中了，我們遍歷得到這個數(shù)據(jù)對應的結點，并將其從原來的位置刪除，然后再插入到鏈表的頭部。
3. 如果此數(shù)據(jù)沒有在緩存鏈表中：
   如果此時緩存未滿，則將此結點直接插入到鏈表的頭部；
   如果此時緩存已滿，則鏈表尾結點刪除，將新的數(shù)據(jù)結點插入鏈表的頭部。

總結：基于這種鏈表，緩存訪問的時間復雜度為O(n)。引入散列表可降低時間復雜度為O(1)。基于數(shù)組也能實現(xiàn)。

鏈表相關code：https://github.com/wangzheng0822/algo/tree/master/java/06_linkedlist

鏈表練習題java版：

1.單鏈表反轉：https://blog.csdn.net/lwkrsa/article/details/82015364
2.鏈表中環(huán)的檢測：https://blog.csdn.net/wanf425/article/details/83048761
3.兩個有序鏈表合并：https://blog.csdn.net/o9109003234/article/details/84245783
4.刪除鏈表中倒數(shù)第n個結點：https://blog.csdn.net/qq_38640439/article/details/81842754
5.求鏈表的中間結點：https://www.taowong.com/blog/2018/10/20/data-strutctures-and-algorithm-05.html