單鏈表的接口定義：
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 <stdlib.h>
//為單鏈表的結點定義一個結構體.
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:
[email protected])
// 博客地址：http://www.cnblogs.com/archimedes/
#include <stdio.h>
#include <stdlib.h>
#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;
}
