數(shù)據(jù)結構中鏈表及常見操作

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

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

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

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

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

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

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