1、list_init

void list_init(List *list, void (*destroy)(void *data));

返回值 void

描述 初始化由参数list指定的链表，该函数必须在链表做其他操作之前调用，当调用list_destroy时，destroy参数提供了一种释放动态分配数据的方法。如果链表采用malloc动态分配的数据，destroy应该设置为free来释放这些数据

复杂度 O(1)

2、list_destroy

void list_destroy(List *list);

返回值 void

描述 销毁由参数list指定的链表，调用该函数以后任何函数都不能再执行，除非重新执行list_init函数。list_destroy将list中的所有元素都移除，每移除一个元素都会调用此函数

复杂度 O(n) n为链表元素的个数

3、list_ins_next

int list_ins_next(List *list, ListElmt *element, const void *data);

返回值 如果插入元素成功返回0，否则返回-1

描述 在指定的list的element元素后面插入一个元素，如果element为NULL，则在链表的头部插入新的元素，该元素包含一个指向data的指针

复杂度 O(1)

4、list_rem_next

int list_rem_next(List *list, ListElmt *element, void **data);

返回值 如果移除元素成功返回0，否则返回-1

描述 移除在指定的list的element后面的那个元素，如果element为NULL，则移除链表的头元素，调用返回后，data指向已经移除元素的数据

复杂度 O(1)

5、list_size

int list_size(const List *list);

返回值 如果list中元素的个数

描述 这是一个宏，用来计算指定list中元素的个数

复杂度 O(1)

6、list_head

ListElmt *list_head(const List *list);

返回值 指向链表头元素的指针

描述 这是一个宏，返回由参数list指定的链表头元素的指针

复杂度 O(1)

7、list_tail

ListElmt *list_tail(const List *list) ((list)->tail);

返回值 指向链表尾元素的指针

描述 这是一个宏，返回由参数list指定的链表尾元素的指针

复杂度 O(1)

8、list_is_head

int list_is_head(const ListElmt *element);

返回值 如果element元素是链表头元素返回0，否则返回-1

描述 这是一个宏，用来判断element元素是否是list的头元素

复杂度 O(1)

9、list_is_tail

int list_is_tail(const ListElmt *element);

返回值 如果element元素是链表尾元素返回0，否则返回-1

描述 这是一个宏，用来判断element元素是否是list的尾元素

复杂度 O(1)

10、list_data

void *list_data(const ListElmt *element);

返回值 结点中保存的数据

描述 这是一个宏，返回由element元素中保存的数据

复杂度 O(1)

11、list_next

ListElmt *list_next(const ListElmt *element) ;

返回值 返回element所指定结点的下一个结点

描述 这是一个宏，返回链表中element所指定结点的下一个结点

复杂度 O(1)

单链表的实现和分析

抽象数据类型的头文件（list.h）：

#ifndef LIST_H

#define LIST_H

#include

//为单链表的结点定义一个结构体.

typedef struct ListElmt_ {

void *data; //数据域

struct ListElmt_ *next; //指针域

} ListElmt;

//为单链表定义一个结构体.

typedef struct List_ {

int size; //容量

int (*match)(const void *key1, const void *key2); //匹配函数

void (*destroy)(void *data); //撤销操作

ListElmt *head; //头指针

ListElmt *tail; //尾指针

} List;

//公共接口

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

初始化单链表：