本頁使用了標題或全文手工轉換

連結串列

維基百科,自由的百科全書
前往: 導覽搜尋

連結串列Linked list)是一種常見的基礎資料結構,是一種線性表,但是並不會按線性的順序儲存資料,而是在每一個節點裡存到下一個節點的指標(Pointer)。由於不必須按順序儲存,連結串列在插入的時候可以達到O(1)的複雜度,比另一種線性表順序表快得多,但是尋找一個節點或者存取特定編號的節點則需要O(n)的時間,而順序表相應的時間複雜度分別是O(logn)和O(1)。

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

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

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

歷史[編輯]

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

結構[編輯]

單向連結串列[編輯]

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

Singly-linked-list.svg
一個單向連結串列包含兩個值: 當前節點的值和一個指向下一個節點的連結

一個單向連結串列的節點被分成兩個部分。第一個部分儲存或者顯示關於節點的資訊,第二個部分儲存下一個節點的位址。單向連結串列只可向一個方向遍歷。

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

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

連結串列也有很多種不同的變化:

雙向連結串列[編輯]

一種更複雜的連結串列是「雙向連結串列」或「雙面連結串列」。每個節點有兩個連線:一個指向前一個節點,(當此「連線」為第一個「連線」時,指向空值或者空清單);而另一個指向下一個節點,(當此「連線」為最後一個「連線」時,指向空值或者空清單)

Doubly-linked-list.svg
一個雙向連結串列有三個整數值: 數值, 向後的節點連結, 向前的節點連結

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

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

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

迴圈連結串列[編輯]

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

指向整個清單的指標可以被稱作存取指標。

Circularly-linked-list.svg
用單向連結串列構建的迴圈連結串列

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

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

塊狀連結串列[編輯]

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

塊狀連結串列透過使用可變的順序表的長度和特殊的插入、刪除方式,可以在達到O( \sqrt n )的複雜度。塊狀連結串列另一個特點是相對於普通連結串列來說節省記憶體,因為不用儲存指向每一個資料節點的指標。

其它擴充功能[編輯]

根據情況,也可以自己設計連結串列的其它擴充功能。但是一般不會在邊上附加資料,因為連結串列的點和邊基本上是一一對應的(除了第一個或者最後一個節點,但是也不會產生特殊情況)。不過有一個特例是如果連結串列支援在連結串列的一段中把前和後指標反向,反向標記加在邊上可能會更方便。

對於非線性的連結串列,可以參見相關的其他資料結構,例如。另外有一種基於多個線性連結串列的資料結構:跳錶,插入、刪除和尋找等基本操作的速度可以達到O(nlogn),和平衡樹一樣。

儲存結構[編輯]

連結串列中的節點不需要以特定的方式儲存,但是集中儲存也是可以的,主要分下面這幾種具體的儲存方法:

共用儲存空間
連結串列的節點和其它的資料共用儲存空間,優點是可以儲存無限多的內容(不過要處理器支援這個大小,並且儲存空間足夠的情況下),不需要提前分配記憶體;缺點是由於內容分散,有時候可能不方便偵錯
獨立儲存空間
一個連結串列或者多個連結串列使用獨立的儲存空間,一般用陣列或者類似結構實作,優點是可以自動獲得一個附加資料:唯一的編號,並且方便偵錯;缺點是不能動態的分配記憶體。當然,另外的在上面加一層塊狀連結串列用來分配記憶體也是可以的,這樣就解決了這個問題。這種方法有時候被叫做陣列模擬連結串列,但是事實上只是用表示在陣列中的位置的下標索引代替了指向記憶體位址的指標,這種下標索引其實也是邏輯上的指標,整個結構還是連結串列,並不算是被模擬的(但是可以說成是用陣列實作的連結串列)。

連結串列的應用[編輯]

連結串列用來構建許多其它資料結構,如堆疊,佇列和他們的衍生。

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

C代碼例項[編輯]

範例代碼是一個ADT(抽象資料類型)雙向環形連結串列的基本操作部分的例項(未包含執行緒安全機制),全部遵從ANSI C標準,由User:JohnBull貢獻,代碼遵從GPL版權許可。

介面宣告[編輯]

#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 llist_st {
        struct node_st head;
        int elmsize;
        int elmnr;
};

初始化和銷毀[編輯]

LLIST_T*
llist_new(int elmsize)
{
        struct llist_st *newlist;
        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->elmsize = 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))

常見用途[編輯]

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

參見[編輯]

其他資料結構[編輯]