鏈結串列

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

使用鏈結串列結構可以克服陣列鏈結串列需要預先知道數據大小的缺點，鏈結串列結構可以充分利用電腦主記憶體空間，實作靈活的主記憶體動態管理。但是鏈結串列失去了陣列隨機讀取的優點，同時鏈結串列由於增加了結點的指標域，空間開銷比較大。

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

鏈結串列可以在多種程式語言中實作。像Lisp和Scheme這樣的語言的內建資料型態中就包含了鏈結串列的存取和操作。程式語言或物件導向語言，如C/C++和Java依靠易變工具來產生鏈結串列。

歷史

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

結構

單向鏈結串列

鏈結串列中最簡單的一種是單向鏈結串列，它包含兩個域，一個資訊域和一個指標域。這個鏈結指向串列中的下一個節點，而最後一個節點則指向一個空值。

一個單向鏈結串列包含兩個值: 目前節點的值和一個指向下一個節點的鏈結

一個單向鏈結串列的節點被分成兩個部分。第一個部分儲存或者顯示關於節點的資訊，第二個部分儲存下一個節點的地址。單向鏈結串列只可向一個方向節點走訪。

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

相對於下面的雙向鏈結串列，這種普通的，每個節點只有一個指標的鏈結串列也叫單向鏈結串列，或者單鏈結串列，通常用在每次都只會按順序節點走訪這個鏈結串列的時候（例如圖的鄰接表，通常都是按固定順序存取的）。

鏈結串列也有很多種不同的變化：

雙向鏈結串列

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

一個雙向鏈結串列有三個整數值: 數值, 向後的節點鏈結, 向前的節點鏈結

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

雙向鏈結串列也叫雙鏈結串列。雙向鏈結串列中不僅有指向後一個節點的指標，還有指向前一個節點的指標。這樣可以從任何一個節點存取前一個節點，當然也可以存取後一個節點，以至整個鏈結串列。一般是在需要大批次的另外儲存數據在鏈結串列中的位置的時候用。雙向鏈結串列也可以配合下面的其他鏈結串列的擴充使用。

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

環狀鏈結串列

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

指向整個串列的指標可以被稱作存取指標。

用單向鏈結串列構建的環狀鏈結串列

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

另外有一種模擬的環狀鏈結串列，就是在存取到最後一個節點之後的時候，手工的跳躍到第一個節點。存取到第一個節點之前的時候也一樣。這樣也可以實作環狀鏈結串列的功能，在直接用環狀鏈結串列比較麻煩或者可能會出現問題的時候可以用。

塊狀鏈結串列

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

塊狀鏈結串列通過使用可變的順序表的長度和特殊的插入、刪除方式，可以在達到 $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))