C单链表

链表是由一系列互相连接的节点组成的数据结构。通常会有一个节点称为头节点，其他节点顺序跟在头节点后面，最后一个节点称为尾节点。我们可以用指针轻松实现节点之间的连接，动态按需分配每个节点。

这种方法比节点的数组好，使用数组的结果就是创建固定数量的节点，而不管实际需要几个。节点之间的连接是用数组元素的索引实现的。使用数组不如使用动态内存分配和指针灵活。

比如说，如果我们想要改变数组元素的顺序，就需要复制两个元素，而结构体元素可能很大。此外，对于添加或删除元素，不论是为新元素腾出空间或是删除已有元素，都可能需要移动数组的一大部分。

链表有好几种类型，最简单的是单链表，一个节点到下一个节点只有一个连接，连接从头节点开始，到尾节点结束。循环链表没有尾节点，链表的最后一个节点又指向头节点。双链表用了两个链表，一个向前连接，一个向后连接，我们可以在两个方向上查找节点，这类链表更灵活，但是也更难实现。图6-5从理论上解释了这些类型的链表。

图6-5：链表类型

这一节我们来看看如何创建和使用单链表，下面的代码显示了用来支持链表的结构体，Node结构体定义一个节点，它有两个指针，第一个是void指针，持有任意类型的数据，第二个是指向下一个节点的指针。LinkedList结构体表示链表，持有指向头节点和尾节点的指针，当前指针用来辅助遍历链表：

typedef struct _node {
    void *data;
    struct _node *next;
} Node;

typedef struct _linkedList {
    Node *head;
    Node *tail;
    Node *current;
} LinkedList;

我们会开发几个使用这些结构体支持链表功能的函数：

void initializeList(LinkedList*)              初始化链表
void addHead(LinkedList*, void*)              给链表的头节点添加数据
void addTail(LinkedList*, void*)              给链表的尾节点添加数据
void delete(LinkedList*, Node*)               从链表删除节点
Node *getNode(LinkedList*, COMPARE, void*)   返回包含指定数据的节点指针
void displayLinkedList(LinkedList*, DISPLAY) 打印链表

使用链表之前要先初始化，如下所示的initializeList函数执行这个任务，将LinkedList对象的指针传递给函数，函数把结构体里的指针置为NULL：

void initializeList(LinkedList *list) {
    list->head = NULL;
    list->tail = NULL;
    list->current = NULL;
}

addHead和addTail函数分别向链表的头和尾添加数据。在这个链表的实现中，add和delete函数负责分配和释放链表节点用到的内存，这样就不需要链表用户负责了。

在如下所示的addHead函数中，先给节点分配内存，然后把传递给函数的数据赋给结构体的data字段。通过把data以void指针的形式传递，链表就能够持有用户想用的任何类型的数据了。

接下来，我们检查链表是否为空，如果为空，就把尾指针指向节点，然后把节点的next字段赋值为NULL；如果不为空，那么将节点的next指针指向链表头。无论哪种情况，链表头都指向节点：

void addHead(LinkedList *list, void* data) {
    Node *node = (Node*) malloc(sizeof(Node));
    node->data = data;
    if (list->head == NULL) {
        list->tail = node;
        node->next = NULL;
    } else {
        node->next = list->head;
    }
    list->head = node;
}

下面的代码片段展示了initializeList和addHead函数的用法。将三个雇员结构体添加到链表中，图6-6显示了执行这些语句后的内存分配情况。为了简化图，我们去掉了一些箭头，此外，还简化了Employee结构体的name数组。

LinkedList linkedList;

Employee *samuel = (Employee*) malloc(sizeof(Employee));
strcpy(samuel->name, "Samuel");
samuel->age = 32;

Employee *sally = (Employee*) malloc(sizeof(Employee));
strcpy(sally->name, "Sally");
sally->age = 28;

Employee *susan = (Employee*) malloc(sizeof(Employee));
strcpy(susan->name, "Susan");
susan->age = 45;

initializeList(&linkedList);

addHead(&linkedList, samuel);
addHead(&linkedList, sally);
addHead(&linkedList, susan);

图6-6：addHead示例

接下来是addTail函数。它先为新节点分配内存，然后把数据赋给data字段。因为我们总是将节点添加到末尾，所以该节点的next字段被赋值为NULL。如果链表为空，那么head指针就是NULL，就可以把新节点赋给head；如果不为空，那么就将尾节点的next指针赋为新节点。无论如何，我们会将链表的tail指针赋为该节点：

void addTail(LinkedList *list, void* data) {
    Node *node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    if (list->head == NULL) {
        list->head = node;
    } else {
        list->tail->next = node;
    }
    list->tail = node;
}

下面的代码片段说明了addTail函数的用法。这里就不重复列出创建雇员对象的代码了，addTail函数将雇员以跟上例相反的顺序添加进去，这样内存分配情况就跟图6-6一样。

initializeList(&linkedList);

addTail(&linkedList, susan);
addTail(&linkedList, sally);
addTail(&linkedList, samuel);

delete函数从链表删除一个节点。为了简化这个函数，将删除节点的指针作为要传递的参数。函数的用户可能有数据的指针，但是没有持有数据的节点的指针，为了帮助定位节点，我们提供了一个辅助函数getNode来返回节点的指针。getNode函数接受三个参数：

• 指向链表的指针；
• 指向比较函数的指针；
• 指向要查找的数据的指针。

下面是getNode函数的代码，变量node一开始指向链表头，然后我们遍历链表直到找到匹配的节点或者到达链表的末尾。我们调用compare函数来判断当前节点是否匹配。当两个数据相等时，它会返回0。

Node *getNode(LinkedList *list, COMPARE compare , void* data) {
    Node *node = list->head;
    while (node != NULL) {
        if (compare(node->data, data) == 0) {
            return node;
        }
        node = node->next;
    }
    return NULL;
}

compare函数说明了如何在运行时用函数指针来决定用哪个函数执行比较操作，这样会给链表的实现增加可观的灵活性，因为我们不需要在getNode函数中硬编码比较函数的名字。

下面是delete函数，为了保持函数简单，它不会检查链表内的空值和传入的节点。第一个if语句处理删除头节点的情况。如果头节点是唯一的节点，那么将头节点和尾节点置为空值；否则，将头节点赋值为原头节点的下一个节点。

else语句用tmp指针从头到尾遍历链表，不论是将tmp赋值为NULL（表示要找的节点不在链表中），还是tmp的下一个节点就是我们要找的节点，while循环都会结束。这是单链表，所以我们需要知道要删除的目标节点的前一节点是哪个，必需知道这一点才能把前一个节点的next字段赋值为目标节点的下一个节点。在delete函数的末尾，将节点释放。用户负责在调用delete函数之前删除节点指向的数据。

void delete(LinkedList *list, Node *node) {
    if (node == list->head) {
        if (list->head->next == NULL) {
            list->head = list->tail = NULL;
        } else {
            list->head = list->head->next;
        }
    } else {
        Node *tmp = list->head;
        while (tmp != NULL && tmp->next != node) {
            tmp = tmp->next;
        }
        if (tmp != NULL) {
            tmp->next = node->next;
        }
    }
    free(node);
}

下面的代码片段说明了这个函数的使用方法。将三个雇员添加到链表头上，我们用6.4节中提到的compareEmployee函数来进行比较操作：

addHead(&linkedList, samuel);
addHead(&linkedList, sally);
addHead(&linkedList, susan);

Node *node = getNode(&linkedList,
        (int (*)(void*, void*))compareEmployee, sally);
delete(&linkedList, node);

执行这段代码后程序栈和堆的状态如图6-7所示。

图6-7：删除示例

如下所示的displayLinkedList函数说明如何遍历链表，从头节点开始，用第二个参数传入的函数打印每一个元素。将next字段的值赋给节点指针，打印最后一个节点后会结束：

void displayLinkedList(LinkedList *list, DISPLAY display) {
    printf("\nLinked List\n");
    Node *current = list->head;
    while (current != NULL) {
        display(current->data);
        current = current->next;
    }
}

下面说明这个函数用用指针支持数据结构中开发的displayEmployee函数打印链表：

addHead(&linkedList, samuel);
addHead(&linkedList, sally);
addHead(&linkedList, susan);

displayLinkedList(&linkedList, (DISPLAY)displayEmployee);

这段代码的输出如下：

Linked List
Susan     45
Sally     28
Samuel     32