鏈表又稱單鏈表、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，用于存儲(chǔ)邏輯關(guān)系為“一對(duì)一”的數(shù)據(jù)。

和順序表不同，使用鏈表存儲(chǔ)數(shù)據(jù)，不強(qiáng)制要求數(shù)據(jù)在內(nèi)存中集中存儲(chǔ)，各個(gè)元素可以分散存儲(chǔ)在內(nèi)存中。例如，使用鏈表存儲(chǔ) {1,2,3}，各個(gè)元素在內(nèi)存中的存儲(chǔ)狀態(tài)可能是：

可以看到，數(shù)據(jù)不僅沒有集中存放，在內(nèi)存中的存儲(chǔ)次序也是混亂的。那么，鏈表是如何存儲(chǔ)數(shù)據(jù)間邏輯關(guān)系的呢？

鏈表存儲(chǔ)數(shù)據(jù)間邏輯關(guān)系的實(shí)現(xiàn)方案是：為每一個(gè)元素配置一個(gè)指針，每個(gè)元素的指針都指向自己的直接后繼元素，如下圖所示：

顯然，我們只需要記住元素 1 的存儲(chǔ)位置，通過它的指針就可以找到元素 2，通過元素 2 的指針就可以找到元素 3，以此類推，各個(gè)元素的先后次序一目了然。

像圖 2 這樣，數(shù)據(jù)元素隨機(jī)存儲(chǔ)在內(nèi)存中，通過指針維系數(shù)據(jù)之間“一對(duì)一”的邏輯關(guān)系，這樣的存儲(chǔ)結(jié)構(gòu)就是鏈表。

結(jié)點(diǎn)（節(jié)點(diǎn)）

很多教材中，也將“結(jié)點(diǎn)”寫成“節(jié)點(diǎn)”，它們是一個(gè)意思。

在鏈表中，每個(gè)數(shù)據(jù)元素都配有一個(gè)指針，這意味著，鏈表上的每個(gè)“元素”都長(zhǎng)下圖這個(gè)樣子：

數(shù)據(jù)域用來存儲(chǔ)元素的值，指針域用來存放指針。數(shù)據(jù)結(jié)構(gòu)中，通常將圖 3 這樣的整體稱為結(jié)點(diǎn)。

也就是說，鏈表中實(shí)際存放的是一個(gè)一個(gè)的結(jié)點(diǎn)，數(shù)據(jù)元素存放在各個(gè)結(jié)點(diǎn)的數(shù)據(jù)域中。舉個(gè)簡(jiǎn)單的例子，圖 2 中 {1,2,3} 的存儲(chǔ)狀態(tài)用鏈表表示，如下圖所示：

在 C 語言中，可以用結(jié)構(gòu)體表示鏈表中的結(jié)點(diǎn)，例如：

我們習(xí)慣將結(jié)點(diǎn)中的指針命名為 next，因此指針域又常稱為“Next 域”。?

頭結(jié)點(diǎn)、頭指針和首元結(jié)點(diǎn)

圖 4 所示的鏈表并不完整，一個(gè)完整的鏈表應(yīng)該由以下幾部分構(gòu)成：

1. 頭指針：一個(gè)和結(jié)點(diǎn)類型相同的指針，它的特點(diǎn)是：永遠(yuǎn)指向鏈表中的第一個(gè)結(jié)點(diǎn)。上文提到過，我們需要記錄鏈表中第一個(gè)元素的存儲(chǔ)位置，就是用頭指針實(shí)現(xiàn)。

2. 結(jié)點(diǎn)：鏈表中的節(jié)點(diǎn)又細(xì)分為頭結(jié)點(diǎn)、首元結(jié)點(diǎn)和其它結(jié)點(diǎn)：

• 頭結(jié)點(diǎn)：某些場(chǎng)景中，為了方便解決問題，會(huì)故意在鏈表的開頭放置一個(gè)空結(jié)點(diǎn)，這樣的結(jié)點(diǎn)就稱為頭結(jié)點(diǎn)。也就是說，頭結(jié)點(diǎn)是位于鏈表開頭、數(shù)據(jù)域?yàn)榭眨ú焕茫┑慕Y(jié)點(diǎn)。

• 首元結(jié)點(diǎn)：指的是鏈表開頭第一個(gè)存有數(shù)據(jù)的結(jié)點(diǎn)。

• 其他節(jié)點(diǎn)：鏈表中其他的節(jié)點(diǎn)。

也就是說，一個(gè)完整的鏈表是由頭指針和諸多個(gè)結(jié)點(diǎn)構(gòu)成的。每個(gè)鏈表都必須有頭指針，但頭結(jié)點(diǎn)不是必須的。

例如，創(chuàng)建一個(gè)包含頭結(jié)點(diǎn)的鏈表存儲(chǔ) {1,2,3}，如下圖所示：

再次強(qiáng)調(diào)，頭指針永遠(yuǎn)指向鏈表中的第一個(gè)結(jié)點(diǎn)。換句話說，如果鏈表中包含頭結(jié)點(diǎn)，那么頭指針指向的是頭結(jié)點(diǎn)，反之頭指針指向首元結(jié)點(diǎn)。

鏈表的創(chuàng)建

創(chuàng)建一個(gè)鏈表，實(shí)現(xiàn)步驟如下：

1. 定義一個(gè)頭指針；

2. 創(chuàng)建一個(gè)頭結(jié)點(diǎn)或者首元結(jié)點(diǎn)，讓頭指針指向它；

3. 每創(chuàng)建一個(gè)結(jié)點(diǎn)，都令其直接前驅(qū)結(jié)點(diǎn)的指針指向它。

例如，創(chuàng)建一個(gè)存儲(chǔ) {1,2,3,4} 且無頭節(jié)點(diǎn)的鏈表，C 語言實(shí)現(xiàn)代碼為：

再比如，創(chuàng)建一個(gè)存儲(chǔ) {1,2,3,4} 且含頭節(jié)點(diǎn)的鏈表，則 C 語言實(shí)現(xiàn)代碼為：

鏈表的使用

對(duì)于創(chuàng)建好的鏈表，我們可以依次獲取鏈表中存儲(chǔ)的數(shù)據(jù)，例如：

0 1 2 3 4

如果不想輸出頭結(jié)點(diǎn)的值，可以將 p->next 作為實(shí)參傳遞給 display() 函數(shù)。

如果程序中創(chuàng)建的是不帶頭結(jié)點(diǎn)的鏈表，最終的輸出結(jié)果應(yīng)該是：

1 2 3 4