鏈?zhǔn)酱鎯Y(jié)構(gòu)，又叫鏈接存儲結(jié)構(gòu)。在計算機(jī)中用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素。鏈?zhǔn)酱鎯Y(jié)構(gòu)不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲結(jié)構(gòu)所具有的弱點(diǎn),但也同時失去了順序表可隨機(jī)存取的優(yōu)點(diǎn)。

鏈?zhǔn)酱鎯Y(jié)構(gòu)一般有單鏈表、靜態(tài)鏈表、循環(huán)鏈表和雙向鏈表。下面為大家一一介紹：

1.單鏈表

n個結(jié)點(diǎn)鏈結(jié)成一個鏈表，即為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，因?yàn)榇随湵淼拿總€結(jié)點(diǎn)中只包含一個指針域，所以叫做單鏈表，單鏈表是通過每個結(jié)點(diǎn)的指針域?qū)⒕€性表的數(shù)據(jù)元素按其邏輯次序鏈接在一起。

有的鏈表是帶有頭結(jié)點(diǎn)的，有的是不包含頭結(jié)點(diǎn)的，頭節(jié)點(diǎn)的數(shù)據(jù)域可以不存儲任何信息，可以存儲線性表長度等附加信息，頭節(jié)點(diǎn)的 指針域存儲指向第一個結(jié)點(diǎn)的指針。當(dāng)鏈表是帶有頭結(jié)點(diǎn)的時候，就相當(dāng)于火車頭一樣的存在，只是用來表面列車順序開始的方向，并不乘坐客人。（鏈表一般都是包含頭結(jié)點(diǎn)的）

帶頭結(jié)點(diǎn)的單鏈表中，頭指針head指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的數(shù)據(jù)域不包含任何信息，從頭結(jié)點(diǎn)的后繼結(jié)點(diǎn)開始存儲數(shù)據(jù)信息。頭指針始終不等于NULL(指針是指指向下一個元素的的信息，當(dāng)為NULL時，即不指向任何元素)，head->next等于NULL的時候，鏈表為空。

不帶頭結(jié)點(diǎn)的單鏈表中的頭指針head直接指向開始結(jié)點(diǎn)，當(dāng)head等于NULL（head->=NULL）的時候，鏈表為空。

鏈表中整個鏈表的存取就必須從頭指針開始進(jìn)行，之后的每個結(jié)點(diǎn)就是上一個結(jié)點(diǎn)的后繼指針指向的位置，最后一個結(jié)點(diǎn)（終端結(jié)點(diǎn)）的指針為空，通常用NULL或^表示。

2.靜態(tài)鏈表

前面的單鏈表是用的指針，但是有的編程語言是沒有指針這個功能的，那怎么？聰明的人總是有，有人想出了用數(shù)組來代替指針，來描述單鏈表，讓每個數(shù)組的元素都由兩個數(shù)據(jù)域組成，數(shù)組的每個下標(biāo)都對應(yīng)兩個數(shù)據(jù)域，一個用來存放數(shù)據(jù)元素，一個用來存放next指針。我們把這種用數(shù)組描述的鏈表叫做靜態(tài)鏈表。

3.循環(huán)鏈表

將單鏈表中終端結(jié)點(diǎn)的指針端由空指針改為指向頭結(jié)點(diǎn)，就使整個單鏈表形成一個環(huán)，這種頭尾相接的單鏈表稱為單循環(huán)鏈表，簡稱循環(huán)鏈表。

4.雙向鏈表

在單鏈表的基礎(chǔ)上，再在每個結(jié)點(diǎn)中設(shè)置一個指向其前驅(qū)結(jié)點(diǎn)的指針域，這樣一個結(jié)點(diǎn)既可以指向它的前面又可以指向它的下一個，我們把這種鏈表稱為雙向鏈表。

結(jié)點(diǎn)是內(nèi)存中一片由用戶分配的存儲空間，只有一個地址用來表示它的存在，沒有顯式的名稱，因此我們會在分配鏈表結(jié)點(diǎn)空間的時候，同時定義一個指針，來存儲這片空間的地址（這個過程通俗的講叫指針指向結(jié)點(diǎn)），并且常用這個指針的名稱來作為結(jié)點(diǎn)的名稱。

鏈?zhǔn)酱鎯Y(jié)構(gòu)的出現(xiàn)實(shí)際上是為了改善順序存儲結(jié)構(gòu)的缺點(diǎn)，邏輯上相鄰的節(jié)點(diǎn)物理上不必相鄰。同時，鏈?zhǔn)酱鎯Y(jié)構(gòu)比順序存儲結(jié)構(gòu)的存儲密度小(鏈?zhǔn)酱鎯Y(jié)構(gòu)中每個結(jié)點(diǎn)都由數(shù)據(jù)域與指針域兩部分組成，相比順序存儲結(jié)構(gòu)增加了存儲空間)。本文對順序存儲結(jié)構(gòu)就不過多介紹，感興趣的小伙伴可以觀看本站的數(shù)據(jù)結(jié)構(gòu)和算法教程自主學(xué)習(xí)。