鏈表（linked list）是一種線性表涌攻，但是并不會(huì)在物理存儲(chǔ)上按照線性順序存儲(chǔ)數(shù)據(jù)崖堤，而是在每一個(gè)節(jié)點(diǎn)里存到下一個(gè)節(jié)點(diǎn)的指針郑气。由于不必須按照順序存儲(chǔ)，所以說鏈表的插入和刪除操作可以達(dá)到O（1）的復(fù)雜度揽乱。這一篇文章我們將講一下單向鏈表和雙向鏈表，并且其中雙向鏈表會(huì)給出關(guān)鍵的代碼來加以解釋粟矿。

1：?jiǎn)蜗蜴湵?/p>

單鏈表是鏈表的一種凰棉，它是由節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)都包含著下一個(gè)節(jié)點(diǎn)的指針陌粹，下圖就是一個(gè)單鏈表撒犀，表頭為空，表頭的后繼結(jié)點(diǎn)是“節(jié)點(diǎn)10”（數(shù)據(jù)為10的節(jié)點(diǎn)）,”節(jié)點(diǎn)10”的后繼結(jié)點(diǎn)是“節(jié)點(diǎn)20”（數(shù)據(jù)為20 ）。或舞。荆姆。。映凳。胆筒。

2：?jiǎn)捂湵韯h除節(jié)點(diǎn)

我們現(xiàn)在來看一下單鏈表刪除節(jié)點(diǎn)的操作，比如說下面這個(gè)單鏈表中我們要?jiǎng)h除節(jié)點(diǎn)“30”

刪除之前：“節(jié)點(diǎn)20”的后繼結(jié)點(diǎn)為“節(jié)點(diǎn)30”诈豌，而"節(jié)點(diǎn)30" 的后繼節(jié)點(diǎn)為"節(jié)點(diǎn)40"腐泻。

刪除之后："節(jié)點(diǎn)20" 的后繼節(jié)點(diǎn)為"節(jié)點(diǎn)40"。

3：?jiǎn)捂湵硖砑庸?jié)點(diǎn)

我們?cè)賮砜纯磫捂湵硖砑庸?jié)點(diǎn)的操作队询，比如說下面這個(gè)單鏈表中我們?cè)?節(jié)點(diǎn)10"與"節(jié)點(diǎn)20"之間添加"節(jié)點(diǎn)15"

添加之前："節(jié)點(diǎn)10" 的后繼節(jié)點(diǎn)為"節(jié)點(diǎn)20"派桩。

添加之后："節(jié)點(diǎn)10" 的后繼節(jié)點(diǎn)為"節(jié)點(diǎn)15"，而"節(jié)點(diǎn)15" 的后繼節(jié)點(diǎn)為"節(jié)點(diǎn)20"蚌斩。

4：雙向鏈表

雙向鏈表(雙鏈表)是鏈表的一種铆惑。和單鏈表一樣，雙鏈表也是由節(jié)點(diǎn)組成送膳，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針员魏，分別指向直接后繼和直接前驅(qū)。所以叠聋，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開始撕阎，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。一般我們都構(gòu)造雙向循環(huán)鏈表碌补。

雙鏈表的示意圖如下：

表頭為空虏束，表頭的后繼節(jié)點(diǎn)為"節(jié)點(diǎn)10"(數(shù)據(jù)為10的節(jié)點(diǎn))；"節(jié)點(diǎn)10"的后繼節(jié)點(diǎn)是"節(jié)點(diǎn)20"(數(shù)據(jù)為10的節(jié)點(diǎn))厦章，"節(jié)點(diǎn)20"的前繼節(jié)點(diǎn)是"節(jié)點(diǎn)10"镇匀；"節(jié)點(diǎn)20"的后繼節(jié)點(diǎn)是"節(jié)點(diǎn)30"，"節(jié)點(diǎn)30"的前繼節(jié)點(diǎn)是"節(jié)點(diǎn)20"袜啃；...汗侵；末尾節(jié)點(diǎn)的后繼節(jié)點(diǎn)是表頭。

不難看出群发，雙向鏈表的節(jié)點(diǎn)定義可以用一個(gè)下面的結(jié)構(gòu)體表示：

5：雙向鏈表刪除節(jié)點(diǎn)

我們看看雙向鏈表刪除節(jié)點(diǎn)的操作晰韵，比如說下面這個(gè)單鏈表中我們要?jiǎng)h除"節(jié)點(diǎn)30"。

刪除之前："節(jié)點(diǎn)20"的后繼節(jié)點(diǎn)為"節(jié)點(diǎn)30"熟妓，"節(jié)點(diǎn)30" 的前繼節(jié)點(diǎn)為"節(jié)點(diǎn)20"雪猪。"節(jié)點(diǎn)30"的后繼節(jié)點(diǎn)為"節(jié)點(diǎn)40"，"節(jié)點(diǎn)40" 的前繼節(jié)點(diǎn)為"節(jié)點(diǎn)30"滑蚯。

刪除之后："節(jié)點(diǎn)20"的后繼節(jié)點(diǎn)為"節(jié)點(diǎn)40"浪蹂，"節(jié)點(diǎn)40" 的前繼節(jié)點(diǎn)為"節(jié)點(diǎn)20"抵栈。

雙向鏈表刪除節(jié)點(diǎn)的關(guān)鍵代碼如下：

6：雙向鏈表添加節(jié)點(diǎn)

我們?cè)賮砜纯措p向鏈表添加節(jié)點(diǎn)的操作，比如說下面這個(gè)雙向鏈表在"節(jié)點(diǎn)10"與"節(jié)點(diǎn)20"之間添加"節(jié)點(diǎn)15"

添加之前："節(jié)點(diǎn)10"的后繼節(jié)點(diǎn)為"節(jié)點(diǎn)20"坤次，"節(jié)點(diǎn)20" 的前繼節(jié)點(diǎn)為"節(jié)點(diǎn)10"古劲。

添加之后："節(jié)點(diǎn)10"的后繼節(jié)點(diǎn)為"節(jié)點(diǎn)15"，"節(jié)點(diǎn)15" 的前繼節(jié)點(diǎn)為"節(jié)點(diǎn)10"缰猴。"節(jié)點(diǎn)15"的后繼節(jié)點(diǎn)為"節(jié)點(diǎn)20"产艾，"節(jié)點(diǎn)20" 的前繼節(jié)點(diǎn)為"節(jié)點(diǎn)15"。

以后這一系列的文章我將會(huì)持續(xù)的轉(zhuǎn)載更新滑绒，這篇文章是來自上善若水闷堡，也歡迎大家關(guān)注他的公眾號(hào)：碼農(nóng)有道，讓我們一起進(jìn)步吧