链表

歷史

連結串列開發於1955-56，由當時所屬於蘭德公司（英語：RAND Corporation）的艾倫紐維爾（Allen Newell），克里夫肖（Cliff Shaw）和赫伯特西蒙（Herbert Simon）在他們編寫的資訊處理語言（IPL）中做為原始資料類型所編寫。IPL被作者們用來開發幾種早期的人工智慧程式，包括邏輯推理機，通用問題解算器和一個電腦象棋程式。

單向連結串列

連結串列中最簡單的一種是單向連結串列，它包含兩個域，一個資訊域和一個指標域。這個連結指向列表中的下一個節點，而最後一個節點則指向一個空值。
一個單向連結串列的節點被分成兩個部分。第一個部分儲存或者顯示關於節點的資訊，第二個部分儲存下一個節點的位址。單向連結串列只可向一個方向遍歷。
連結串列最基本的結構是在每個節點儲存資料和到下一個節點的位址，在最後一個節點儲存一個特殊的結束標記，另外在一個固定的位置儲存指向第一個節點的指標，有的時候也會同時儲存指向最後一個節點的指標。一般尋找一個節點的時候需要從第一個節點開始每次存取下一個節點，一直存取到需要的位置。但是也可以提前把一個節點的位置另外儲存起來，然後直接存取。當然如果只是存取資料就沒必要了，不如在連結串列上儲存指向實際資料的指標。這樣一般是為了存取連結串列中的下一個或者前一個（需要儲存反向的指標，見下面的雙向連結串列）節點。
相對於下面的雙向連結串列，這種普通的，每個節點只有一個指標的連結串列也叫單向連結串列，或者單連結串列，通常用在每次都只會按順序遍歷這個連結串列的時候（例如圖的鄰接表，通常都是按固定順序存取的）。
連結串列也有很多種不同的變化：

雙向連結串列

一種更複雜的連結串列是「雙向連結串列」或「雙面連結串列」。每個節點有兩個連接：一個指向前一個節點，（當此「連接」為第一個「連接」時，指向空值或者空列表）；而另一個指向下一個節點，（當此「連接」為最後一個「連接」時，指向空值或者空列表）
在一些低階語言中, XOR-linking 提供一種在雙向連結串列中通過用一個詞來表示兩個連結（前後），我們通常不提倡這種做法。
雙向連結串列也叫雙連結串列。雙向連結串列中不僅有指向後一個節點的指標，還有指向前一個節點的指標。這樣可以從任何一個節點存取前一個節點，當然也可以存取後一個節點，以至整個連結串列。一般是在需要大批次的另外儲存資料在連結串列中的位置的時候用。雙向連結串列也可以配合下面的其他連結串列的擴充使用。
由於另外儲存了指向連結串列內容的指標，並且可能會修改相鄰的節點，有的時候第一個節點可能會被刪除或者在之前添加一個新的節點。這時候就要修改指向首個節點的指標。有一種方便的可以消除這種特殊情況的方法是在最後一個節點之後、第一個節點之前儲存一個永遠不會被刪除或者移動的虛擬節點，形成一個下面說的迴圈連結串列。這個虛擬節點之後的節點就是真正的第一個節點。這種情況通常可以用這個虛擬節點直接表示這個連結串列，對於把連結串列單獨的存在陣列里的情況，也可以直接用這個陣列表示連結串列並用第0個或者第-1個（如果編譯器支援）節點固定的表示這個虛擬節點。

迴圈連結串列

在一個 迴圈連結串列中, 首節點和末節點被連接在一起。這種方式在單向和雙向連結串列中皆可實現。要轉換一個迴圈連結串列，你開始於任意一個節點然後沿著列表的任一方向直到返回開始的節點。再來看另一種方法，迴圈連結串列可以被視為「無頭無尾」。這種列表很利於節約資料儲存快取， 假定你在一個列表中有一個物件並且希望所有其他物件疊代在一個非特殊的排列下。
指向整個列表的指標可以被稱作存取指標。
迴圈連結串列中第一個節點之前就是最後一個節點，反之亦然。迴圈連結串列的無邊界使得在這樣的連結串列上設計演算法會比普通連結串列更加容易。對於新加入的節點應該是在第一個節點之前還是最後一個節點之後可以根據實際要求靈活處理，區別不大(詳見下面實體程式碼)。當然，如果只會在最後插入資料（或者只會在之前），處理也是很容易的。
另外有一種類比的迴圈連結串列，就是在存取到最後一個節點之後的時候，手工的跳轉到第一個節點。存取到第一個節點之前的時候也一樣。這樣也可以實現迴圈連結串列的功能，在直接用迴圈連結串列比較麻煩或者可能會出現問題的時候可以用。

塊狀連結串列

塊狀連結串列本身是一個連結串列，但是連結串列儲存的並不是一般的資料，而是由這些資料組成的順序表。每一個塊狀連結串列的節點，也就是順序表，可以被叫做一個塊。
塊狀連結串列通過使用可變的順序表的長度和特殊的插入、刪除方式，可以在達到的複雜度。塊狀連結串列另一個特點是相對於普通連結串列來說節省記憶體，因為不用儲存指向每一個資料節點的指標。

其它擴充

根據情況，也可以自己設計連結串列的其它擴充。但是一般不會在邊上附加資料，因為連結串列的點和邊基本上是一一對應的（除了第一個或者最後一個節點，但是也不會產生特殊情況）。不過有一個特例是如果連結串列支援在連結串列的一段中把前和後指標反向，反向標記加在邊上可能會更方便。
對於非線性的連結串列，可以參見相關的其他資料結構，例如樹、圖。另外有一種基於多個線性連結串列的資料結構：跳表，插入、刪除和尋找等基本操作的速度可以達到O(nlogn)，和平衡樹一樣。

連結串列的應用

連結串列用來構建許多其它資料結構，如堆疊，佇列和他們的衍生。
節點的資料域也可以成為另一個連結串列。通過這種手段，我們可以用列表來構建許多鏈性資料結構；這個實體產生於Lisp程式語言，在Lisp中連結串列是初級資料結構，並且現在成為了常見的基礎編程模式。
有時候，連結串列用來生成聯合陣列，在這種情況下我們稱之為聯合數列。這種情況下用連結串列會優於其它資料結構，如自平對分尋找樹（self-balancing binary search trees）甚至是一些小的資料集合。不管怎樣，一些時候一個連結串列在這樣一個樹中建立一個節點子集，並且以此來更有效率地轉換這個集合。

C程式碼實體

範例程式碼是一個ADT（抽象資料類型）雙向環形連結串列的基本操作部分的實體（未包含執行緒安全機制），全部遵從ANSI C標準。

介面聲明

1 #ifndef LLIST_H 2 #define LLIST_H 3  4 typedef void node_proc_fun_t(void*); 5 typedef int node_comp_fun_t(const void*, const void*); 6  7 typedef void LLIST_T; 8  9 LLIST_T *llist_new(int elmsize);10 int llist_delete(LLIST_T *ptr);11  
12 int llist_node_append(LLIST_T *ptr, const void *datap);13 int llist_node_prepend(LLIST_T *ptr, const void *datap);14 15 int llist_travel(LLIST_T *ptr, node_proc_fun_t *proc);16  
17 void llist_node_delete(LLIST_T *ptr, node_comp_fun_t *comp, const void *key); 
18 void *llist_node_find(LLIST_T *ptr, node_comp_fun_t *comp, const void *key);19 20 #endif

類型定

1 struct node_st { 2     void *datap; 3     struct node_st *next, *prev; 4 }; 5  6 struct llit_st { 7     struct node_st head; 8     int lmsize; 9     int elmnr;10 };

初始化和銷毀

1 LLIST_T * 2 llist_new(int elmsize) { 3     struct llist_st *newlist; 4     newlist = malloc(sizeof(struct llist_st)); 5     if (newlist == NULL) 6         return NULL; 7     newlist->head.datap = NULL; 8     newlist->head.next = &newlist->head; 9     newlist->head.prev = &newlist->head;10     newlist->elmsize = elmsize;11     return (void *)newlist;12 }13 14 int llist_delete(LLIST_T *ptr) {15     struct llist_st *me = ptr;16     struct node_st *curr, *save;17     for (curr = me->head.next ;18             curr != &me->head ; curr = save) {19         save = curr->next;20         free(curr->datap);21         free(curr);22     }23     free(me);24     return 0;25 }

節點插入

1 int llist_node_append(LLIST_T *ptr, const void *datap) { 2     struct llist_st *me = ptr; 3     struct node_st *newnodep; 4     newnodep = malloc(sizeof(struct node_st)); 5     if (newnodep == NULL) 6         return -1; 7     newnodep->datap = malloc(me->elmsize); 8     if (newnodep->datap == NULL) { 9         free(newnodep);10         return -1;11     }12     memcpy(newnodep->datap, datap, me->elmsize);13     me->head.prev->next = newnodep;14     newnodep->prev = me->head.prev;15     me->head.prev = newnodep;16     newnodep->next = &me->head;17     return 0;18 }19 20 int llist_node_prepend(LLIST_T *ptr, const void *datap) {21     struct llist_st *me = ptr;22     struct node_st *newnodep;23     newnodep = malloc(sizeof(struct node_st));24     if (newnodep == NULL)25         return -1;26     newnodep->datap = malloc(me->elmsize);27     if (newnodep->datap == NULL) {28         free(newnodep);29         return -1;30     }31     memcpy(newnodep->datap, datap, me->elmsize);32     me->head.next->prev = newnodep;33     newnodep->next = me->head.next;34     me->head.next = newnodep;35     newnodep->prev = &me->head;36     return 0;37 }

遍歷

1 int llist_travel(LLIST_T *ptr, node_proc_fun_t *proc) {2     struct llist_st *me = ptr;3     struct node_st *curr;4     for (curr = me->head.next;5             curr != &me->head ; curr = curr->next)6         proc(curr->datap); // proc(something you like)7     return 0;8 }

刪除和尋找

1 void llist_node_delete(LLIST_T *ptr, 2                        node_comp_fun_t *comp, 3                        const void *key) { 4     struct llist_st *me = ptr; 5     struct node_st *curr; 6     for (curr = me->head.next; 7             curr != &me->head; curr = curr->next) { 8         if ( (*comp)(curr->datap, key) == 0 ) { 9             struct node_st *_next, *_prev;10             _prev = curr->prev; _next = curr->next;11             _prev->next = _next; _next->prev = _prev;12             free(curr->datap);13             free(curr);14             break;15         }16     }17     return;18 }19 20 void *llist_node_find(LLIST_T *ptr,21                       node_comp_fun_t *comp, const void *key) {22     struct llist_st *me = ptr;23     struct node_st *curr;24     for (curr = me->head.next;25             curr != &me->head; curr = curr->next) {26         if ( (*comp)(curr->datap, key) == 0 )27             return curr->datap;28     }29     return NULL;30 }

C宏實體

以下程式碼摘自Linux核心2.6.21.5原始碼(部分)，展示了連結串列的另一種實現思路，未採用ANSI C標準，採用GNU C標準，遵從GPL著作權許可。
 1 struct list_head { 2     struct list_head *next, *prev; 3 }; 4  5 #define LIST_HEAD_INIT(name) { &(name), &(name) } 6 #define LIST_HEAD(name) \ 7         struct list_head name = LIST_HEAD_INIT(name) 8  9 static inline void INIT_LIST_HEAD(struct list_head *list) {10     list->next = list;11     list->prev = list;12 }13 14 static inline void __list_add(struct list_head *new,15                               struct list_head *prev,16                               struct list_head *next) {17     next->prev = new;18     new->next = next;19     new->prev = prev;20     prev->next = new;21 }22 23 static inline void list_add(struct list_head *new, struct list_head *head) {24     __list_add(new, head, head->next);25 }26 27 static inline void __list_del(struct list_head *prev, struct list_head *next) {28     next->prev = prev;29     prev->next = next;30 }31 32 static inline void list_del(struct list_head *entry) {33     __list_del(entry->prev, entry->next);34     entry->next = NULL;35     entry->prev = NULL;36 }37 38 #define __list_for_each(pos, head) \39         for (pos = (head)->next; pos != (head); pos = pos->next)40 41 #define list_for_each_entry(pos, head, member)                          \42         for (pos = list_entry((head)->next, typeof(*pos), member);      \43              prefetch(pos->member.next), &pos->member != (head);        \44              pos = list_entry(pos->member.next, typeof(*pos), member))

常見用途

常用於組織檢索較少，而刪除、添加、遍歷較多的資料。
如果與上述情形相反，應採用其他資料結構或者與其他資料結構組合使用。