【在主畫面加入捷徑】
       
【選擇語系】
繁中 简中

[資料結構] 使用 C 語言:實作鏈結串列 (Linked List)

Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email
【贊助商連結】

    鏈結串列的抽象資料結構

    以下是鏈結串列的抽象資料結構 (ADT):

    L is a list
    
    sub IsEmpty(L): bool
    sub PeekFront(L): result
    sub PeekRear(L): result
    sub At(L, index): result, 0 <= index < size
    sub SetAt(L, index, value): bool, 0 <= index < size
    sub Unshift(L, value): bool
    sub Push(L, value): bool
    sub Shift(L): result
    sub Pop(L): result
    sub InsertAt(L, index, value): bool
    sub RemoveAt(L, index): (result, bool)
    

    由此可知,串列有以下和狀態相關的行為:

    • IsEmpty(L):確認串列是否為空
    • PeekFront(L):檢視串列頭端的元素
    • PeekRear(L):檢視串列尾端的元素
    • At(L, index):檢視串列任意位置的元素
    • SetAt(L, index, value):設置串列任意位置的元素

    除此之外,串列可透過以下方式來操作:

    • Unshift(L, value):從串列頭端放入元素
    • Push(L, value):從串列尾端放入元素
    • Shift(L):從串列頭端移出元素
    • Pop(L):從串列尾端移出元素
    • InsertAt(L, index, value):從串列任意位置放入元素
    • RemoveAt(L, index):從串列任意位置移出元素

    鏈結串列一部分的操作和佇列或雙向佇列重疊,讀者若不熟悉這些部分可再回頭閱讀。

    宣告鏈結串列的類別

    鏈結串列的類別宣告如下:

    class Node:
        data <- empty
        prev <- null
        next <- null
        
    class List:
        head <- null
        tail <- null
        size <- 0
    

    如同我們先前實作佇列般,串列分為內部節點 Node 和主類別 List。等效的 C 語言宣告如下:

    typedef struct node node_t;
    
    struct node {
        int data;
        node_t *prev;
        node_t *next;
    };
    
    typedef struct list list_t;
    
    struct list {
        node_t *head;
        node_t *tail;
        size_t size;
    };

    鏈結串列的建構函式

    以下是 C 語言版本的串列建構函式:

    list_t * list_new(void)
    {
        list_t *lt = malloc(sizeof(list_t));
        if (!lt) {
            return lt;
        }
    
        lt->head = NULL;
        lt->tail = NULL;
        lt->size = 0;
    
        return lt;
    }

    上述建構函式會建立一個空串列,這是傳統的建構函式的寫法。也可以在初始化時塞入一些值,使用方式如下:

    list_t *lt = list_init(4, 6, 8, 5, 7);

    list_init 建構函式中,第一個參數代表串列長度,第二個以後的參數代表實際填入的值。以下是其 C 語言實作:

    list_t * list_init(size_t size, int value, ...)
    {
        list_t *lt = malloc(sizeof(list_t));
        if (!lt) {
            return lt;
        }
    
        node_t *first = node_new(value);
        if (!first) {
            list_free(lt);
            lt = NULL;
            return lt;
        }
        lt->head = first;
        lt->tail = first;
        lt->size = 0;
    
        va_list args;
        va_start(args, value);
        lt->size++;
    
        node_t *temp;
        for (size_t i = 1; i < size; i++) {
            temp = node_new(va_arg(args, int));
            if (temp == NULL) {
                list_free(lt);
                lt = NULL;
                va_end(args);
                return lt;
            }
    
            lt->tail->next = temp;
            temp->prev = lt->tail;
            lt->tail = temp;
    
            lt->size++;
        }
    
        va_end(args);
    
        return lt;
    }

    在此處,我們使用到不定參數相關的一些巨集,這些巨集由 函式庫所提供。使用時會依序使用以下四個巨集:

    • va_list:建立代表參數串列的變數
    • va_start:設置參數串列起始位置
    • va_arg:從參數串列取值
    • va_end:結束此參數串列

    讀者可參考本建構函式來學習如何使用不定參數。

    鏈結串列的解構函式

    以下是以 C 語言實作的解構函式:

    void list_delete(void *self)
    {
        if (!self) {
            return;
        }
    
        node_t *curr = ((list_t *) self)->head;
        while (curr) {
            node_t *temp = curr;
            curr = curr->next;
            free(temp);
        }
    
        free(self);
    }

    同樣的,要先逐一釋放內部節點後,再釋放掉物件本身。

    檢查鏈結串列是否為空

    以下是檢查串列是否為空的虛擬碼:

    sub IsEmpty(L):
        check whether L->head == null
    

    檢查其頭端 head 是否為空即可。以下是等效的 C 語言實作:

    bool list_is_empty(const list_t *self)
    {
        assert(self);
    
        return self->head == NULL;
    }

    檢視鏈結串列頭端的資料

    以下是檢視串列頭端資料的虛擬碼:

    sub PeekFront(L):
        assert not IsEmpty(L)
        
        return L->head->data
    

    先確認串列不為空,再回傳頭端的資料 data 即可。以下是等效的 C 語言實作:

    int list_peek_front(const list_t *self)
    {
        assert(!list_is_empty(self));
    
        return self->head->data;
    }

    檢視鏈結串列尾端的資料

    以下是檢視串列尾端資料的虛擬碼:

    sub PeekRear(L):
        assert not IsEmpty(L)
        
        return L->tail->data
    

    和檢視頭端的情境類似,先確認串列不為空,再回傳其尾端的資料 data 即可。以下是等效的 C 語言實作:

    int list_peek_rear(const list_t *self)
    {
        assert(!list_is_empty(self));
    
        return self->tail->data;
    }

    檢視鏈結串列中任意位置的資料

    以下是檢視串列任意元置元素的虛擬碼:

    sub At(L, index):
        assert not IsEmpty(L)
        assert 0 <= index < Size(L)
        
        p <- L->head
        i <- 0
        while p != null do
            if i == index then
                return p->data
            end if
            
            p <- p->next
            i <- i + 1
        end while
        
        throw Error("No available data")
    

    要先確認串列不為空以及索引值是合法的,接著再進行下一步動作。由於本範例內部以鏈結串列實作,需逐一走訪串列元素,直到符合索引值所在的位置為止。以下是等效的 C 語言實作:

    bool list_at(const list_t *self, size_t index, int *out)
    {
        assert(index < list_size(self));
    
        node_t* curr = self->head;
        size_t i = 0;
        while (curr) {
            if (i == index) {
                *out = curr->data;
                return true;
            }
    
            curr = curr->next;
            i++;
        }
    
        return false;
    }

    由於 C 語言沒有錯誤處理的機制且僅能回傳單一值,所以我們在這裡修改一下該函式的介面。此函式會回傳執行成功與否的狀態,並將回傳值寫在 out 中。使用實例如下:

    // Allocate some memory for `out`.
    int *out = malloc(sizeof(int));
    
    if (list_at(lt, 2, out)) {
        // `out` is valid now.
        // Use `out` here.
    }
    
    // Free `out` later.

    修改鏈結串列任意位置的資料

    以下虛擬碼展示如何修改串列中任意位置的資料:

    sub SetAt(L, index, value):
        assert L != null
        assert 0 <= index < L->size
        
        p <- L->head
        i <- 0
        while p != null do
            if i == index then
                p->data <- value
            end if
            
            p <- p->next
            i <- i + 1
        end while
    

    同樣地,要先確認串列不為空且索引值合法。接著,逐一走訪串列直到符合索引所在的位置,修改元素的值後結束程式。以下是等效的 C 語言實作:

    bool list_set_at(list_t *self, size_t index, int data)
    {
        assert(self);
        assert(index < list_size(self));
    
        node_t* curr = self->head;
        size_t i = 0;
        while (curr) {
            if (i == index) {
                curr->data = data;
                return true;
            }
    
            curr = curr->next;
            i++;
        }
    
        return false;
    }

    同樣地,由於 C 語言沒有錯誤處理的機制,此函式會回傳程式執行成功與否的狀態。

    從鏈結串列尾端放入一個元素

    以下是從鏈結串列尾端放入元素的虛擬碼:

    sub Push(L, data): void
        node <- node_t(data)
        
        if L.size == 0 then
            L.head <- node
            L.tail <- node
        else
            L.tail.next <- node
            node.prev <- L.tail
            L.tail <- node
        end if
    
        L.size += 1
    

    根據串列本身是否為空的處理方式略為不同。以下是等效的 C 程式實作:

    bool list_push(list_t *self, int value)
    {
        assert(self);
    
        node_t *node = node_new(value);
        if (!node) {
            return false;
        }
    
        if (!(self->tail)) {
            self->head = node;
            self->tail = node;
        }
        else {
            self->tail->next = node;
            node->prev = self->tail;
            self->tail = node;
        }
    
        self->size++;
    
        return true;
    }

    從鏈結串列頭端放入一個元素

    以下是從鏈結串列頭端放入元素的虛擬碼:

    sub Unshift(L, value): void
        node <- node_t(value)
        
        if L.head == null then
            L.head <- node
            L.tail <- node
        else
            node.next <- L.head
            L.head.prev <- node
            L.head <- node
        end if
    
        L.size += 1
    

    根據串列本身是否為空的處理方式略為不同。以下是等效的 C 程式實作:

    bool list_unshift(list_t *self, int value)
    {
        assert(self);
    
        node_t *node = node_new(value);
        if (!node) {
            return false;
        }
    
        if (!(self->head)) {
            self->head = node;
            self->tail = node;
        }
        else {
            node->next = self->head;
            self->head->prev = node;
            self->head = node;
        }
    
        self->size++;
    
        return true;
    }

    從鏈結串列尾端取出一個元素

    以下是從鏈結串列尾端放入元素的虛擬碼:

    sub Pop(L): result
        assert not IsEmpty(L)
        
        result <- L.tail.data
        
        if L.head == L.tail then
            delete L.tail
    
            L.head <- null
            L.tail <- null
        else
            p <- L.tail
            L.tail <- p.prev
            delete p
            L.tail.next <- null
        end if
        
        L.size -= 1
        
        return result
    

    根據串列本身的元素為單個或多個,處理方式相異。以下是等效的 C 程式實作:

    int list_pop(list_t *self)
    {
        assert(!list_is_empty(self));
    
        int popped = self->tail->data;
    
        if (self->head == self->tail) {
            free(self->tail);
            self->head = NULL;
            self->tail = NULL;
        }
        else {
            node_t *curr = self->tail;
            self->tail = curr->prev;
            free(curr);
            self->tail->next = NULL;
        }
    
        self->size--;
    
        return popped;
    }

    從鏈結串列頭端取出一個元素

    以下是從串列頭端取出元素的虛擬碼:

    sub Shift(L): result
        assert not IsEmpty(L)
        
        result <- L.head
        
        if L.head == L.tail then
            delete L.head
            
            L.head <- null
            L.tail <- null        
        else
            p <- L.head
            L.head <- p.next
            delete p
            L.head.prev <- null
        end
    
        L.size -= 1
        
        return result
    

    根據串列元素為單個或多個,處理方式有所不同。以下是等效的 C 程式實作:

    int list_shift(list_t *self)
    {
        assert(!list_is_empty(self));
    
        int popped = self->head->data;
    
        if (self->head == self->tail) {
            free(self->head);
            self->head = NULL;
            self->tail = NULL;
        }
        else {
            node_t *curr = self->head;
            self->head = curr->next;
            free(curr);
            self->head->prev = NULL;
        }
    
        self->size--;
    
        return popped;
    }

    從鏈結串列中任意位置放入元素

    以下是從串列中任意位置放入元素的虛擬碼:

    sub InsertAt(L, index, data): void
        if L.size == 0 then
            assert index == 0
        else
            assert 0 <= index <= L.size
        end
        
        node <- node_t(data)
        
        if L.size == 0 then
            L.head <- node
            L.tail <- node
            L.size += 1
            return
        end if
        
        p <- null
        q <- L.head
        i <- 0
        while q.next != null do
            if i == index then
                if p == null then
                    node.next <- q
                    q.prev <- node
                    q <- node
                else
                    p.next <- node
                    q.prev <- node
                    
                    node.prev <- p
                    node.next <- q
                end if
    
                break
            end if
            
            p <- q
            q <- q.next
            i += 1
        end while
        
        if q == L.tail then
            L.tail.next <- node
            node.prev <- L.tail
            L.tail <- node
        end
        
        L.size += 1
    

    當串列為空時,直接放入元素即可。

    走訪串列的方式是以兩個指標來走訪,一個指標指向目前的元素,一個則指向前一個元素。當串列不為空時,可再細分為三個情境:

    • 放在串列頭端
    • 放在串列尾端
    • 放在串列其他位置

    當放在串列頭 (或尾) 端時,會影響串列頭 (或尾) 端指標所指向的元素,故需獨立處理。以下是等效的 C 語言程式碼:

    bool list_insert_at(list_t *self, size_t index, int value)
    {
        assert(self);
    
        if (!(self->head)) {
            assert(index == 0);
        } else {
            assert(0 <= index && index <= self->size);
        }
    
        node_t *node = node_new(value);
        if (!node) {
            return false;
        }
    
        if (!(self->head)) {
            self->head = node;
            self->tail = node;
            self->size++;
            return true;
        }
    
        node_t *p = NULL;
        node_t *q = self->head;
        size_t i = 0;
        while(q->next) {
            if (i == index) {
                if (!p) {
                    node->next = q;
                    q->prev = node;
                    q = node;
                    self->head = q;
                } else {
                    p->next = node;
                    node->prev = p;
    
                    q->prev = node;
                    node->next = q;
                }
    
                break;
            }
    
            p = q;
            q = q->next;
            i++;
        }
    
        if (q == self->tail) {
            q->next = node;
            node->prev = q;
            q = node;
            self->tail = q;
        }
    
        self->size++;
    
        return true;
    }

    從鏈結串列中任意位置取出元素

    在從串列中移出元素時,需考慮以下情境:

    • 串列為空
    • 串列僅單個元素
    • 串列有多個元素

    在本例中,第一個情形直接以錯誤排除,第三個情形需再細分,下文會說明。以下是虛擬碼:

    sub RemoveAt(L, index): result
        assert not IsEmpty(L)
    
        if L.size == 1 then
            assert index == 0
        else
            assert 0 <= index < L.size
        end if
        
        if L.size == 1 then
            result <- L.head.data
            
            delete L.head
            L.head <- null
            L.tail <- null
            L.size -= 1
            
            return result
        end if
        
        p <- null
        q <- L.head
        i <- 0
        while q.next != null do
            if i == index then
                result <- q.data
                
                if p == null then
                    L.head <- q.next
                    delete q
                    L.head.prev <- null
                else
                    p.next <- q.next
                    q.next.prev <- p
                    delete q
                end if
    
                break
            end if
            
            p <- q
            q <- q.next
            i += 1
        end while
        
        if q == L.tail then
            result <- q.data
            L.tail <- q.prev
            delete q
            L.tail.next <- null
        end if
        
        L.size -= 1
        
        return result
    

    當串列僅單個元素時,直接移出該元素即可。

    走訪串列的方式是以兩個指標來走訪,一個指標指向目前的元素,一個則指向前一個元素。當串列有多個元素時,需再區分:

    • 從串列頭端移出元素
    • 從串列尾端移出元素
    • 從串列其他位置移出元素

    當從串列頭 (或尾) 端移出串列時,會影響頭 (或尾) 端指標所指向的元素,故需獨立出來處理。

    int list_remove_at(list_t *self, size_t index)
    {
        assert(!list_is_empty(self));
    
        if (list_size(self) == 1) {
            assert(index == 0);
        }
        else {
            assert(index < list_size(self));
        }
    
        if (list_size(self) == 1) {
            int result = self->head->data;
    
            free(self->head);
            self->head = NULL;
            self->tail = NULL;
            self->size--;
    
            return result;
        }
    
        int result;
    
        node_t *p = NULL;
        node_t *q = self->head;
        size_t i = 0;
        while (q->next) {
            if (i == index) {
                result = q->data;
    
                if (!p) {
                    self->head = q->next;
                    free(q);
                    self->head->prev = NULL;
                }
                else {
                    p->next = q->next;
                    q->next->prev = p;
                    free(q);
                }
    
                break;
            }
    
            p = q;
            q = q->next;
            i++;
        }
    
        if (q == self->tail) {
            result = q->data;
            self->tail = p;
            free(q);
            self->tail->next = NULL;
        }
    
        self->size--;
    
        return result;
    }

    在演算法上的效率

    以下和狀態相關的行為的演算法效率如下:

    • IsEmpty(L)O(1)
    • PeekFront(L)O(1)
    • PeekRear(L)O(1)
    • At(L, index)O(n)
    • SetAt(L, index, value)O(n)

    由此可見,以索引操作串列的效率會比陣列差,如果串列大小不會更動或更動不頻繁的話,或許可考慮改用陣列。

    以下操作串列的方法的演算法效率如下:

    • Unshift(L, value)O(1)
    • Push(L, value)O(1)
    • Shift(L)O(1)
    • Pop(L)O(1)
    • InsertAt(L, index, value)O(n)
    • RemoveAt(L, index)O(n)

    由此可見若串列大小會頻繁更動時,串列的效率會比陣列好。

    【贊助商連結】
    標籤: DATA STRUCTURES
    【贊助商連結】
    【分類瀏覽】