单链表的实现
现在我们一步步实现单链表。
首先声明数据类型。
typedef struct Node TNode;
struct Node {
void *data;
TNode *next;
};
typedef struct {
TNode *head;
TNode *tail;
} LinkedList;
LinkedList的成员，是两个类型为TNode、且分别指向链表第一个节点及最后一个节点的指针。
第二步，初始化链表。
void initLinkedList(LinkedList *pList) {
pList->head = NULL;
pList->tail = NULL;
}
void printList(const LinkedList *pList) {
if (pList->head == NULL) {
printf("Empty\n");
} else {
}
}
void freeList(const LinkedList *pList) {
TNode *node = pList->head;
while(node != NULL) {
node = node->next;
}
}
int main() {
LinkedList list;
initLinkedList(&list);
printList(&list);
freeList(&list);
}
定义了3个函数，分别用于初始化链表、打印链表，以及释放链表内存。
因涉及到动态内存的分配，因此我们需小心翼翼地跟踪内存分配的细节。我们准备使用malloc函数来申请分配内存。只要一调用此函数，则需立即考虑在合适的位置释放相应的内存。因此，在主程序的最后，我们调用freeList函数以完成内存清理工作。目前，因我们尚未实际分配内存，因此它仅是完成了最基本的遍历工作，尚未真正实现释放内存的功能。
此时状态：
digraph {
rankdir=LR;
node [shape=record];
linkedList [label="linkedList | *head | *tail"];
NULL [shape=point, width=0.15, fillcolor="red"];
linkedList:head, linkedList:tail -> NULL;
}
下面实现添加节点的函数。
void addNode(LinkedList *pList, void *pData) {
TNode *node = malloc(sizeof(TNode));
node->data = pData;
node->next = NULL;
if (pList->head == NULL) {
pList->head = node;
} else {
pList->tail->next = node;
}
pList->tail = node;
}
int main() {
LinkedList list;
initLinkedList(&list);
// codes added
int data = 10;
addNode(&list, &data);
printList(&list);
freeList(&list);
}
此时内存状态如下图所示：
digraph {
rankdir=LR;
subgraph clusterStack {
linkedList [shape=plain, fillcolor=invis, label=<
>];
localVariable [shape=plain, fillcolor=invis, label=<
>];
linkedList -> localVariable [style=invis];
label="Main Function Stack";
}
subgraph clusterHeap {
tnode [shape=plain, fillcolor=invis, label=<
>];
NULL [shape=point, width=0.15, fillcolor="red"];
tnode:next -> NULL [color=gray];
label="Heap";
}
tnode:title -> linkedList:head [dir=back];
tnode:title -> linkedList:tail [dir=back];
tnode:data -> localVariable [color=gray];
}
addNode的主要任务，就是穿针引线。当原来的链表为空时，需要同时将head及tail都指向新创建的节点。而节点与节点的关系仍旧由node来维护。
我们看到，用户所传进的参数pData，其存储在主程序的栈中，不属于在堆上动态分配的内存，因此不需要释放其内存。这里，只有node在堆上动态分配了内存，用完后需要释放内存。因此，我们需在freeList函数释放其内存。修改该函数如下：
void freeList(const LinkedList *pList) {
TNode *node = pList->head;
while(node != NULL) {
printf("Freeing a node... \n");
TNode *currNode = node;
TNode *nextNode = currNode->next;
free(currNode);
node = nextNode;
}
}
这里的要点是，在释放当前节点的内存之前，我们需要先将其所指向的下一节点的地址保存进另一指针变量中，然后再安全地释放当前节点的内存。由于while语句是根据node来遍历的，因此释放内存完毕后，应将node指向下一节点。同时，为确保程序是否清理了内存，函数中加入了打印信息的功能。
做好内存清理工作，再回头完善打印函数。
void printList(const LinkedList *pList) {
if (pList->head == NULL) {
printf("Empty\n");
} else {
TNode *node = pList->head;
while(node != NULL) {
int *data = (int *)node->data;
printf("%d\n", *data);
node = node->next;
}
}
}
我们看到，虽然链表被设计为可以存储任意类型的数据，但要打印这些数据时，需将它们转换回具体类型的指针才能正确打印其结果。
运行程序，终端输出：
10
Freeing a node...
添加的数据被打印了，且最后内存得到了清理。
现在，再添加第二个数据：
LinkedList list;
initLinkedList(&list);
int data1 = 10;
addNode(&list, &data1);
int data2 = 20;
addNode(&list, &data2);
printList(&list);
freeList(&list);
内存示意图：
digraph {
rankdir=LR;
subgraph clusterStack {
linkedList [shape=plain, fillcolor=invis, label=<
>];
localData1 [shape=plain, fillcolor=invis, label=<
>];
localData2 [shape=plain, fillcolor=invis, label=<
>];
linkedList -> localData1 -> localData2 [style=invis];
label="Main Function Stack";
}
subgraph clusterHeap {
tnode1 [shape=plain, fillcolor=invis, label=<
>];
tnode2 [shape=plain, fillcolor=invis, label=<
>];
NULL [shape=point, width=0.15, fillcolor="red"];
tnode1:next -> tnode2 [color=gray];
tnode2:next -> NULL [color=gray];
label="Heap";
}
tnode1:title -> linkedList:head [dir=back, color=green];
tnode2:title -> linkedList:tail [dir=back, color=cyan];
tnode1:data -> localData1 [color=gray];
tnode2:data -> localData2 [color=gray];
}
这里可以更为清晰地看出，linkedList只负责维护第一个及最后一个节点，而各个节点之间的链路，则由各节点自行维护。
linkedList除了维护第一个节点之外，还有指向最后一个节点的指针，这对于在最后添加新节点是很有必要的，否则，每次添加新节点，都得从头开始遍历，顺藤摸瓜，费时费力才能定位到最后的节点。
在实现链表的过程中，我们也感受到了指针的强大威力所在。addNode函数的pData，如果将其数据类型改为int，则只能处理该数据类型，对其他的数据类型则无能为力了。而在我们将其数据类型设置为能接受任意类型的指针后，我们的链表就能动态地存储任意的数据类型。其原理是，不管是何数据类型，它们的指针的字长都是一样的。而指定并保存了指针，在需要时就可访问该指针所指向的地址并取出其数据。当然，如上所述，在具体打印数值时，需将void*指针转换为特定类型的指针。而这属于调用者的职责而非链表的职责。在下面我们将进一步通过函数指针来实现通用的打印功能。
上面的例子还有一个问题，即只能存储在函数栈帧中创建的数据，不能存储在堆上创建的数据。存在即是合理。当存在这种情况时，我们就不能在freeList函数中简单地一概释放pData的内存空间了。在上面的例子中，pData所指向的数据属于在栈中自动创建的变量，无需释放，也不能释放。同样，根据谁创建谁负责清理的原则，如果调用者需要存储在堆上动态创建的数据，则由调用者来负责释放其内存。这同样也可通过函数指针来实现。
在打印函数中加入函数指针
在上面的实现中，printList里面内容是linkedList要干的活，但它却被迫干了它不该干的活：
int *data = (int *)node->data;
printf("%d\n", *data);
linkedList只负责存储所有的数据类型的数据，但它并不了解应为何数据类型。调用者负责提供数据，他才是真正的知情人。因此应由他来负责转换数据。
因此，我们需要在printList通过函数指针来实现一种回调机制，调用者向该函数提供一个函数指针，当printList遍历到相应数据后，将以此数据作为参数回调该函数。直白来说，就是"如何打印这个数据我不懂，既然你是数据提供者，就由你代办吧"。具体来说，我们需要分4步来改写上面的代码。
第一步，先声明一个函数指针。
typedef void (*PrintFuncPtr)(void *);
关键字typedef声明了一种名为PrintFuncPtr新的数据类型，它是一个函数指针，所指向的函数，没有返回值，参数类型为void *。
函数原型确定后，其名字也明确了该函数指针的用途：将参数中的数据打印出来。
第二步，在printList函数中使用该函数指针。
void printList(const LinkedList *pList, PrintFuncPtr printPtr) { // modified
if (pList->head == NULL) {
printf("Empty\n");
} else {
TNode *node = pList->head;
while(node != NULL) {
printPtr(node->data); // modified
node = node->next;
}
}
}
形参中添加了类型为PrintFuncPtr的函数指针，然后将数据node->data作为参数回调它。
下面轮到调用者干活了。
第三步，调用者根据PrintFuncPtr的原型来定义一个专门打印int类型的函数。
void printInt(void *data) {
int *p = data;
printf("%d\n", *p);
}
第四步，将printInt这个函数的地址传给printList。
int main() {
LinkedList list;
initLinkedList(&list);
int data1 = 10;
addNode(&list, &data1);
int data2 = 20;
addNode(&list, &data2);
printList(&list, printInt); // modified
freeList(&list);
}
上面这段代码可清晰地看到，调用者原来存储的是int的数据类型，因此，由他来要求按int来打印出来，合情合理。
以后如果需要存储其他类型的数据，例如，数据类型为struct、数组等复合数据，只需再添加相应的函数再将其地址传给printList就行了。可见，函数指针的引入，为我们留出了充分的扩展接口。
仅是简单地声明并使用函数指针，并不会体现出函数指针有多大的价值。但如果在协调不同的协作者之间的职责及任务时，依据相应的设计模式，使用函数指针来编写代码，其强大威力就立即体现出来了。
C语言标准库也有许多这样的应用，较为典型的是stdlib.h中的qsort函数，我们向其传入一个规范了如何排序的函数指针，qsort函数就能依此排序规则对数组进行相应的排序。其结果就是，qsort函数能对任何数据进行排序。
在清理函数中加入函数指针
同样，链表中存储的数据是否动态分配的、是否需要释放其内存，均是调用者的职责。因此，在freeList函数中，我们也需要传入专门清理内存的函数指针。
第一步，先声明一个专用于清理内存的函数指针。
typedef void (*PrintFuncPtr)(void *);
typedef void (*FreeFuncPtr)(void *); // added
第二步，在freeList函数中使用该函数指针。
void freeList(const LinkedList *pList, FreeFuncPtr freePtr) {
TNode *node = pList->head;
while(node != NULL) {
TNode *currNode = node;
TNode *nextNode = currNode->next;
if (freePtr) {
printf("Freeing dynamic data in node, at: %p\n", currNode->data);
freePtr(currNode->data);
}
printf("Freeing node, at: %p\n", currNode);
free(currNode);
node = nextNode;
}
}
如前所述，如果要存储的数据是在栈上自动分配的，则不需要释放其内存。因此，上面加了一个条件语句以同时应对这两种场合。
有一点需注意，在层级上来讲，currNode持有要清理内存的变量，在释放内存时，需先释放子级的内存，再释放父级的内存。
第三步，定义一个释放内存的函数。
void freeMem(void *data) {
free(data);
}
函数内容这么简单，还需要大费周章来改写代码吗？有必要。你敢将free(data)直接放在原来的freeList函数中吗？不敢。因为上面的例子数据在栈中生成，因此不能释放。同样，这个决定应由调用者而不是LinkedList来作出。
第四步，将freeMem这个函数的地址传给freeList。
int main() {
LinkedList list;
initLinkedList(&list);
int data1 = 10;
addNode(&list, &data1);
int data2 = 20;
addNode(&list, &data2);
printList(&list, printInt);
freeList(&list, NULL);
}
对于在栈中分配的数据，不需要释放内存，因此只需将Null作为地址传递给freeList函数即可。在该函数中，只有此参数值为非空时，才会调用清理内存的函数：
if (freePtr) {
...
freePtr(currNode->data);
}
因为我们传入了空值，因此不会调用释放内存的函数。
下面我们可以安全地改写为使用动态分配内存的数据了。
int main() {
LinkedList list;
initLinkedList(&list);
int *data1 = malloc(sizeof(int)); // heap data, need to be freed
*data1 = 10;
addNode(&list, data1);
int *data2 = malloc(sizeof(int)); // heap data, need to be freed
*data2 = 20;
addNode(&list, data2);
printList(&list, printInt);
freeList(&list, freeMem);
}
运行程序，终端显示：
10
20
Freeing dynamic data in node, at: 0x6000026b8040
Freeing node, at: 0x6000026b8050
Freeing dynamic data in node, at: 0x6000026b8060
Freeing node, at: 0x6000026b8070
所有动态分配的内存，最终均得到了释放。我们的程序不会造成内存泄露。我们毕竟是负责任的一方。
从上面的代码可以看出，如何解释数据，如何释放内存，均是调用者的职责。而使用了函数指针的printList函数及freeList函数提供了这样一个相互协同配合的机会：按调用者所提供的函数指针的规范来操作即可。因此调用者应承担起其相应的职责。
而另一方面，由于数据类型及动态分配的代码均集中于一个地方，作为调用者，我们能够快速地明确职责所在，因此职责履行起来也很轻松。
提炼为单独的文件
LinkedList.h文件的内容：
#ifndef linkedlist_h
#define linkedlist_h
#include <stdbool.h>
typedef struct Node TNode;
struct Node {
void *data;
TNode *next;
};
typedef struct {
TNode *head;
TNode *tail;
} LinkedList;
typedef void (*PrintFuncPtr)(int, void *);
typedef void (*FreeFuncPtr)(void *);
typedef bool (*FilterFuncPtr)(void *);
void initLinkedList(LinkedList *pList);
void addNode(LinkedList *pList, void *pData);
void addHead(LinkedList *pList, void *pData);
void addTail(LinkedList *pList, void *pData);
void printList(const LinkedList *pList, PrintFuncPtr printPtr);
void freeList(const LinkedList *pList, FreeFuncPtr freePtr, bool isVerbose);
void printInt(int, void *data);
void freeMem(void *data);
#endif /* linkedlist_h */
LinkedList.c文件的内容：
#include <stdio.h>
#include <stdlib.h>
#include "linkedlist.h"
void initLinkedList(LinkedList *pList) {
pList->head = NULL;
pList->tail = NULL;
}
void printList(const LinkedList *pList, PrintFuncPtr printPtr) {
if (pList->head == NULL) {
printf("Empty\n");
} else {
TNode *node = pList->head;
int index = 0;
while(node != NULL) {
printPtr(index++, node->data);
node = node->next;
}
}
}
void addHead(LinkedList *pList, void *pData) {
TNode *node = malloc(sizeof(TNode));
node->data = pData;
if (pList->head == NULL) {
node->next = NULL;
pList->head = node;
pList->tail = node;
} else {
node->next = pList->head;
pList->head = node;
}
}
void addTail(LinkedList *pList, void *pData) {
TNode *node = malloc(sizeof(TNode));
node->data = pData;
node->next = NULL;
if (pList->head == NULL) {
pList->head = node;
pList->tail = node;
} else {
pList->tail->next = node;
pList->tail = node;
}
}
void addNode(LinkedList *pList, void *pData) {
TNode *node = malloc(sizeof(TNode));
node->data = pData;
node->next = NULL;
if (pList->head == NULL) {
pList->head = node;
} else {
pList->tail->next = node;
}
pList->tail = node;
}
void freeList(const LinkedList *pList, FreeFuncPtr freePtr, bool isVerbose) {
TNode *node = pList->head;
int dataFreed = 0;
int nodesFreed = 0;
while(node != NULL) {
TNode *currNode = node;
TNode *nextNode = currNode->next;
if (freePtr) {
if (isVerbose) {
printf("Freeing dynamic data in node, at: %p\n", currNode->data);
}
freePtr(currNode->data);
dataFreed++;
}
if (isVerbose) {
printf("Freeing node, at: %p\n", currNode);
}
free(currNode);
nodesFreed++;
node = nextNode;
}
printf("%d data are freed.\n", dataFreed);
printf("%d nodes are freed.\n", nodesFreed);
}
void printInt(int index, void *data) {
int *p = data;
printf("Node %d: %d\n", index, *p);
}
void freeMem(void *data) {
free(data);
}
上面的实现，我们还添加了addHead及addTail函数，即方便了链表的管理，同时也为下一步实现队列、栈的功能打下基础。此外，在释放内存时，freeList函数可根据需要打印出不同的信息。
我们的链表虽然目前为止仅实现了一些最基本的功能，还不够强大。但已有用武之地。在目前已经实现的基础上，我利用它来实现了一个内存自动管理的功能。详见自动内存管理。
filter函数
下面的用例是在随机生成的整数中，筛选出符合特定条件的一组数字。
要点有2个。首先是通过筛选函数的指针来植入不同的筛选条件，这个前面已有涉及。其次是接收筛选结果的方式。这是此用例的重点。有两种方式。一是利用栈空间来接收函数返回的数据，二是接收在堆上动态生成的数据。
下面先实现第一种。
先看客户端代码：
void addRandInts(uint32_t upper_bound, uint32_t count) {
for (int i = 1; i <= count; i++) {
uint32_t *data = malloc(sizeof(unsigned int));
*data = arc4random_uniform(upper_bound) + 1;
addTail(&auto_mem_list, data);
}
}
bool filterFunc(void *data) {
if (*((uint32_t *)data) >= 5) {
return true;
}
return false;
}
int main() {
init_mem_manager();
addRandInts(10, 5);
printList(&auto_mem_list, print_uint32);
const uint32_t BUFFER_SIZE = 5;
uint32_t *buffer[BUFFER_SIZE];
int nums = filter(&auto_mem_list, filterFunc, (void *)buffer, BUFFER_SIZE);
if (nums >= 0) {
for (int i = 0; i < nums; i++) {
uint32_t *value = (uint32_t *)buffer[i];
printf("%u\n", *value);
}
}
}
生成5个整数，其范围是[1, 10]。filterFunc函数筛选出其值大于等于5的数值。而在main函数中，先在函数栈帧上开辟能存储5个元素的数组，用以接收从filter函数返回的数据。
由于C语言不会检测数组越界的问题，因此，对于专用于接收从函数返回值的数组，应同时传入数组元素个数以避免数组越界。
int filter(LinkedList *pList, FilterFuncPtr filterPtr, void *buffer[], uint32_t buffSize) {
TNode *node = pList->head;
uint32_t index = 0;
void *localBuffer[buffSize];
while(node != NULL) {
if (filterPtr(node->data)) {
if (index < buffSize) {
buffer[index++] = node->data;
} else {
printf("Buffer size too small. Failed.\n");
return -1;
}
}
node = node->next;
}
return index;
}
对于每个符合条件的数据，先检查是否数组越界，确定不越界后才写入传进来的buffer数组，且最后返回符合筛选条件的数量；而一旦发现数组越界，则直接返回-1。
因此在客户端代码中，需根据函数返回值来判断是否成功。如果成功，才打印其结果。
这种方式有个弊端，虽然我们已经确保了不存在数组越界的风险，但为顺利接收结果，需事先声明足够大的数组空间，否则，就没有下文了。因此这种方式对客户端并不友好。
下面实现第二种方式，即接收在堆上动态生成的一组数据。由于我们已经实现了链表，因此，对于这种动态分配一组数据的情况，非常适合使用链表来存储并返回。
LinkedList *filter(LinkedList *pList, FilterFuncPtr filterPtr) {
TNode *node = pList->head;
LinkedList *list = NULL;
while(node != NULL) {
if (filterPtr(node->data)) {
if (!list) {
list = malloc(sizeof(list));
}
addTail(list, node->data);
}
node = node->next;
}
return list;
}
如果没有符合筛选条件的数据，不会申请内存空间；若有，才会为新链表申请新的内存空间。此时新链表中存储的数值，仍是原来链表中已经分配了内存空间的数据的地址，它们仍由原链表进行管理，因此不会对这些数据再次申请内存空间。
客户端调用代码如下：
int main() {
init_mem_manager();
addRandInts(10, 5);
printList(&auto_mem_list, print_uint32);
LinkedList *list = filter(&auto_mem_list, filterFunc);
if (list) {
printf("result: \n");
printList(list, print_uint32);
free(list);
}
}
这种方式，由于返回的是在堆上动态分配的数据，在使用完毕后，我们需要用时清理内存。但此时我们只需清理第二个链表自身的内存，不能清理它所存储的数据的内存。因为第二个链表中所存储的数据，指向了第一个链表，也即auto_mem_list链表所存储的数据，这些数据的内存空间会由auto_mem_list在程序退出时自动清理。
上面清理第二个链表时也可改写为：
if (list) {
printf("result: \n");
printList(list, print_uint32);
freeList(list, NULL, false);
}
程序运行，其结果为：
Node 0: 7
Node 1: 3
Node 2: 10
Node 3: 2
Node 4: 1
result:
Node 0: 7
Node 1: 10
0 data are freed.
2 nodes are freed.
5 data are freed.
5 nodes are freed.
Good bye!
在随机生成的数据中，符合大于等于5的筛选条件的值共有7和10共两个。第一个链表list仅该链表所占用的内存空间得到了释放，而第二个链表auto_mem_list不仅释放了该链表自身的内存空间，同时也释放了该链表所存储数据所占用的内存空间。
可见，C语言给了我们很大的自由与权利，但权利与义务相对等，我们需要同时承担起相应的职责。如果我们知道我们在干什么，我们就可编写出灵活、强健、安全的代码。
