鍊表

在電腦科學中，鍊表（英語：Linked list）是一種常見的基礎數據結構，是一種線性表，但是並不會按線性的順序存儲數據，而是在每一個節點裡存到下一個節點的指針。由於不必須按順序存儲，鍊表在插入的時候可以達到O(1)的複雜度，比另一種線性表順序表快得多，但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而順序表相應的時間複雜度分別是O(n)和O(1)。

使用鍊表結構可以克服數組鍊表需要預先知道數據大小的缺點，鍊表結構可以充分利用計算機內存空間，實現靈活的內存動態管理。但是鍊表失去了數組隨機讀取的優點，同時鍊表由於增加了結點的指針域，空間開銷比較大。

在計算機科學中，鍊表作為一種基礎的數據結構可以用來生成其它類型的數據結構。鍊表通常由一連串節點組成，每個節點包含任意的實例數據（data fields）和一或兩個用來指向上一個/或下一個節點的位置的鏈接（"links"）。鍊表最明顯的好處就是，常規數組排列關聯項目的方式可能不同於這些數據項目在記憶體或磁盤上順序，數據的存取往往要在不同的排列順序中轉換。而鍊表是一種自我指示數據類型，因為它包含指向另一個相同類型的數據的指針（鏈接）。鍊表允許插入和移除表上任意位置上的節點，但是不允許隨機存取。鍊表有很多種不同的類型：單向鍊表，雙向鍊表以及循環鍊表。

鍊表可以在多種編程語言中實現。像Lisp和Scheme這樣的語言的內建數據類型中就包含了鍊表的存取和操作。程序語言或面向對象語言，如C/C++和Java依靠易變工具來生成鍊表。

Remove ads

歷史

鍊表開發於1955年至1956年，由當時所屬於蘭德公司的艾倫·紐厄爾、克里夫·肖（英語：Cliff Shaw）和司馬賀在他們編寫的信息處理語言（IPL）中做為原始數據類型所編寫。IPL被作者們用來開發幾種早期的人工智能程序，包括邏輯推理機，通用問題解算器和一個計算機象棋程序。

結構

單向鍊表

鍊表中最簡單的一種是單向鍊表，它包含兩個域，一個信息域和一個指針域。這個鏈接指向列表中的下一個節點，而最後一個節點則指向一個空值。

一個單向鍊表包含兩個值: 當前節點的值和一個指向下一個節點的鏈接

一個單向鍊表的節點被分成兩個部分。第一個部分保存或者顯示關於節點的信息，第二個部分存儲下一個節點的地址。單向鍊表只可向一個方向遍歷。

鍊表最基本的結構是在每個節點保存數據和到下一個節點的地址，在最後一個節點保存一個特殊的結束標記，另外在一個固定的位置保存指向第一個節點的指針，有的時候也會同時儲存指向最後一個節點的指針。一般查找一個節點的時候需要從第一個節點開始每次訪問下一個節點，一直訪問到需要的位置。但是也可以提前把一個節點的位置另外保存起來，然後直接訪問。當然如果只是訪問數據就沒必要了，不如在鍊表上儲存指向實際數據的指針。這樣一般是為了訪問鍊表中的下一個或者前一個（需要儲存反向的指針，見下面的雙向鍊表）節點。

相對於下面的雙向鍊表，這種普通的，每個節點只有一個指針的鍊表也叫單向鍊表，或者單鍊表，通常用在每次都只會按順序遍歷這個鍊表的時候（例如圖的鄰接表，通常都是按固定順序訪問的）。

鍊表也有很多種不同的變化：

Remove ads

雙向鍊表

一種更複雜的鍊表是「雙向鍊表」或「雙面鍊表」。每個節點有兩個連接：一個指向前一個節點，（當此「連接」為第一個「連接」時，指向空值或者空列表）；而另一個指向下一個節點，（當此「連接」為最後一個「連接」時，指向空值或者空列表）

一個雙向鍊表有三個整數值: 數值, 向後的節點鏈接, 向前的節點鏈接

在一些低級語言中，XOR-linking 提供一種在雙向鍊表中通過用一個詞來表示兩個鏈接（前後），我們通常不提倡這種做法。

雙向鍊表也叫雙鍊表。雙向鍊表中不僅有指向後一個節點的指針，還有指向前一個節點的指針。這樣可以從任何一個節點訪問前一個節點，當然也可以訪問後一個節點，以至整個鍊表。一般是在需要大批量的另外儲存數據在鍊表中的位置的時候用。雙向鍊表也可以配合下面的其他鍊表的擴展使用。

由於另外儲存了指向鍊表內容的指針，並且可能會修改相鄰的節點，有的時候第一個節點可能會被刪除或者在之前添加一個新的節點。這時候就要修改指向首個節點的指針。有一種方便的可以消除這種特殊情況的方法是在最後一個節點之後、第一個節點之前儲存一個永遠不會被刪除或者移動的虛擬節點，形成一個下面說的循環鍊表。這個虛擬節點之後的節點就是真正的第一個節點。這種情況通常可以用這個虛擬節點直接表示這個鍊表，對於把鍊表單獨的存在數組里的情況，也可以直接用這個數組表示鍊表並用第0個或者第-1個（如果編譯器支持）節點固定的表示這個虛擬節點。

Remove ads

循環鍊表

在一個 循環鍊表中, 首節點和末節點被連接在一起。這種方式在單向和雙向鍊表中皆可實現。要轉換一個循環鍊表，你開始於任意一個節點然後沿着列表的任一方向直到返回開始的節點。再來看另一種方法，循環鍊表可以被視為「無頭無尾」。這種列表很利於節約數據存儲緩存，假定你在一個列表中有一個對象並且希望所有其他對象迭代在一個非特殊的排列下。

指向整個列表的指針可以被稱作存取指針。

用單向鍊表構建的循環鍊表

循環鍊表中第一個節點之前就是最後一個節點，反之亦然。循環鍊表的無邊界使得在這樣的鍊表上設計算法會比普通鍊表更加容易。對於新加入的節點應該是在第一個節點之前還是最後一個節點之後可以根據實際要求靈活處理，區別不大(詳見下面實例代碼)。當然，如果只會在最後插入數據（或者只會在之前），處理也是很容易的。

另外有一種模擬的循環鍊表，就是在訪問到最後一個節點之後的時候，手工的跳轉到第一個節點。訪問到第一個節點之前的時候也一樣。這樣也可以實現循環鍊表的功能，在直接用循環鍊表比較麻煩或者可能會出現問題的時候可以用。

塊狀鍊表

塊狀鍊表本身是一個鍊表，但是鍊表儲存的並不是一般的數據，而是由這些數據組成的順序表。每一個塊狀鍊表的節點，也就是順序表，可以被叫做一個塊。

塊狀鍊表通過使用可變的順序表的長度和特殊的插入、刪除方式，可以在達到 $O({\sqrt {n}})$ 的複雜度。塊狀鍊表另一個特點是相對於普通鍊表來說節省內存，因為不用保存指向每一個數據節點的指針。

其它擴展

根據情況，也可以自己設計鍊表的其它擴展。但是一般不會在邊上附加數據，因為鍊表的點和邊基本上是一一對應的（除了第一個或者最後一個節點，但是也不會產生特殊情況）。不過有一個特例是如果鍊表支持在鍊表的一段中把前和後指針反向，反向標記加在邊上可能會更方便。

對於非線性的鍊表，可以參見相關的其他數據結構，例如樹、圖。另外有一種基於多個線性鍊表的數據結構：跳表，插入、刪除和查找等基本操作的速度可以達到O(nlogn)，和平衡樹一樣。

存儲結構

鍊表中的節點不需要以特定的方式存儲，但是集中存儲也是可以的，主要分下面這幾種具體的存儲方法：

共用存儲空間: 鍊表的節點和其它的數據共用存儲空間，優點是可以存儲無限多的內容（不過要處理器支持這個大小，並且存儲空間足夠的情況下），不需要提前分配內存；缺點是由於內容分散，有時候可能不方便調試。
獨立存儲空間: 一個鍊表或者多個鍊表使用獨立的存儲空間，一般用數組或者類似結構實現，優點是可以自動獲得一個附加數據：唯一的編號，並且方便調試；缺點是不能動態的分配內存。當然，另外的在上面加一層塊狀鍊表用來分配內存也是可以的，這樣就解決了這個問題。這種方法有時候被叫做數組模擬鍊表，但是事實上只是用表示在數組中的位置的下標索引代替了指向內存地址的指針，這種下標索引其實也是邏輯上的指針，整個結構還是鍊表，並不算是被模擬的（但是可以說成是用數組實現的鍊表）。

鍊表的應用

鍊表用來構建許多其它數據結構，如堆棧，隊列和他們的衍生。

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

C代碼實例

範例代碼是一個ADT（抽象數據類型）雙向環形鍊表的基本操作部分的實例（未包含線程安全機制），全部遵從ANSI C標準。

接口聲明

#ifndef LLIST_H
#define LLIST_H

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);

#endif

接口實現

類型定義

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->head.datap = NULL;
    newlist->head.next = &newlist->head;
    newlist->head.prev = &newlist->head;
    newlist->lmsize = elmsize;
    return (void *)newlist;
}

int llist_delete(LLIST_T *ptr) {
    struct llist_st *me = ptr;
    struct node_st *curr, *save;
    for (curr = me->head.next ;
            curr != &me->head ; curr = save) {
        save = curr->next;
        free(curr->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->datap = malloc(me->elmsize);
    if (newnodep->datap == NULL) {
        free(newnodep);
        return -1;
    }
    memcpy(newnodep->datap, datap, me->elmsize);
    me->head.prev->next = newnodep;
    newnodep->prev = me->head.prev;
    me->head.prev = newnodep;
    newnodep->next = &me->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->datap = malloc(me->elmsize);
    if (newnodep->datap == NULL) {
        free(newnodep);
        return -1;
    }
    memcpy(newnodep->datap, datap, me->elmsize);
    me->head.next->prev = newnodep;
    newnodep->next = me->head.next;
    me->head.next = newnodep;
    newnodep->prev = &me->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->head.next;
            curr != &me->head ; curr = curr->next)
        proc(curr->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->head.next;
            curr != &me->head; curr = curr->next) {
        if ( (*comp)(curr->datap, key) == 0 ) {
            struct node_st *_next, *_prev;
            _prev = curr->prev; _next = curr->next;
            _prev->next = _next; _next->prev = _prev;
            free(curr->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->head.next;
            curr != &me->head; curr = curr->next) {
        if ( (*comp)(curr->datap, key) == 0 )
            return curr->datap;
    }
    return NULL;
}

C宏實例

以下代碼摘自Linux 內核2.6.21.5源碼(部分)，展示了鍊表的另一種實現思路，未採用ANSI C標準，採用GNU C標準，遵從GPL版權許可。

struct list_head {
    struct list_head *next, *prev;
};

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
        struct list_head name = LIST_HEAD_INIT(name)

static inline void INIT_LIST_HEAD(struct list_head *list) {
    list->next = list;
    list->prev = list;
}

static inline void __list_add(struct list_head *new,
                              struct list_head *prev,
                              struct list_head *next) {
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

static inline void list_add(struct list_head *new, struct list_head *head) {
    __list_add(new, head, head->next);
}

static inline void __list_del(struct list_head *prev, struct list_head *next) {
    next->prev = prev;
    prev->next = next;
}

static inline void list_del(struct list_head *entry) {
    __list_del(entry->prev, entry->next);
    entry->next = NULL;
    entry->prev = NULL;
}

#define __list_for_each(pos, head) \
        for (pos = (head)->next; pos != (head); pos = pos->next)

#define list_for_each_entry(pos, head, member)                          \
        for (pos = list_entry((head)->next, typeof(*pos), member);      \
             prefetch(pos->member.next), &pos->member != (head);        \
             pos = list_entry(pos->member.next, typeof(*pos), member))

常見用途

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

延伸閲讀

Juan, Angel. Ch20 –Data Structures; ID06 - PROGRAMMING with JAVA (slide part of the book 'Big Java', by CayS. Horstmann) (PDF): 3. 2006 [2011-07-10]. （原始內容 (PDF)存檔於2012-01-06）.
Black, Paul E. Pieterse, Vreda; Black, Paul E. , 編. linked list. Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. 2004-08-16 [2004-12-14]. （原始內容存檔於2009-01-31）.
Antonakos, James L.; Mansfield, Kenneth C., Jr. Practical Data Structures Using C/C++. Prentice-Hall. 1999: 165–190. ISBN 0-13-280843-9.
Collins, William J. Data Structures and the Java Collections Framework. New York: McGraw Hill. 2005: 239–303 [2002]. ISBN 0-07-282379-8.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms. MIT Press. 2003: 205–213, 501–505. ISBN 0-262-03293-7.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. 10.2: Linked lists. Introduction to Algorithms 2nd. MIT Press. 2001: 204–209. ISBN 0-262-03293-7.
Green, Bert F., Jr. Computer Languages for Symbol Manipulation. IRE Transactions on Human Factors in Electronics. 1961, (2): 3–8. doi:10.1109/THFE2.1961.4503292.
McCarthy, John. Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. Communications of the ACM. 1960, 3 (4): 184 [2021-03-15]. doi:10.1145/367177.367199. （原始內容存檔於2013-10-04）.
Knuth, Donald. 2.2.3-2.2.5. Fundamental Algorithms 3rd. Addison-Wesley. 1997: 254–298. ISBN 0-201-89683-4.
Newell, Allen; Shaw, F. C. Programming the Logic Theory Machine. Proceedings of the Western Joint Computer Conference. 1957: 230–240.
Parlante, Nick. Linked list basics (PDF). Stanford University. 2001 [2009-09-21]. （原始內容存檔 (PDF)於2009-03-17）.
Sedgewick, Robert. Algorithms in C. Addison Wesley. 1998: 90–109. ISBN 0-201-31452-5.
Shaffer, Clifford A. A Practical Introduction to Data Structures and Algorithm Analysis. New Jersey: Prentice Hall. 1998: 77–102. ISBN 0-13-660911-2.
Wilkes, Maurice Vincent. An Experiment with a Self-compiling Compiler for a Simple List-Processing Language. Annual Review in Automatic Programming (Pergamon Press). 1964, 4 (1): 1. doi:10.1016/0066-4138(64)90013-8.
Wilkes, Maurice Vincent. Lists and Why They are Useful. Proceeds of the ACM National Conference, Philadelphia 1964 (ACM). 1964, (P–64): F1–1.
Shanmugasundaram, Kulesh. Linux Kernel Linked List Explained. 2005-04-04 [2009-09-21]. （原始內容存檔於2009-09-25）.

參閲

其他數據結構

線性表
順序表
基本數據結構
樹 (資料結構)

外部連結

Description （頁面存檔備份，存於網際網路檔案館） from the Dictionary of Algorithms and Data Structures
Introduction to Linked Lists （頁面存檔備份，存於網際網路檔案館）, Stanford University Computer Science Library
Linked List Problems （頁面存檔備份，存於網際網路檔案館）, Stanford University Computer Science Library
Open Data Structures - Chapter 3 - Linked Lists （頁面存檔備份，存於網際網路檔案館）, Pat Morin
Patent for the idea of having nodes which are in several linked lists simultaneously (note that this technique was widely used for many decades before the patent was granted)