返回目錄

概況

鏈(lian)(lian)表(biao)是(shi)一種物理存(cun)儲(chu)(chu)單元上非(fei)連續、非(fei)順(shun)序(xu)的(de)存(cun)儲(chu)(chu)結(jie)構，數據(ju)元素的(de)邏輯順(shun)序(xu)是(shi)通過鏈(lian)(lian)表(biao)中的(de)指針鏈(lian)(lian)接次(ci)序(xu)實(shi)現的(de)。鏈(lian)(lian)表(biao)由一系列結(jie)點（鏈(lian)(lian)表(biao)中每一個(ge)(ge)(ge)元素稱為結(jie)點）組(zu)成，結(jie)點可以(yi)在運(yun)行時動態生成。每個(ge)(ge)(ge)結(jie)點包括兩個(ge)(ge)(ge)部分：一個(ge)(ge)(ge)是(shi)存(cun)儲(chu)(chu)數據(ju)元素的(de)數據(ju)域，另一個(ge)(ge)(ge)是(shi)存(cun)儲(chu)(chu)下一個(ge)(ge)(ge)結(jie)點地址的(de)指針域。 相比于線性表(biao)順(shun)序(xu)結(jie)構，鏈(lian)(lian)表(biao)比較(jiao)方便插(cha)入和(he)刪除操作。

鏈表(Linked list)是(shi)(shi)(shi)(shi)一(yi)(yi)種(zhong)(zhong)常見的(de)(de)(de)(de)(de)(de)(de)基(ji)礎數(shu)(shu)(shu)(shu)據(ju)結(jie)構，是(shi)(shi)(shi)(shi)一(yi)(yi)種(zhong)(zhong)線性表(biao)(biao)(biao)(biao)(biao)，但(dan)(dan)是(shi)(shi)(shi)(shi)并不(bu)會(hui)按線性的(de)(de)(de)(de)(de)(de)(de)順(shun)(shun)序存(cun)(cun)儲數(shu)(shu)(shu)(shu)據(ju)，而(er)是(shi)(shi)(shi)(shi)在(zai)(zai)每一(yi)(yi)個(ge)(ge)(ge)節(jie)(jie)點(dian)(dian)里存(cun)(cun)到(dao)下一(yi)(yi)個(ge)(ge)(ge)節(jie)(jie)點(dian)(dian)的(de)(de)(de)(de)(de)(de)(de)指針(Pointer)。由(you)(you)(you)于不(bu)必按順(shun)(shun)序存(cun)(cun)儲，鏈(lian)(lian)(lian)(lian)(lian)(lian)(lian)(lian)表(biao)(biao)(biao)(biao)(biao)在(zai)(zai)插(cha)入的(de)(de)(de)(de)(de)(de)(de)時候可(ke)以(yi)達到(dao)O(1)的(de)(de)(de)(de)(de)(de)(de)復(fu)雜度，比另一(yi)(yi)種(zhong)(zhong)線性表(biao)(biao)(biao)(biao)(biao)：順(shun)(shun)序表(biao)(biao)(biao)(biao)(biao)快得多，但(dan)(dan)是(shi)(shi)(shi)(shi)查找一(yi)(yi)個(ge)(ge)(ge)節(jie)(jie)點(dian)(dian)或(huo)者訪問特定(ding)編號的(de)(de)(de)(de)(de)(de)(de)節(jie)(jie)點(dian)(dian)則需要O(n)的(de)(de)(de)(de)(de)(de)(de)時間，而(er)順(shun)(shun)序表(biao)(biao)(biao)(biao)(biao)相應的(de)(de)(de)(de)(de)(de)(de)時間復(fu)雜度分別(bie)是(shi)(shi)(shi)(shi)O(logn)和(he)(he)O(1)。使用鏈(lian)(lian)(lian)(lian)(lian)(lian)(lian)(lian)表(biao)(biao)(biao)(biao)(biao)結(jie)構可(ke)以(yi)克服數(shu)(shu)(shu)(shu)組鏈(lian)(lian)(lian)(lian)(lian)(lian)(lian)(lian)表(biao)(biao)(biao)(biao)(biao)需要預(yu)先知道數(shu)(shu)(shu)(shu)據(ju)大(da)小(xiao)的(de)(de)(de)(de)(de)(de)(de)缺點(dian)(dian)，鏈(lian)(lian)(lian)(lian)(lian)(lian)(lian)(lian)表(biao)(biao)(biao)(biao)(biao)結(jie)構可(ke)以(yi)充分利用計算機(ji)(ji)內存(cun)(cun)空(kong)間，實(shi)現靈活的(de)(de)(de)(de)(de)(de)(de)內存(cun)(cun)動(dong)態管理。但(dan)(dan)是(shi)(shi)(shi)(shi)鏈(lian)(lian)(lian)(lian)(lian)(lian)(lian)(lian)表(biao)(biao)(biao)(biao)(biao)失(shi)去了(le)數(shu)(shu)(shu)(shu)組隨(sui)機(ji)(ji)讀取的(de)(de)(de)(de)(de)(de)(de)優(you)點(dian)(dian)，同(tong)時鏈(lian)(lian)(lian)(lian)(lian)(lian)(lian)(lian)表(biao)(biao)(biao)(biao)(biao)由(you)(you)(you)于增(zeng)加了(le)結(jie)點(dian)(dian)的(de)(de)(de)(de)(de)(de)(de)指針域，空(kong)間開銷比較大(da)。在(zai)(zai)計算機(ji)(ji)科學中，鏈(lian)(lian)(lian)(lian)(lian)(lian)(lian)(lian)表(biao)(biao)(biao)(biao)(biao)作為一(yi)(yi)種(zhong)(zhong)基(ji)礎的(de)(de)(de)(de)(de)(de)(de)數(shu)(shu)(shu)(shu)據(ju)結(jie)構可(ke)以(yi)用來生成(cheng)其它類型(xing)的(de)(de)(de)(de)(de)(de)(de)數(shu)(shu)(shu)(shu)據(ju)結(jie)構。鏈(lian)(lian)(lian)(lian)(lian)(lian)(lian)(lian)表(biao)(biao)(biao)(biao)(biao)通常由(you)(you)(you)一(yi)(yi)連串節(jie)(jie)點(dian)(dian)組成(cheng)，每個(ge)(ge)(ge)節(jie)(jie)點(dian)(dian)包(bao)含任意的(de)(de)(de)(de)(de)(de)(de)實(shi)例數(shu)(shu)(shu)(shu)據(ju)(data fields)和(he)(he)一(yi)(yi)或(huo)兩個(ge)(ge)(ge)用來指向(xiang)(xiang)明(ming)上一(yi)(yi)個(ge)(ge)(ge)/或(huo)下一(yi)(yi)個(ge)(ge)(ge)節(jie)(jie)點(dian)(dian)的(de)(de)(de)(de)(de)(de)(de)位(wei)置的(de)(de)(de)(de)(de)(de)(de)鏈(lian)(lian)(lian)(lian)(lian)(lian)(lian)(lian)接（"links"）。鏈(lian)(lian)(lian)(lian)(lian)(lian)(lian)(lian)表(biao)(biao)(biao)(biao)(biao)最明(ming)顯的(de)(de)(de)(de)(de)(de)(de)好處就是(shi)(shi)(shi)(shi)，常規數(shu)(shu)(shu)(shu)組排(pai)列(lie)(lie)關聯項目的(de)(de)(de)(de)(de)(de)(de)方式可(ke)能不(bu)同(tong)于這些數(shu)(shu)(shu)(shu)據(ju)項目在(zai)(zai)記憶體或(huo)磁盤上順(shun)(shun)序，數(shu)(shu)(shu)(shu)據(ju)的(de)(de)(de)(de)(de)(de)(de)存(cun)(cun)取往往要在(zai)(zai)不(bu)同(tong)的(de)(de)(de)(de)(de)(de)(de)排(pai)列(lie)(lie)順(shun)(shun)序中轉(zhuan)換(huan)。而(er)鏈(lian)(lian)(lian)(lian)(lian)(lian)(lian)(lian)表(biao)(biao)(biao)(biao)(biao)是(shi)(shi)(shi)(shi)一(yi)(yi)種(zhong)(zhong)自我指示數(shu)(shu)(shu)(shu)據(ju)類型(xing)，因為它包(bao)含指向(xiang)(xiang)另一(yi)(yi)個(ge)(ge)(ge)相同(tong)類型(xing)的(de)(de)(de)(de)(de)(de)(de)數(shu)(shu)(shu)(shu)據(ju)的(de)(de)(de)(de)(de)(de)(de)指針（鏈(lian)(lian)(lian)(lian)(lian)(lian)(lian)(lian)接）。鏈(lian)(lian)(lian)(lian)(lian)(lian)(lian)(lian)表(biao)(biao)(biao)(biao)(biao)允許插(cha)入和(he)(he)移除表(biao)(biao)(biao)(biao)(biao)上任意位(wei)置上的(de)(de)(de)(de)(de)(de)(de)節(jie)(jie)點(dian)(dian)，[1]但(dan)(dan)是(shi)(shi)(shi)(shi)不(bu)允許隨(sui)機(ji)(ji)存(cun)(cun)取。鏈(lian)(lian)(lian)(lian)(lian)(lian)(lian)(lian)表(biao)(biao)(biao)(biao)(biao)有很多種(zhong)(zhong)不(bu)同(tong)的(de)(de)(de)(de)(de)(de)(de)類型(xing)：單向(xiang)(xiang)鏈(lian)(lian)(lian)(lian)(lian)(lian)(lian)(lian)表(biao)(biao)(biao)(biao)(biao)，雙(shuang)向(xiang)(xiang)鏈(lian)(lian)(lian)(lian)(lian)(lian)(lian)(lian)表(biao)(biao)(biao)(biao)(biao)以(yi)及(ji)循環鏈(lian)(lian)(lian)(lian)(lian)(lian)(lian)(lian)表(biao)(biao)(biao)(biao)(biao)。鏈(lian)(lian)(lian)(lian)(lian)(lian)(lian)(lian)表(biao)(biao)(biao)(biao)(biao)可(ke)以(yi)在(zai)(zai)多種(zhong)(zhong)編程(cheng)(cheng)語言(yan)(yan)中實(shi)現。像Lisp和(he)(he)Scheme這樣的(de)(de)(de)(de)(de)(de)(de)語言(yan)(yan)的(de)(de)(de)(de)(de)(de)(de)內建數(shu)(shu)(shu)(shu)據(ju)類型(xing)中就包(bao)含了(le)鏈(lian)(lian)(lian)(lian)(lian)(lian)(lian)(lian)表(biao)(biao)(biao)(biao)(biao)的(de)(de)(de)(de)(de)(de)(de)存(cun)(cun)取和(he)(he)操作。程(cheng)(cheng)序語言(yan)(yan)或(huo)面向(xiang)(xiang)對(dui)象語言(yan)(yan)，如C,C++和(he)(he)Java依(yi)靠易變工具來生成(cheng)鏈(lian)(lian)(lian)(lian)(lian)(lian)(lian)(lian)表(biao)(biao)(biao)(biao)(biao)。

圖像

特點

的(de)(de)(de)鏈式存(cun)(cun)儲表(biao)(biao)示(shi)的(de)(de)(de)特點是(shi)用一(yi)(yi)組任(ren)意的(de)(de)(de)存(cun)(cun)儲單(dan)元(yuan)(yuan)(yuan)存(cun)(cun)儲線(xian)性表(biao)(biao)的(de)(de)(de)數(shu)據元(yuan)(yuan)(yuan)素（這組存(cun)(cun)儲單(dan)元(yuan)(yuan)(yuan)可以是(shi)連續(xu)的(de)(de)(de)，也可以是(shi)不連續(xu)的(de)(de)(de)）。因此，為了(le)表(biao)(biao)示(shi)每個數(shu)據元(yuan)(yuan)(yuan)素 與其直(zhi)接后繼數(shu)據元(yuan)(yuan)(yuan)素 之間(jian)的(de)(de)(de)邏輯關系，對數(shu)據元(yuan)(yuan)(yuan)素 來說，除了(le)存(cun)(cun)儲其本身的(de)(de)(de)信息(xi)(xi)之外(wai)，還需存(cun)(cun)儲一(yi)(yi)個指示(shi)其直(zhi)接后繼的(de)(de)(de)信息(xi)(xi)（即直(zhi)接后繼的(de)(de)(de)存(cun)(cun)儲位(wei)置）。由這兩部分(fen)信息(xi)(xi)組成一(yi)(yi)個"結點"（如概述旁的(de)(de)(de)圖所示(shi)），表(biao)(biao)示(shi)線(xian)性表(biao)(biao)中一(yi)(yi)個數(shu)據元(yuan)(yuan)(yuan)素 。

擴展

根(gen)據情(qing)況(kuang)，也可(ke)以(yi)自己(ji)設計鏈(lian)(lian)表的其它(ta)擴展。但是一(yi)(yi)般不(bu)會(hui)在邊上附加數據，因為鏈(lian)(lian)表的點和邊基本上是一(yi)(yi)一(yi)(yi)對應的（除了第(di)一(yi)(yi)個或者最后(hou)一(yi)(yi)個節點，但是也不(bu)會(hui)產生特(te)殊情(qing)況(kuang)）。不(bu)過(guo)有一(yi)(yi)個特(te)例是如果鏈(lian)(lian)表支持在鏈(lian)(lian)表的一(yi)(yi)段中把前和后(hou)指(zhi)針反向，反向標(biao)記加在邊上可(ke)能會(hui)更方便。

對于非線性(xing)(xing)的(de)鏈(lian)表(biao)(biao)，可以(yi)參見相關(guan)的(de)其他，例如樹、圖(tu)。另外(wai)有一(yi)種基于多個線性(xing)(xing)鏈(lian)表(biao)(biao)的(de)數據結構：跳表(biao)(biao)，插(cha)入、刪除和(he)查找等基本操作的(de)速(su)度(du)可以(yi)達到(dao)O(nlogn)，和(he)一(yi)樣。

其中存儲數據元素信息的(de)域稱作數據域（設域名(ming)為(wei)(wei)data），存儲直接后繼(ji)存儲位置的(de)域稱為(wei)(wei)指針(zhen)(zhen)域（設域名(ming)為(wei)(wei)next）。指針(zhen)(zhen)域中存儲的(de)信息又稱做指針(zhen)(zhen)或鏈。

由分別表(biao)示,,…, 的N 個結點(dian)依次相(xiang)鏈(lian)構成(cheng)的鏈(lian)表(biao)，稱為線性表(biao)的鏈(lian)式存儲表(biao)示，由于此類鏈(lian)表(biao)的每個結點(dian)中只包含一個指針域(yu)，故又稱或線性鏈(lian)表(biao)。

兩種鏈表形式

一、循環鏈表

循環鏈表是與單鏈表一樣，是一種鏈式的存儲結構，所不同的是，循環鏈表的最后一個結點的指針是指向該循環鏈表的第一個結點或者表頭(tou)結點，從而(er)構成一個環(huan)形的鏈。

循環鏈表的運算與單鏈表的運算基本一致。所不同(tong)的有(you)以下幾點：

1、在建立一個循環鏈表時，必須使其最后一個結點的指針指向表頭結點，而不是象單鏈表那樣置為NULL。此種(zhong)情況還(huan)使用于在最后(hou)一個結(jie)點后(hou)插(cha)入(ru)一個新(xin)的結(jie)點。

2、在判斷是否到表尾時，是判斷該結點鏈域的值是否是表頭結點，當鏈域值等于表頭指針時，說明已到表尾。而非象單鏈表那樣判斷(duan)鏈(lian)域值是否為(wei)NULL。

二、雙向鏈表

雙向鏈表其實是單鏈表的改進。

當我們對單鏈表進行操作時，有時你要對某個結點的直接前驅進行操作時，又必須從表頭開始查找。這是由單鏈表結點的結構所限制的。因為單鏈表每個結點只有一個存儲直接后繼結點地址的鏈域，那么能不能定義一個既有存儲直接后繼結點地址的鏈域，又有存儲直接前驅結點地址的鏈域的這樣一個雙鏈域結點結構呢？這就是雙向鏈表。

在雙向鏈表中(zhong)，結點(dian)除(chu)含有數據域(yu)外，還有兩(liang)個鏈(lian)域(yu)，一(yi)個存(cun)儲直(zhi)接后繼(ji)結點(dian)地址，一(yi)般稱之為右鏈(lian)域(yu)；一(yi)個存(cun)儲直(zhi)接前驅結點(dian)地址，一(yi)般稱之為左(zuo)鏈(lian)域(yu)。

返回目錄