數(shù)據(jù)結(jié)構(gòu)中鏈表及常見(jiàn)操作

1、鏈表鏈表1定義定義鏈表（Linkedlist）是一種常見(jiàn)的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會(huì)按線性的順序存儲(chǔ)數(shù)據(jù)，而是在每一個(gè)節(jié)點(diǎn)里存到下一個(gè)節(jié)點(diǎn)的指針(Pointer)。由于不必須按順序存儲(chǔ)，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度，比另一種線性表順序表快得多，但是查找一個(gè)節(jié)點(diǎn)或者訪問(wèn)特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間，而順序表相應(yīng)的時(shí)間復(fù)雜度分別是O(logn)和O(1)。使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)，

2、鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。但是鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域，空間開(kāi)銷比較大。在計(jì)算機(jī)科學(xué)中，鏈表作為一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)可以用來(lái)生成其它類型的數(shù)據(jù)結(jié)構(gòu)。鏈表通常由一連串節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)包含任意的實(shí)例數(shù)據(jù)（datafields）和一或兩個(gè)用來(lái)指向明上一個(gè)或下一個(gè)節(jié)點(diǎn)的位置的鏈接（“l(fā)inks“）。鏈表最明顯的好處就是，常規(guī)數(shù)組排列關(guān)聯(lián)項(xiàng)目的方式可能不同于這些數(shù)據(jù)項(xiàng)目在記憶體

3、或磁盤上順序，數(shù)據(jù)的訪問(wèn)往往要在不同的排列順序中轉(zhuǎn)換。而鏈表是一種自我指示數(shù)據(jù)類型，因?yàn)樗赶蛄硪粋€(gè)相同類型的數(shù)據(jù)的指針（鏈接）。鏈表允許插入和移除表上任意位置上的節(jié)點(diǎn)，但是不允許隨機(jī)存取。鏈表有很多種不同的類型：?jiǎn)蜗蜴湵?，雙向鏈表以及循環(huán)鏈表。2結(jié)構(gòu)結(jié)構(gòu)2.12.1單向鏈表單向鏈表鏈表中最簡(jiǎn)單的一種是單向鏈表，它包含兩個(gè)域，一個(gè)信息域和一個(gè)指針域。這個(gè)鏈接指向列表中的下一個(gè)節(jié)點(diǎn)，而最后一個(gè)節(jié)點(diǎn)則指向一個(gè)空值。一個(gè)單向鏈表的節(jié)點(diǎn)被分

4、成兩個(gè)部分。第一個(gè)部分保存或者顯示關(guān)于節(jié)點(diǎn)的信息，第二個(gè)部分存儲(chǔ)下一個(gè)節(jié)點(diǎn)的地址。單向鏈表只可向一個(gè)方向遍歷。鏈表最基本的結(jié)構(gòu)是在每個(gè)節(jié)點(diǎn)保存數(shù)據(jù)和到下一個(gè)節(jié)點(diǎn)的地址，在最后一個(gè)節(jié)點(diǎn)保存一個(gè)特殊的結(jié)束標(biāo)記，另外在一個(gè)固定的位置保存指向第一個(gè)節(jié)點(diǎn)的指針，有的時(shí)候也會(huì)同時(shí)儲(chǔ)存指向最后一個(gè)節(jié)點(diǎn)的指針。一般查找一個(gè)節(jié)點(diǎn)的時(shí)候需要從第一個(gè)節(jié)點(diǎn)開(kāi)始每次訪問(wèn)下一個(gè)節(jié)點(diǎn)，一直訪問(wèn)到需要的位置。2.22.2雙向鏈表雙向鏈表每個(gè)節(jié)點(diǎn)有兩個(gè)連接：一個(gè)指向前一

5、個(gè)節(jié)點(diǎn)，（當(dāng)此“連接”為第一個(gè)“連接”時(shí)，指向空值或者空列表）；而另一個(gè)指向下一個(gè)節(jié)點(diǎn)，（當(dāng)此“連接”為最后一個(gè)“連接”時(shí)，指向空值或者空列表）雙向鏈表可以從任何一個(gè)節(jié)點(diǎn)訪問(wèn)前一個(gè)節(jié)點(diǎn)，當(dāng)然也可以訪問(wèn)后一個(gè)節(jié)點(diǎn)，以至整個(gè)鏈表。一般是在需要大批量的另外儲(chǔ)存數(shù)據(jù)在鏈表中的位置的時(shí)候用。2.32.3循環(huán)鏈表循環(huán)鏈表在一個(gè)循環(huán)鏈表中首節(jié)點(diǎn)和末節(jié)點(diǎn)被連接在一起。這種方式在單向和雙向鏈表中皆可實(shí)現(xiàn)。要轉(zhuǎn)換一個(gè)循環(huán)鏈表，你開(kāi)始于任意一個(gè)節(jié)點(diǎn)然后沿著列

6、表的任一方向直到返回開(kāi)始的節(jié)點(diǎn)。指向整個(gè)列表的指針可以被稱作訪問(wèn)指針。附錄附錄：（鏈表的部分常見(jiàn)操作）1單向鏈表單向鏈表線性表的單鏈表存儲(chǔ)結(jié)構(gòu)typedefstructLNodeElemTypedatastructLNodenextLNodeLinkList帶有頭結(jié)點(diǎn)的單鏈表的基本操作(12個(gè))voidInitList(LinkListL)操作結(jié)果：構(gòu)造一個(gè)空的線性表LL=(LinkList)malloc(sizeof(structLN

7、ode))產(chǎn)生頭結(jié)點(diǎn)，并使L指向此頭結(jié)點(diǎn)if(!L)存儲(chǔ)分配失敗exit(OVERFLOW)(L)next=NULL指針域?yàn)榭誺oidDestroyList(LinkListL)初始條件：線性表L已存在。操作結(jié)果：銷毀線性表LLinkListqwhile(L)q=(L)nextfree(L)L=qvoidClearList(LinkListL)不改變L初始條件：線性表L已存在。操作結(jié)果：將L重置為空表LinkListpqp=Lnextp