連結串列

在電腦科學中，連結串列是一種常見的基礎資料結構，是一種線性表，但是並不會按線性的順序儲存資料，而是在每一個節點裡存到下一個節點的指標(--)。由於不必須按順序儲存，連結串列在插入的時候可以達到O(1)的複雜度，比另一種線性表順序錶快得多，但是查詢一個節點或者訪問特定編號的節點則需要O(n)的時間，而順序表相應的時間複雜度分別是O(logn)和O(1)。使用連結串列結構可以克服陣列連結串列需要預先知道資料大小的缺點，連結串列結構可以充分利用計算機記憶體空間，實現靈活的記憶體動態管理。但是連結串列失去了陣列隨機讀取的優點，同時連結串列由於增加了結點的指標域，空間開銷比較大。在計算機科學中，連結串列作為一種基礎的資料結構可以用來生成其它型別的資料結構。連結串列通常由一連串節點組成，每個節點包含任意的例項資料。連結串列允許插入和移除表上任意位置上的節點，但是不允許隨機存取。連結串列有很多種不同的型別：單向連結串列，雙向連結串列以及迴圈連結串列。連結串列可以在多種程式語言中實現。像Lisp和Scheme這樣的語言的內建資料型別中就包含了連結串列的存取和操作。程式語言或面嚮物件語言，如C/C++和Java依靠易變工具來生成連結串列。歷史.連結串列開發於1955-56，由當時所屬於蘭德公司中做為原始資料型別所編寫。IPL被作者們用來開發幾種早期的人工智慧程式，包括邏輯推理機，通用問題解算器和一個計算機象棋程式。結構.單向連結串列.連結串列中最簡單的一種是單向連結串列，它包含兩個域，一個資訊域和一個指標域。這個連結指向列表中的下一個節點，而最後一個節點則指向一個空值。一個單向連結串列的節點被分成兩個部分。第一個部分儲存或者顯示關於節點的資訊，第二個部分儲存下一個節點的地址。單向連結串列只可向一個方向遍歷。連結串列最基本的結構是在每個節點儲存資料和到下一個節點的地址，在最後一個節點儲存一個特殊的結束標記，另外在一個固定的位置儲存指向第一個節點的指標，有的時候也會同時儲存指向最後一個節點的指標。一般查詢一個節點的時候需要從第一個節點開始每次訪問下一個節點，一直訪問到需要的位置。但是也可以提前把一個節點的位置另外儲存起來，然後直接訪問。當然如果只是訪問資料就沒必要了，不如在連結串列上儲存指向實際資料的指標。這樣一般是為了訪問連結串列中的下一個或者前一個節點。相對於下面的雙向連結串列，這種普通的，每個節點只有一個指標的連結串列也叫單向連結串列，或者單鏈表，通常用在每次都只會按順序遍歷這個連結串列的時候。連結串列也有很多種不同的變化：雙向連結串列.一種更復雜的連結串列是“雙向連結串列”或“雙面連結串列”。每個節點有兩個連線：一個指向前一個節點，在一些低階語言中, XOR-linking 提供一種在雙向連結串列中透過用一個詞來表示兩個連結，我們通常不提倡這種做法。雙向連結串列也叫雙鏈表。雙向連結串列中不僅有指向後一個節點的指標，還有指向前一個節點的指標。這樣可以從任何一個節點訪問前一個節點，當然也可以訪問後一個節點，以至整個連結串列。一般是在需要大批次的另外儲存資料在連結串列中的位置的時候用。雙向連結串列也可以配合下面的其他連結串列的擴充套件使用。由於另外儲存了指向連結串列內容的指標，並且可能會修改相鄰的節點，有的時候第一個節點可能會被刪除或者在之前新增一個新的節點。這時候就要修改指向首個節點的指標。有一種方便的可以消除這種特殊情況的方法是在最後一個節點之後、第一個節點之前儲存一個永遠不會被刪除或者移動的虛擬節點，形成一個下面說的迴圈連結串列。這個虛擬節點之後的節點就是真正的第一個節點。這種情況通常可以用這個虛擬節點直接表示這個連結串列，對於把連結串列單獨的存在數組裡的情況，也可以直接用這個陣列表示連結串列並用第0個或者第-1個節點固定的表示這個虛擬節點。迴圈連結串列.在一個 迴圈連結串列中, 首節點和末節點被連線在一起。這種方式在單向和雙向連結串列中皆可實現。要轉換一個迴圈連結串列，你開始於任意一個節點然後沿著列表的任一方向直到返回開始的節點。再來看另一種方法，迴圈連結串列可以被視為“無頭無尾”。這種列表很利於節約資料儲存快取， 假定你在一個列表中有一個物件並且希望所有其他物件迭代在一個非特殊的排列下。指向整個列表的指標可以被稱作存取指標。迴圈連結串列中第一個節點之前就是最後一個節點，反之亦然。迴圈連結串列的無邊界使得在這樣的連結串列上設計算法會比普通連結串列更加容易。對於新加入的節點應該是在第一個節點之前還是最後一個節點之後可以根據實際要求靈活處理，區別不大(詳見下面例項程式碼)。當然，如果只會在最後插入資料，處理也是很容易的。另外有一種模擬的迴圈連結串列，就是在訪問到最後一個節點之後的時候，手工的跳轉到第一個節點。訪問到第一個節點之前的時候也一樣。這樣也可以實現迴圈連結串列的功能，在直接用迴圈連結串列比較麻煩或者可能會出現問題的時候可以用。塊狀連結串列.塊狀連結串列本身是一個連結串列，但是連結串列儲存的並不是一般的資料，而是由這些資料組成的順序表。每一個塊狀連結串列的節點，也就是順序表，可以被叫做一個塊。塊狀連結串列透過使用可變的順序表的長度和特殊的插入、刪除方式，可以在達到formula_1的複雜度。塊狀連結串列另一個特點是相對於普通連結串列來說節省記憶體，因為不用儲存指向每一個數據節點的指標。其它擴充套件.根據情況，也可以自己設計連結串列的其它擴充套件。但是一般不會在邊上附加資料，因為連結串列的點和邊基本上是一一對應的。不過有一個特例是如果連結串列支援在連結串列的一段中把前和後指標反向，反向標記加在邊上可能會更方便。對於非線性的連結串列，可以關的其他資料結構，例如樹、圖。另外有一種基於多個線性連結串列的資料結構：跳錶，插入、刪除和查詢等基本操作的速度可以達到O(nlogn)，和平衡樹一樣。儲存結構.連結串列中的節點不需要以特定的方式儲存，但是集中儲存也是可以的，主要分下面這幾種具體的儲存方法：連結串列的應用.連結串列用來構建許多其它資料結構，如堆疊，佇列和他們的衍生。節點的資料域也可以成為另一個連結串列。透過這種手段，我們可以用列表來構建許多鏈性資料結構；這個例項產生於Lisp程式語言，在Lisp中連結串列是初級資料結構，並且現在成為了常見的基礎程式設計模式。有時候，連結串列用來生成聯合陣列，在這種情況下我們稱之為聯合數列。這種情況下用連結串列會優於其它資料結構，如自平對分查詢樹甚至是一些小的資料集合。不管怎樣，一些時候一個連結串列在這樣一個樹中建立一個節點子集，並且以此來更有效率地轉換這個集合。C程式碼例項.範例程式碼是一個ADT，全部遵從ANSI C標準。介面宣告.typedef void node_proc_fun_t(void*);typedef int node_comp_fun_t(const void*, const void*);typedef void LLIST_T;LLIST_T *llist_new(int elmsize);int llist_delete(LLIST_T *ptr);int llist_node_append(LLIST_T *ptr, const void *datap);int llist_node_prepend(LLIST_T *ptr, const void *datap);int llist_travel(LLIST_T *ptr, node_proc_fun_t *proc);void llist_node_delete(LLIST_T *ptr, node_comp_fun_t *comp, const void *key);void *llist_node_find(LLIST_T *ptr, node_comp_fun_t *comp, const void *key);介面實現.型別定義.struct node_st {void *datap;struct node_st *next, *prev;struct llit_st {struct node_st head;int lmsize;int elmnr;初始化和銷燬.LLIST_T *llist_new(int elmsize) {struct llist_st *newlist = malloc(sizeof(struct llist_st));if (newlist == NULL)return NULL;newlist-&gt;head.datap = NULL;newlist-&gt;head.next = &amp;newlist-&gt;head;newlist-&gt;head.prev = &amp;newlist-&gt;head;newlist-&gt;lmsize = elmsize;return (void *)newlist;int llist_delete(LLIST_T *ptr) {struct llist_st *me = ptr;struct node_st *curr, *save;for (curr = me-&gt;head.next ;curr != &amp;me-&gt;head ; curr = save) {save = curr-&gt;next;free(curr-&gt;datap);free(curr);free(me);return 0;節點插入.int llist_node_append(LLIST_T *ptr, const void *datap) {struct llist_st *me = ptr;struct node_st *newnodep;newnodep = malloc(sizeof(struct node_st));if (newnodep == NULL)return -1;newnodep-&gt;datap = malloc(me-&gt;elmsize);if (newnodep-&gt;datap == NULL) {free(newnodep);return -1;memcpy(newnodep-&gt;datap, datap, me-&gt;elmsize);me-&gt;head.prev-&gt;next = newnodep;newnodep-&gt;prev = me-&gt;head.prev;me-&gt;head.prev = newnodep;newnodep-&gt;next = &amp;me-&gt;head;return 0;int llist_node_prepend(LLIST_T *ptr, const void *datap) {struct llist_st *me = ptr;struct node_st *newnodep;newnodep = malloc(sizeof(struct node_st));if (newnodep == NULL)return -1;newnodep-&gt;datap = malloc(me-&gt;elmsize);if (newnodep-&gt;datap == NULL) {free(newnodep);return -1;memcpy(newnodep-&gt;datap, datap, me-&gt;elmsize);me-&gt;head.next-&gt;prev = newnodep;newnodep-&gt;next = me-&gt;head.next;me-&gt;head.next = newnodep;newnodep-&gt;prev = &amp;me-&gt;head;return 0;遍歷.int llist_travel(LLIST_T *ptr, node_proc_fun_t *proc) {struct llist_st *me = ptr;struct node_st *curr;for (curr = me-&gt;head.next;curr != &amp;me-&gt;head ; curr = curr-&gt;next)proc(curr-&gt;datap); // proc(something you like)return 0;刪除和查詢.void llist_node_delete(LLIST_T *ptr,node_comp_fun_t *comp,const void *key) {struct llist_st *me = ptr;struct node_st *curr;for (curr = me-&gt;head.next;curr != &amp;me-&gt;head; curr = curr-&gt;next) {if ( (*comp)(curr-&gt;datap, key) == 0 ) {struct node_st *_next, *_prev;_prev = curr-&gt;prev; _next = curr-&gt;next;_prev-&gt;next = _next; _next-&gt;prev = _prev;free(curr-&gt;datap);free(curr);break;return;void *llist_node_find(LLIST_T *ptr,node_comp_fun_t *comp, const void *key) {struct llist_st *me = ptr;struct node_st *curr;for (curr = me-&gt;head.next;curr != &amp;me-&gt;head; curr = curr-&gt;next) {if ( (*comp)(curr-&gt;datap, key) == 0 )return curr-&gt;datap;return NULL;C宏例項.以下程式碼摘自Linux核心2.6.21.5原始碼(部分)，展示了連結串列的另一種實現思路，未採用ANSI C標準，採用GNU C標準，遵從GPL版權許可。struct list_head {struct list_head *next, *prev;struct list_head name = LIST_HEAD_INIT(name)static inline void INIT_LIST_HEAD(struct list_head *list) {list-&gt;next = list;list-&gt;prev = list;static inline void __list_add(struct list_head *new,struct list_head *prev,struct list_head *next) {next-&gt;prev = new;new-&gt;next = next;new-&gt;prev = prev;prev-&gt;next = new;static inline void list_add(struct list_head *new, struct list_head *head) {__list_add(new, head, head-&gt;next);static inline void __list_del(struct list_head *prev, struct list_head *next) {next-&gt;prev = prev;prev-&gt;next = next;static inline void list_del(struct list_head *entry) {__list_del(entry-&gt;prev, entry-&gt;next);entry-&gt;next = NULL;entry-&gt;prev = NULL;for (pos = (head)-&gt;next; pos != (head); pos = pos-&gt;next)for (pos = list_entry((head)-&gt;next, typeof(*pos), member); \prefetch(pos-&gt;member.next), &amp;pos-&gt;member != (head); \pos = list_entry(pos-&gt;member.next, typeof(*pos), member))常見用途.常用於組織檢索較少，而刪除、新增、遍歷較多的資料。如果與上述情形相反，應採用其他資料結構或者與其他資料結構組合使用。延伸閲讀.