单链表的实现与分析

结构体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 re