鏈表的定義
鏈表是數(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ù)時需要改變更多指針的指向捉撮。
