鏈表的定義
鏈表是數(shù)據(jù)結(jié)構(gòu)之一，其中的數(shù)據(jù)呈線性排列。在鏈表中，數(shù)據(jù)的添加和刪除都較為方便，就是訪問比較耗費時間。
-
這就是鏈表的概念圖。Blue、Yellow、Red 這 3 個字符串作為數(shù)據(jù)被存儲于鏈表中。每個數(shù)據(jù)都有 1 個“指針”，它指向下一個數(shù)據(jù)的內(nèi)存地址。
image.png -
在鏈表中，數(shù)據(jù)一般都是分散存儲于內(nèi)存中的，無須存儲在連續(xù)空間內(nèi)。
image.png -
因為數(shù)據(jù)都是分散存儲的，所以如果想要訪問數(shù)據(jù)，只能從第 1個數(shù)據(jù)開始，順著指針的指向一一往下訪問（這便是順序訪問）。比如，想要找到 Red這一數(shù)據(jù)，就得從 Blue開始訪問。
image.png -
這之后，還要經(jīng)過 Yellow，我們才能找到 Red。
image.png -
如果想要添加數(shù)據(jù)，只需要改變添加位置前后的指針指向就可以，非常簡單。比如，在 Blue和 Yellow 之間添加 Green。
image.png -
將 Blue的指針指向的位置變成 Green，然后再把 Green的指針指向 Yellow，數(shù)據(jù)的添加就大功告成了
image.png -
數(shù)據(jù)的刪除也一樣，只要改變指針的指向就可以，比如刪除 Yellow。
image.png -
只需要把 Green指針指向的位置從 Yellow變成 Red，刪除就完成了。
image.png
對鏈表的操作所需的運行時間到底是多少呢？在這里，我們把鏈表中的數(shù)據(jù)量記成n。訪問數(shù)據(jù)時，我們需要從鏈表頭部開始查找（線性查找），如果目標(biāo)數(shù)據(jù)在鏈表最后的話，需要的時間就是 O(n)。
另外，添加數(shù)據(jù)只需要更改兩個指針的指向，所以耗費的時間與 n 無關(guān)。如果已經(jīng)到達(dá)了添加數(shù)據(jù)的位置，那么添加操作只需花費 O(1) 的時間。刪除數(shù)據(jù)同樣也只需O(1) 的時間。
鏈表的分類
-
循環(huán)鏈表，也叫環(huán)形鏈表。
image.png
我們也可以在鏈表尾部使用指針，并且讓它指向鏈表頭部的數(shù)據(jù)，將鏈表變成環(huán)形。
-
雙向鏈表
image.png
上文鏈表里的每個數(shù)據(jù)都只有一個指針，但我們可以把指針設(shè)定為兩個，并且讓它們分別指向前后數(shù)據(jù)，這就是“雙向鏈表”。使用這種鏈表，不僅可以從前往后，還可以從后往前遍歷數(shù)據(jù)，十分方便。
但是，雙向鏈表存在兩個缺點：一是指針數(shù)的增加會導(dǎo)致存儲空間需求增加；二是添加和刪除數(shù)據(jù)時需要改變更多指針的指向。
