數據結構 鏈表_單鏈表的實現與分析

單鏈表的實現與分析

結構體ListElmt表示鏈表中的單個元素（見示例1），這個結構體擁有兩個成員，就是前面介紹的數據成員和指針成員。

結構體List則表示鏈表這種數據結構（見示例1）。這個結構由5個成員組成：size表示鏈表中元素個數；match並不由鏈表本身使用，而是由鏈表數據結構派生而來的新類型所使用；destroy是封裝之後傳遞給list_init的析構函數；head是指向鏈表中頭結點元素的指針；tail則是指向鏈表中末尾結點元素的指針。

示例1：鏈表抽象數據類型的頭文件

    /*list.h*/  
    #ifndef LIST_H  
    #define LIST_H  
      
    #include <stdio.h>  
    /*Define a structure for linked list elements.*/  
    typedef struct ListElmt_  
    {  
        void *data;  
        struct ListElmt_ *next;  
    } ListElmt;  
      
    /*Define a structure for linked lists.*/  
    typedef struct List_  
    {  
        int size;  
        int (*match)(const void *key1,const void *key2);  
        void (*destroy)(void *data);  
        ListElmt *head;  
        ListElmt *tail;  
    } List;  
      
    /*Public Interface*/  
    void list_init(List *list,void(*destroy)(void *data));  
    void list_destroy(List *list);  
    int list_ins_next(List *list,ListElmt *element,const void *data);  
    int list_rem_next(List *list,listElmt *element,void **data);  
    #define list_size(list)((list)->size)  
      
    #define list_head(list)((list)->head)  
    #define list_tail(list)((list)->tail)  
    #define list_is_head(list,element)(element==(list)->head ? 1 : 0)  
    #define list_is_tail(element)((element)->next==NULL ? 1 : 0)  
    #define list_data(element)((element)->data)  
    #define list_next(element)((element)->next)  
      
    #endif // LIST_H  

list_init

list_init用來初始化一個鏈表以便能夠執行其他操作（見示例2）。

初始化鏈表是一種簡單的操作，只要把鏈表的size成員設置為0，把函數指針成員destroy設置為定義的析構函數，head和tail指針全部設置為NULL即可。

list_init的複雜度為O(1)，因為初始化過程中的所有步驟都能在一段恆定的時間內完成。

示例2：鏈表抽象數據類型的實現

    /*list.c*/  
    #include <stdio.h>  
    #include <string.h>  
      
    #include "lish.h"  
      
    /*list_init*/  
    void list_init(List *list,void(*destroy)(void *data))  
    {  
        list->size = 0;  
        list->destroy = destroy;  
        list->head = NULL;  
        list->tail = NULL;  
      
        return;  
    }  
      
    /*list_destroy*/  
    void list_destroy(List *list)  
    {  
        void *data;  
        /*Remove each element*/  
        while(list_size(list)>0)  
        {  
            if(list_rem_next(list,NULL,(void **)&data)==0 && list->destroy!=NULL)  
            {  
                /*Call a user-defined function to free dynamically allocated data.*/  
                list->destroy(data);  
            }  
        }  
        memset(list,0,sizeof(list));  
        return;  
    }  
      
    /*list_ins_next*/  
    int list_ins_next(List *list,ListElmt *element,const void *data)  
    {  
        ListElmt *new_element;  
          
        /*Allocate storage for the element*/  
        if((new_element=(ListElmt *)malloc(sizeof(ListElmt)))==NULL)  
            return -1;  
        /*insert the element into the list*/  
        new_element->data=(void *)data;  
        if(element == NULL)  
        {  
            /*Handle insertion at the head of the list. */  
            if(list_size(list)==0)  
                list_tail = new_element;  
                  
            new_element->next = list->head;  
            list->head = new_element  
        }  
        else   
        {  
            /*Handle insertion somewhere other than at the head*/  
            if(element->next==NULL)  
                list->tail = new_element;  
              
            new_element->next = element->next;  
            element->next = new_element;  
        }  
        /*Adjust the size of the list of account for the inserted element. */  
        list->size++;  
          
        return 0;  
    }  
      
    /*list_rem_next*/  
    int list_rem_next(List *list,ListElmt *element,void **data)  
    {  
        ListElmt *old_element;  
          
        /*Do not allow removal from an empty list. */  
        if(list_size(list) == 0)  
            return -1;  
          
        /*Remove the element from the list. */  
        if(element == NULL)  
        {  
            /*Handle removal from the head of the list. */  
            *data = list->head->data;  
            old_element = list->head;  
            list->head = list->head->next;  
              
            if(list_size(list) == 1)  
                list->tail = NULL;  
        }  
        else   
        {  
            /*Handle removal from somewhere other than the head. */  
            if(element->next == NULL)  
                return -1;  
              
            *data = element->next->data;  
            old_element = element->next;  
            element->next = element->next->next;  
              
            if(element->next == NULL)  
                list->tail = element;  
        }  
        /*Free the storage allocated by the abstract datatype.*/  
        free(old_element);  
        /*Adjust the size of the list account for the removed element. */  
        list->size--;  
        return 0;  
    }  

list_destroy

list_destroy用來銷毀鏈表（見示例2），其意義就是移除鏈表中的所有的元素。

如果調用list_init時destroy參數不為NULL，則當每個元素被移除時都將調用list_destroy一次。

list_destroy的運行時複雜度為O(n)，n代錶鏈表中的元素個數，這是因為list_rem_next的複雜度為O,而移除每個元素時都將調用list_rem_next一次。

list_ins_next

list_ins_next將一個元素插入由element參數所指定的元素之後（見示例2）。該調用將新元素的數據指向由用戶傳遞進來的數據。向鏈表中插入新元素的處理步驟很簡單，但需要特別小心。有兩種情況需要考慮：插入鏈表頭部和插入其他位置。

一般來說，要把一個元素插入鏈表中，需要將新元素的next指針指向它之後的那個元素，然後將新元素位置之前的結點next指針指向新插入的元素（見圖3）。但是，當從鏈表頭部插入時，新元素之前沒有別的結點了。因此在這種情況下，將新元素的next指針指向鏈表的頭部，然後重置頭結點指針，使其指向新元素。回顧一下前面介面設計，當傳入element為null時代表新的元素將插入鏈表頭部。另外需要註意的是，無論何時當插入的元素位於鏈表末尾時，都必須重置鏈表數據結構的tail成員使其指向新的結點。最後，更新統計鏈表中結點個數的size成員。

list_rem_next

list_rem_next從鏈表中移除由element所指定的元素之後的那個結點（見示例2）。移除的是element之後的那個結點而不是移除element本身。這個調用也需要考慮兩個因素，移除的是頭結點以及移除其餘位置上的結點。

移除操作是很簡單的，但同樣需要註意一些細節問題（見圖4）。一般來說，從鏈表中移除一個元素，需要將移除的目標結點前一個元素的next結點指針指向目標結點的下一個元素。但是，當移除的目標結點是頭指針時，目標結點之前並沒有其他元素了。因此，在這種情況下，只需要將鏈接表的head成員指向目標結點的下一個元素。同插入操作一樣，當傳入的element為NULL時就代錶鏈表的頭結點需要移除。另外，無論何時當移除的目標結點是鏈表的尾部結點時，都必須更新鏈表數據結構中的tail成員，使其指向新的尾結點，或者當移除操作使得整個鏈表為空鏈表時，需要把tail設置為NULL。最後，更新鏈表的size成員，使其減1。當這個調用返回時，data將指向已經移除結點的數據域。

list_rem_next的複雜度為O(1)，因為所有的移除步驟都在恆定的時間內完成。

list_size、list_head、list_tail、list_is_tail、list_data以及list_next

這些巨集實現了一些鏈表中的一些簡單操作（見示例1）。一般來說，它們提供了快速訪問和檢測List和ListElmt結構體中成員的能力。

這些操作的複雜度都是O(1)，因為訪問和檢測結構體成員都可以在恆定的時間內完成。