单链表的实现

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

list.h

#ifndef list_h
#define list_h

#include <stdlib.h>


/**
 Define a structrue for linked list elements.
 */
typedef struct ListElmt_
{
    void *data;
    struct ListElmt_ *next;
} ListElmt;


/**
 Define astructure 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.m

#include <stdlib.h>
#include <string.h>

#include "list.h"

void list_init(List *list, void (*destroy)(void *data)) {
    list->size = 0;
    list->destroy = destroy;
    list->head = NULL;
    list->tail = NULL;
}


/**
 list_destroy
 */
void list_destroy(List *list) {
    void *data;
    while (list_size(list) > 0) {
        if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy != NULL) {
            list->destroy(data);
        }
    }

    /* No operations are allowed now, but clear the structure as a precaution. */
    memset(list, 0, list_size(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 to 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 to account for the removed element. */
    list->size--;
    return 0;
}