单链表概述
单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。
从概念上讲，可以把链表想象成一系列连续的元素，然而，由于这些元素是动态分配的（C语言中使用malloc），切记这些元素通常实际上都是分散在内存空间的
欢迎关注我的个人博客：, 更多精彩文章与您分享
单链表的接口定义：
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元素是链表头元素返回1，否则返回-1
描述 这是一个宏，用来判断element元素是否是list的头元素
复杂度 O(1)
9、list_is_tail
int list_is_tail(const ListElmt *element);
返回值 如果element元素是链表尾元素返回1，否则返回-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
初始化单链表：
void list_init(List *list, void (*destroy)(void *data)) { //初始化list list->size = 0; list->destroy = destroy; //设置为定义的析构函数 list->head = NULL; list->tail = NULL; return;} 回收单链表：
void list_destroy(List *list) {//移除每一个元素 while (list_size(list) > 0) { if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy != NULL) { //不断地移除链表的头结点 list->destroy(data); //调用一个用户定义的函数来释放动态分配的数据. } } //现在没有操作了,释放结构体作为预防措施 memset(list, 0, sizeof(List)); return;} 插入新节点作为指定结点的直接后继结点:
int list_ins_next(List *list, ListElmt *element, const void *data) { ListElmt *new_element; //为结点动态分配存储空间 if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL) //假如分配失败 return -1; // 将元素插入链表 new_element->data = (void *)data; if (element == NULL) { //插入到链表的头部 if (list_size(list) == 0) list->tail = new_element; new_element->next = list->head; list->head = new_element; } else { //插入到除了链表头部以外指定的其他地方 if (element->next == NULL) list->tail = new_element; new_element->next = element->next; element->next = new_element; } list->size++; //表长增加 return 0;} 删除指定结点的直接后继结点:
int list_rem_next(List *list, ListElmt *element, void **data) { ListElmt *old_element; //不允许从一个空的list中移除元素. if (list_size(list) == 0) return -1; // 从list中移除元素. if (element == NULL) { // 移除表头的结点. *data = list->head->data; old_element = list->head; list->head = list->head->next; if (list_size(list) == 1) //如果list只有一个元素，则直接删除尾结点 list->tail = NULL; } else { // 移除非头结点. if (element->next == NULL) return -1; *data = element->next->data; old_element = element->next; element->next = element->next->next; if (element->next == NULL) //移除指定结点后，后继为NULL，则用尾结点指向 list->tail = element; } //释放分配的抽象数据类型. free(old_element); //调整list的长度. * list->size--; return 0;} 注意：list_size、list_head、list_tail、list_is_head、list_is_tail、list_data、list_next 这些宏实现了链表中的一些简单操作，它们提供了快速访问和检测结构体成员的能力。这些操作的时间复杂度都是O(1)
完整的测试代码如下：
// Completed on 2014.10.22 21:00// Language: C99//// 版权所有（C）codingwu (mail: oskernel@126.com) // 博客地址：#include#include #include "list.h"static void print_list(const List *list) { ListElmt *element; int *data, i; fprintf(stdout, "List size is %d\n", list_size(list)); i = 0; element = list_head(list); while (1) { data = list_data(element); fprintf(stdout, "list[%03d]=%03d\n", i, *data); i++; if (list_is_tail(element)) break; else element = list_next(element); } return;}int main(int argc, char **argv) { List list; ListElmt *element; int *data, i; //初始化list list_init(&list, free); element = list_head(&list); for (i = 10; i > 0; i--) { if ((data = (int *)malloc(sizeof(int))) == NULL) return 1; *data = i; if (list_ins_next(&list, NULL, data) != 0) //逐个插入元素 return 1; } print_list(&list); //打印初始list element = list_head(&list); //指向头结点 for (i = 0; i < 7; i++) element = list_next(element); data = list_data(element); fprintf(stdout, "Removing an element after the one containing %03d\n", *data); if (list_rem_next(&list, element, (void **)&data) != 0) //删除指定结点 return 1; print_list(&list); fprintf(stdout, "Inserting 011 at the tail of the list\n"); *data = 11; if (list_ins_next(&list, list_tail(&list), data) != 0) //插入指定结点 return 1; print_list(&list); fprintf(stdout, "Removing an element after the first element\n"); element = list_head(&list); if (list_rem_next(&list, element, (void **)&data) != 0) return 1; print_list(&list); fprintf(stdout, "Inserting 012 at the head of the list\n"); *data = 12; if (list_ins_next(&list, NULL, data) != 0) return 1; print_list(&list); fprintf(stdout, "Iterating and removing the fourth element\n"); element = list_head(&list); element = list_next(element); element = list_next(element); if (list_rem_next(&list, element, (void **)&data) != 0) return 1; print_list(&list); fprintf(stdout, "Inserting 013 after the first element\n"); *data = 13; if (list_ins_next(&list, list_head(&list), data) != 0) return 1; print_list(&list); i = list_is_head(&list, list_head(&list)); fprintf(stdout, "Testing list_is_head...Value=%d (1=OK)\n", i); i = list_is_head(&list, list_tail(&list)); fprintf(stdout, "Testing list_is_head...Value=%d (0=OK)\n", i); i = list_is_tail(list_tail(&list)); fprintf(stdout, "Testing list_is_tail...Value=%d (1=OK)\n", i); i = list_is_tail(list_head(&list)); fprintf(stdout, "Testing list_is_tail...Value=%d (0=OK)\n", i); fprintf(stdout, "Destroying the list\n"); list_destroy(&list); return 0;}