这是我实现的C语言单向链表。单向链表很简单，可以存储任意类型的数据：整型、字符串或指针类型。但是，不要混存。除整型外，链表节点数据由调用者分配和负责释放，即调用者负责提供一个回调函数，当链表释放时，自动调用你提供的这个函数。记住：链表不分配任何用户的数据，仅分配和管理自己的私有数据，因此，分配和释放链表所存放的数据的工作必须由用户来完成。读者可以在测试代码中看到用例。

　　链表需要的文件为：unistd.h，list.h，list.c。测试文件为test.c。以下是代码：

/****************************************************************************************
　* list.h　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 *
　*　 Generic sequential linked list node structure -- can hold any type data.　　　　　　　 *
　*　 cheungmine　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 *
　*　　　　　 Mar. 22, 2008.　 All rights reserved.　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 *
　****************************************************************************************/
#ifndef LIST_H_INCLUDED__
#define LIST_H_INCLUDED__

#ifdef __cplusplus
extern "C" {
#endif

#include "unistd.h"

typedef struct _listnode_t
{
　struct _listnode_t *next;
　union{
　 void　　　　　　　　　　　 *data;
　 struct _list_t *list;
　 const char　 *str;
　 long　　　　　　　　　　　　 key;
　};
}listnode_t;

typedef struct _list_t
{
　size_t　 size; /* count of nodes */
　listnode_t *head;
　listnode_t　 *tail;
}list_t, *list_p;

/**
　* A prototype of callbacked function called by:
　*　 - list_destroy()
　* - list_traverse()
　* - list_node_free()
　* NULL for no use
　*/
typedef void(*pfunc_list_callback)(listnode_t* node);

/**
　* An prototype example of free node data function implemented by caller:
　*/
static void my_listnode_data_free(listnode_t *node)
{
　 free(node->data);
　DBG_TRACE("my_listnode_data_freen");
}

/**
　* A prototype example of traverse implemented by caller:
　*/
static void my_listnode_key_traverse(listnode_t *node)
{
　printf("　　　 key=%ldn", node->key);
}

/**
　* Traverses a list, applied callback functionn for each node
　*/
void
list_traverse(list_t *in_list, pfunc_list_callback pfcb_traversenode);

/**
　* Allocates a empty list from heap, this creates a new list
　*/
list_t*
list_create();

/**
　* Clears a list and free memory, the list cannot be used later
　*/
void
list_destroy(list_t *in_list, pfunc_list_callback　 pfcb_freedata);

/**
　* Creates a new node assigned with data, not allocates for data
　*/
listnode_t*
list_node_create(void* data);

/**
　* Free a list node and it's associated nodes, the freed node cannot be used later
　*/
void
list_node_free(listnode_t* node, pfunc_list_callback　 pfcb_freedata);

/**
　* Creates a new node assigned with a key, not allocates for key
　*/
listnode_t*
list_key_create(long key);

/**
　* Finds prev node of given node
　*/
listnode_t*
list_find_prev(const list_t *in_list, const listnode_t *node);

/**
　* Appends a node to a list at back
　*/
void
list_push_back(list_t *in_list, listnode_t *node);

/**
　* Inserts a node in front of head into a list
　*/
void
list_push_front(list_t *in_list, listnode_t *in_node);

/**
　* Inserts a node after pos node into a list
　*/
void
list_insert_after(list_t *in_list, listnode_t *pos_node, listnode_t *in_node);

/**
　* Inserts a node before pos node into a list
　*/
void
list_insert_before(list_t *in_list, listnode_t *pos_node, listnode_t *in_node);

/**
　* Removes the first node from a list and returns it
　*/
listnode_t*
list_pop_front(list_t *in_list);

/**
　* Removes the last node from a list and returns it
　*/
listnode_t*
list_pop_back(list_t *in_list);

/**
　* Removes all nodes but for list itself
　*/
void
list_clear(list_t *in_list, pfunc_list_callback pfcb);

/**
　* Returns a copy of a list_t from heap
　*/
list_t*
list_copy(list_t list);

/**
　* Concatenates two lists into first list
　*/
void
list_concat(list_t *first, list_t *second);

/**
　* Gets count of nodes in the list
　*/
size_t
list_size(const list_t* in_list);

/**
　* Gets node by index: 0-based. 0 is head
　*/
listnode_t*
list_node_at(const list_t* in_list, size_t index);

/**
　* Slices list off from begin to end, returns begin node
　* Caller should free returned list nodes
　* begin and end can be same one
　*/
listnode_t*
list_slice(list_t* in_list, listnode_t* begin, listnode_t* end);

#ifdef __cplusplus
}
#endif

#endif　 /* LIST_H_INCLUDED__ */


/****************************************************************************************
　* list.c　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 *
　*　 Generic sequential linked list node structure -- can hold any type data.　　　　　　　 *
　*　 cheungmine　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 *
　*　　　　　 Mar. 22, 2008.　 All rights reserved.　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 *
　****************************************************************************************/
#include "list.h"

void
list_traverse(list_t *in_list, pfunc_list_callback pfcb)
{
　listnode_t* node;
　DBG_TRACE("list_traverse:n　　　 size= %ldn", in_list->size);
　if (pfcb) {
　 node = in_list->head;
　 while (node) {
　　 (*pfcb)(node);
　　 node = node->next;
　 }
　}
}

list_t*
list_create()
{
　list_t *list = (list_t*)malloc (sizeof(list_t));
　list->size = 0;
　list->head = list->tail = NULL;

　DBG_TRACE("list_createn");
　return list;
}

void
list_destroy(list_t *in_list, pfunc_list_callback　 pf)
{
　DBG_TRACE("list_destroyn");
　list_clear(in_list, pf);
　free(in_list);
}

listnode_t*
list_node_create(void* data)
{
　listnode_t *node = (listnode_t*)malloc (sizeof(listnode_t));
　node->next = NULL;
　node->data = data;
　DBG_TRACE("list_node_createn");
　return node;
}

void
list_node_free(listnode_t* node, pfunc_list_callbacki pfcb)
{
　listnode_t* next;
　DBG_TRACE("list_node_freen");
　while(node){
　 next = node->next;
　 if (pfcb)
　　 (*pfcb)(node);
　 free(node);
　 node = next;
　}
}

listnode_t*
list_key_create(long key)
{
　listnode_t *node = (listnode_t*)malloc (sizeof(listnode_t));
　node->next = NULL;
　node->key = key;
　DBG_TRACE("list_key_create: key=%ldn", key);
　return node;
}

listnode_t*
list_find_prev(const list_t *in_list, const listnode_t *node)
{
　listnode_t* prev;
　assert(node);
　prev = in_list->head;
　if (prev==node)
　 return NULL;
　while(prev && prev->next!=node) {
　 prev = prev->next;
　}
　assert(prev);
　return prev;
}

void
list_push_back(list_t *in_list, listnode_t *node)
{
　node->next = NULL;

　if (in_list->head)
　{
　 in_list->tail->next = node;
　 in_list->tail = node;
　}
　else
　 in_list->head = in_list->tail = node;

　in_list->size++;
　DBG_TRACE("list_push_backn");
}

void
list_push_front(list_t *in_list, listnode_t *in_node)
{
　in_node->next = in_list->head;
　in_list->head = in_node;

　if (!in_node->next)
　 in_list->tail = in_node;

　in_list->size++;
　DBG_TRACE("list_push_frontn");
}

void
list_insert_after(list_t *in_list, listnode_t *pos_node, listnode_t *in_node)
{
　in_node->next = pos_node->next;
　pos_node->next = in_node;

　if (in_list->tail==pos_node)
　 in_list->tail = in_node;

　in_list->size++;
}

void
list_insert_before(list_t *in_list, listnode_t *pos_node, listnode_t *in_node)
{
　listnode_t* prev_node;
　prev_node = list_find_prev(in_list, pos_node);
　if (prev_node)
　 list_insert_after(in_list, prev_node, in_node);
　else
　 list_push_front(in_list, in_node);
}

listnode_t*
list_pop_front(list_t *in_list)
{
　listnode_t *pop_node = NULL;
　if (in_list->head)
　{
　 pop_node = in_list->head;
　 in_list->head = in_list->head->next;
　 if (in_list->head == NULL)
　　 in_list->tail = NULL;
　 pop_node->next = NULL;
　 in_list->size--;　
　}
　assert(in_list->size >= 0);
　DBG_TRACE("list_pop_frontn");
　return pop_node;
}

listnode_t*
list_pop_back(list_t *in_list)
{
　listnode_t *pop_node = in_list->tail;
　if (in_list->head==pop_node) {
　 in_list->size = 0;
　 in_list->head = in_list->tail = NULL;
　}
　else {
　 assert(pop_node && !pop_node->next);
　 in_list->tail = list_find_prev(in_list, pop_node);
　 assert(in_list->tail);
　 in_list->tail->next = NULL;
　 in_list->size--;
　}
　assert(in_list->size >= 0);
　DBG_TRACE("list_pop_backn");
　return pop_node;
}

void
list_clear(list_t *in_list, pfunc_list_callback pfcb)
{
　listnode_t *node;
　if (pfcb) {
　 while((node = list_pop_front(in_list))){
　　 (*pfcb)(node);
　　 free(node);
　 }　
　}
　else {
　 while((node = list_pop_front(in_list))){
　　 free(node);
　 }
　}
　assert (in_list->size==0);
　DBG_TRACE("list_clearn");
}

list_t*
list_copy(list_t list)
{
　list_t *newlist = (list_t*)malloc (sizeof(list_t));
　*newlist = list;
　DBG_TRACE("list_copyn");
　return newlist;
}

void
list_concat(list_t *first, list_t *second)
{
　if (first->head)
　{
　 if (second->head)
　 {
　　 first->tail->next = second->head;
　　 first->tail = second->tail;
　 }
　}
　else
　 *first = *second;
　second->head = second->tail = NULL;

　first->size += second->size;
　DBG_TRACE("list_concatn");
}

size_t
list_size(const list_t* in_list)
{
　DBG_TRACE("list_size:%ldn", in_list->size);
　return in_list->size;
}

listnode_t*
list_node_at(const list_t* in_list, size_t index)
{
　size_t　 i=0;<br />　listnode_t *node = in_list->head;
　assert(index >=0 && index < in_list->size);
　while (i < index) {
　 node = node->next;
　 i++;
　}
　return node;
}

listnode_t*
list_slice(list_t* in_list, listnode_t* begin, listnode_t* end)
{
　listnode_t* prev;
　assert(end);
　prev = list_find_prev(in_list, begin);

　if (prev==NULL) {
　 assert(begin==in_list->head);
　 in_list->head = end->next;
　 end->next = NULL;
　 if (in_list->tail == end)
　　 in_list->tail = in_list->head;
　}
　else {
　 prev->next = end->next;
　 end->next = NULL;
　 if (in_list->tail == end)
　　 in_list->tail = prev;　
　}
　DBG_TRACE("list_slicen");

　in_list->size = 0;
　prev = in_list->head;
　while(prev) {
　 in_list->size++;　
　 prev = prev->next;
　}

　return begin;
}


/****************************************************************************************
　* unistd.h　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 *
　* 2008-03-15 Last created by cheungmine.　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 *
　*　 All rights reserved by cheungmine.　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 *
　****************************************************************************************/
#ifndef UNISTD_H__
#define UNISTD_H__

/* Standard C header files included */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

/*============================================================================*/

#ifndef HAVE_INT8
　#define HAVE_INT8
　typedef signed char int8; /* NB: non-ANSI compilers may not grok */
　typedef unsigned char uint8, uchar, byte, BYTE;
#endif

#ifndef HAVE_INT16
　#define HAVE_INT16
　typedef short int16;
　typedef unsigned short uint16, word_t, ushort; /* sizeof (uint16) must == 2 */
#endif

#ifndef HAVE_INT32
　#define HAVE_INT32
　typedef int int32;
　typedef unsigned int uint32, size_t, dword_t; /* sizeof (uint32) must == 4 */
　typedef unsigned long ulong;　　　　
#endif

typedef long lresult;

typedef __int64 int64, longlong;
typedef unsigned __int64 uint64, qword_t, ulonglong;

#ifndef BOOL
　typedef int　　　　 BOOL;
　#define TRUE　 1
　#define FALSE 0
#endif

#ifndef RESULT
　#define RESULT　 lresult
　#define _SUCCESS 0
　#define _ERROR　 -1
#endif

#ifndef IN
#define IN
#endif

#ifndef OUT
#define OUT
#endif

#ifndef INOUT
#define INOUT
#endif

#ifndef OPTIONAL
#define OPTIONAL
#endif

#define SIZE_BYTE 1
#define SIZE_ACHAR 1
#define SIZE_WCHAR 2
#define SIZE_SHORT 2
#define SIZE_INT 4
#define SIZE_LONG 4
#define SIZE_FLT 4
#define SIZE_DBL 8
#define SIZE_WORD 2
#define SIZE_DWORD 4
#define SIZE_QWORD 8
#define SIZE_LINT 8
#define SIZE_INT64 8
#define SIZE_UUID 16

#ifdef _DEBUG
　#include <stdarg.h>
　static void DBG_TRACE(const char *fmt, ...) {
　 va_list ap;
　　　　　　　 va_start(ap, fmt);
　　　　　　　 vprintf(fmt, ap);
　　　　　　　 va_end(ap);
　}
#else
　static void DBG_TRACE(const char *fmt, ...){}
#endif

/*============================================================================*/
#endif /*UNISTD_H__*/


最后是测试工程：

//
// test.c - test topology
// cheungmine@gmail.com
// 2008-3
//
#include <stdio.h>
#include <stdlib.h>

#include "list.h"

void list_use_key()
{
　long k;
　list_t*　 lst;
　listnode_t* nod;
　lst = list_create();
　assert(lst);

　for(k=1; k<=10; k++){
　 list_push_back(lst, list_key_create(k));
　}

　list_size(lst);
　list_pop_front(lst);
　list_size(lst);
　list_pop_back(lst);
　list_size(lst);

　list_traverse(lst, my_listnode_key_traverse);

　nod = list_slice(lst, lst->head->next->next, list_find_prev(lst, lst->tail));
　list_node_free(nod, 0);

　list_traverse(lst, my_listnode_key_traverse);

　list_destroy(lst, 0);
}

typedef struct
{
　char * _buff;
　size_t _size;
}blob;

blob* blob_create(size_t n)
{
　blob* p = (blob*) malloc(sizeof(blob));
　p->_buff = (char*) malloc(n);
　p->_size = n;
　DBG_TRACE("blob_createn");
　return p;
}

void blob_free(blob* p)
{
　free(p->_buff);
　p->_size = 0;
　DBG_TRACE("blob_freen");
}

void my_listnode_blob_free(listnode_t *node)
{
　blob_free((blob*)node->data);
}

void my_listnode_blob_traverse(listnode_t *node)
{
　printf("　　 _size: %d, _buff: %sn", ((blob*)node->data)->_size, ((blob*)node->data)->_buff);
}

void list_use_data()
{
　long k;
　list_t*　 lst;
　blob* pb;
　listnode_t* nod;
　lst = list_create();
　assert(lst);

　for(k=1; k<=10; k++){
　 pb = blob_create(50);
　 sprintf_s(pb->_buff, 50, "　　　 this is a blob: %d", k);
　 list_push_back(lst, list_node_create(pb));
　}
　list_size(lst);
　
　nod = list_pop_front(lst);
　DBG_TRACE("Use blob here...n");
　list_node_free(nod, my_listnode_blob_free);
　list_size(lst);

　nod = list_pop_back(lst);
　list_size(lst);
　DBG_TRACE("Use blob here...n");
　list_node_free(nod, my_listnode_blob_free);
　
　list_traverse(lst, my_listnode_blob_traverse);

　nod = list_slice(lst, lst->head->next->next, list_find_prev(lst, lst->tail));
　list_node_free(nod, my_listnode_blob_free);

　list_traverse(lst, my_listnode_blob_traverse);

　list_destroy(lst, my_listnode_blob_free);
}

int main()
{
　printf("==================list_use_key==================n");
　list_use_key();

　printf("==================list_use_data==================n");
　list_use_data();

　printf("-----------------nPress <Enter> for quit! cheungmine@gmail.comn");
　getchar();
　return 0;
}