如何编写一个通用的链表

　　编写通用链表是一项复杂的任务，不可能在这一节中把它阐述清楚，这里我们先考虑三个问题。

　　存值还是存指针

　　通用链表首先要做到能够存放任何数据类型的数据，新手常见的做法是定义一个抽象数据类型，需要存放什么，就

定义成什么。如：

　　typedef int Type;

　　typedef struct _DListNode

　　{

　　struct _DListNode* prev;

　　struct _DListNode* next;

　　Type data;

　　}DListNode;

　　这样的链表算不上是通用的，因为你存放整数时编译一次，存放字符串时，重新定义Type再编译一次，存放其他类

型同样要重复这个过程。麻烦不说，关键是没有办法同时使用多个数据类型。我们要找到一种同时可以表示不同数据类

型的类型才行，有人说可以用union，但是数据类型是无穷无尽的，不可能在 union中表示它们的全部。

　　可行的办法有两种。

　　? 存值

　　typedef struct _DListNode

　　{

　　struct _DListNode* prev;

　　struct _DListNode* next;

　　void* data;

　　size_t length;

　　}DListNode;

　　存入时复制一份数据，保存数据的指针和长度。考虑到复制数据会带来性能开销，不合符C语言的风格，而且C语言

中没有构造函数，实现深复制比较麻烦，所以在C语言中以这种方式实现的链表很少见。

　　? 存指针

　　typedef struct _DListNode

　　{

　　struct _DListNode* prev;

　　struct _DListNode* next;

　　void* data;

　　}DListNode;

　　只保存指向对象的指针，存取效率高，是C语言中常见的做法。在存放整数时，可以把void*强制转换成整数使用，

以避免内存分配(在现实中，90%以上的情况下，链表都是存放结构的)。

　　让C++可以调用

　　这不是一个和本书主旨密切相关的话题，因此在这里只是稍微提一下。C++中允许同名函数存在，所以编译器会对函

数名重新编码。当C++代码包含C语言的头文件时，重新编码的函数名如果与C语言库中的原函数名不一致，就会造成找不

到函数的情况。为了让用C语言实现的函数可以在C++中调用，需要在头文件中加点东西才行。

　　#ifdef __cplusplus

　　extern "C" {

　　#endif

　　...

　　#ifdef __cplusplus

　　}

　　#endif

　　它表示如果在C++中调用这里的函数，编译器不能对函数名进行重新编码。

　　完整的接口

　　作为一个通用的链表，接口要比较完整才行，否则无法满足各种情况的需要(提供完整的接口并不违背最小接口原则

)。实现具有完整接口的链表不是件容易的事，在这里你只需要先实现插入删除等基本操作就行了，后面我们会一步一步地继续扩展它的功能。