练习32：双向链表

原文：Exercise 32: Double Linked Lists

译者：飞龙

这本书的目的是教给你计算机实际上如何工作，这也包括多种数据结构和算法函数。计算机自己其实并没有太大用处。为了让它们做一些有用的事情，你需要构建数据，之后在这些结构上组织处理。其它编程语言带有实现所有这些结构的库，或者带有直接的语法来创建它们。C需要你手动实现所有数据结构，这使它成为最“完美”的语言，让你知道它们的工作原理。

我的目标是交给你这些数据结构，以及相关算法的知识，来帮助你完成下面这三件事：

• 理解Python、Ruby或JavaScript的data = {"name": "Zed"}到底做了什么。
• 使用数据结构来解决问题，使你成为更好的C程序员。
• 学习数据结构和算法的核心部分，让你知道在特定条件下哪个最好。

数据结构是什么。

“数据结构”这个名称自己就能够解释。它是具有特性模型的数据组织方法。这一模型可能设计用于以新的方法处理数据，也可能只是用于将它们更高效地储存在磁盘上。这本书中我会遵循一些简单的模式来构建可用的数据结构：

• 定义一个结构的主要“外部结构”。
• 定义一个结构的内容，通常是带有链接的节点。
• 创建函数操作它们的函数。

C中还有其它样式的数据结构，但是这个模式效果很好，并且对于你创建的大部分数据结构都适用。

构建库

对于这本书的剩余部分，当你完成这本书之后，你将会创建一个可用的库。这个库会包含下列元素：

• 为每个数据结构编写的头文件.h。
• 为算法编写的实现文件.c。
• 用于测试它们确保有效的单元测试。
• 从头文件自动生成的文档。

你已经实现了c-skeleton（项目框架目录），使用它来创建一个liblcthw项目：

$ cp -r c-skeleton liblcthw
$ cd liblcthw/
$ ls
LICENSE             Makefile        README.md       bin             build           src             tests
$ vim Makefile
$ ls src/
dbg.h               libex29.c       libex29.o
$ mkdir src/lcthw
$ mv src/dbg.h src/lcthw
$ vim tests/minunit.h
$ rm src/libex29.* tests/libex29*
$ make clean
rm -rf build  tests/libex29_tests
rm -f tests/tests.log 
find . -name "*.gc*" -exec rm {} \;
rm -rf `find . -name "*.dSYM" -print`
$ ls tests/
minunit.h  runtests.sh
$

这个会话中我执行了下列事情：

• 复制了c-skeleton。
• 编辑Makefile，将libYOUR_LIBRARY.a改为liblcthw.a作为新的TARGET。
• 创建src/lcthw目录，我们会在里面放入代码。
• 移动src/dbg.h文件到新的目录中。
• 编辑tests/minunit.h，使它使用所包含的#include <lcthw/dbg.h>。
• 移除libex29.*中我们不需要的源文件和测试文件。
• 清理所有遗留的东西。

执行完之后你就准备好开始构建库了，我打算构建第一个数据结构是双向链表。

双向链表

我们将要向liblcthw添加的第一个数据结构是双向链表。这是你能够构建的最简单的数据结构，并且它拥有针对特定操作的实用属性。单向链表通过指向下一个或上一个元素的节点来工作。“双向”链表持有全部这两个指针，而“单向”链表只持有下一个元素的指针。

由于每个节点都有下一个和上一个元素的指针，并且你可以跟踪联保的第一个和最后的元素，你就可以快速地执行一些操作。任何涉及到插入和删除元素的操作会非常快。它对大多数人来说也易于实现。

链表的主要缺点是，遍历它涉及到处理沿途每个单个的指针。这意味着搜索、多数排序以及迭代元素会表较慢。这也意味着你不能直接跳过链表的随机一部分。如果换成数组，你就可以直接索引到它的中央，但是链表不行。也就是说如果你想要访问第十个元素，你必须经过1~9。

定义

正如在这个练习的介绍部分所说，整个过程的第一步，是编程一个头文件，带有正确的C结构定义。

#ifndef lcthw_List_h
#define lcthw_List_h

#include <stdlib.h>

struct ListNode;

typedef struct ListNode {
    struct ListNode *next;
    struct ListNode *prev;
    void *value;
} ListNode;

typedef struct List {
    int count;
    ListNode *first;
    ListNode *last;
} List;

List *List_create();
void List_destroy(List *list);
void List_clear(List *list);
void List_clear_destroy(List *list);

#define List_count(A) ((A)->count)
#define List_first(A) ((A)->first != NULL ? (A)->first->value : NULL)
#define List_last(A) ((A)->last != NULL ? (A)->last->value : NULL)

void List_push(List *list, void *value);
void *List_pop(List *list);

void List_unshift(List *list, void *value);
void *List_shift(List *list);

void *List_remove(List *list, ListNode *node);

#define LIST_FOREACH(L, S, M, V) ListNode *_node = NULL;\
    ListNode *V = NULL;\
    for(V = _node = L->S; _node != NULL; V = _node = _node->M)

#endif

我所做的第一件事就是创建两个结构，ListNode和包含这些节点的List。这创建了是将在函数中使用的数据结构，以及随后定义的宏。如果你浏览这些函数，它们看起来非常简单。当我讲到实现时，我会解释他们，但我更希望你能猜出它们的作用。

这些数据结构的工作方式，就是每个ListNode都有三个成员。

• 值，它是无类型的指针，存储我们想在链表中放置的东西。
• ListNode *next指针，它指向另一个储存下一个元素的ListNode。
• ListNode *prev指针，它指向另一个储存上一个元素的ListNode。

List结构只是这些ListNode结构的容器，它们互联链接组成链型。它跟踪链表的count，first和last元素。

最后，看一看src/lcthw/list.h:37，其中我定义了LIST_FOREACH宏。这是个常见的习语，你可以创建一个宏来生成迭代代码，使用者就不会弄乱了。正确使用这类执行过程来处理数据结构十分困难，所以可以编写宏来帮助使用者。当我讲到实现时，你可以看到我如何使用它。

实现

一旦你理解了它们之后，你很可能理解了双向链表如何工作。它只是带有两个指针的节点，指向链表中前一个和后一个元素。接下来你可以编写src/lcthw/list.c中的代码，来理解每个操作如何实现。

#include <lcthw/list.h>
#include <lcthw/dbg.h>

List *List_create()
{
    return calloc(1, sizeof(List));
}

void List_destroy(List *list)
{
    LIST_FOREACH(list, first, next, cur) {
        if(cur->prev) {
            free(cur->prev);
        }
    }

    free(list->last);
    free(list);
}


void List_clear(List *list)
{
    LIST_FOREACH(list, first, next, cur) {
        free(cur->value);
    }
}


void List_clear_destroy(List *list)
{
    List_clear(list);
    List_destroy(list);
}


void List_push(List *list, void *value)
{
    ListNode *node = calloc(1, sizeof(ListNode));
    check_mem(node);

    node->value = value;

    if(list->last == NULL) {
        list->first = node;
        list->last = node;
    } else {
        list->last->next = node;
        node->prev = list->last;
        list->last = node;
    }

    list->count++;

error:
    return;
}

void *List_pop(List *list)
{
    ListNode *node = list->last;
    return node != NULL ? List_remove(list, node) : NULL;
}

void List_unshift(List *list, void *value)
{
    ListNode *node = calloc(1, sizeof(ListNode));
    check_mem(node);

    node->value = value;

    if(list->first == NULL) {
        list->first = node;
        list->last = node;
    } else {
        node->next = list->first;
        list->first->prev = node;
        list->first = node;
    }

    list->count++;

error:
    return;
}

void *List_shift(List *list)
{
    ListNode *node = list->first;
    return node != NULL ? List_remove(list, node) : NULL;
}

void *List_remove(List *list, ListNode *node)
{
    void *result = NULL;

    check(list->first && list->last, "List is empty.");
    check(node, "node can't be NULL");

    if(node == list->first && node == list->last) {
        list->first = NULL;
        list->last = NULL;
    } else if(node == list->first) {
        list->first = node->next;
        check(list->first != NULL, "Invalid list, somehow got a first that is NULL.");
        list->first->prev = NULL;
    } else if (node == list->last) {
        list->last = node->prev;
        check(list->last != NULL, "Invalid list, somehow got a next that is NULL.");
        list->last->next = NULL;
    } else {
        ListNode *after = node->next;
        ListNode *before = node->prev;
        after->prev = before;
        before->next = after;
    }

    list->count--;
    result = node->value;
    free(node);

error:
    return result;
}

我实现了双向链表上的所有操作，它们不能用简单的宏来完成。比起覆盖文件中的每一行，我打算为list.h和list.c中的每个操作提供一个高阶的概览。你需要自己阅读代码。

list.h:List_count

返回链表中元素数量，它在元素添加或移除时维护。

list.h:List_first

返回链表的首个元素，但是并不移除它。

list.h:List_last

返回链表的最后一个元素，但是不移除它。

list.h:LIST_FOREACH

遍历链表中的元素。

list.c:List_create

简单地创建主要的List结构。

list.c:List_destroy

销毁List以及其中含有的所有元素。

list.c:List_clear

为释放每个节点中的值（而不是节点本身）创建的辅助函数。

list.c:List_clear_destroy

清理并销毁链表。它并不十分搞笑因为它对每个元素遍历两次。

list.c:List_push

第一个操作演示了链表的有点。它向链表尾添加新的元素，由于只是一些指针赋值，所以非常快。

list.c:List_pop

List_push的反向版本，它去除最后一个元素并返回它。

list.c:List_unshift

亦可以轻易对链表执行的另一件事，就是快速地向链表头部添加元素。由于找不到合适的词，这里我把它称为unshift。

list.c:List_shift

类似List_pop，但是它移除链表的首个元素并返回。

list.c:List_remove

当你执行List_pop或List_shift时，它执行实际的移除操作。在数据结构中移除数据总是看似比较困难，这个函数也不例外。它需要处理一些条件，取决于被移除的位置，在开头、在结尾、开头并且结尾，或者在中间。

这些函数大多数都没什么特别的，你应该能够轻易描述出来，并且根据代码来理解它。你应该完全专注于List_destroy中的LIST_FOREACH如何使用来理解它如何简化通常的操作。

测试

在你编译它们之前，需要创建测试来确保它们正确执行。

#include "minunit.h"
#include <lcthw/list.h>
#include <assert.h>

static List *list = NULL;
char *test1 = "test1 data";
char *test2 = "test2 data";
char *test3 = "test3 data";


char *test_create()
{
    list = List_create();
    mu_assert(list != NULL, "Failed to create list.");

    return NULL;
}


char *test_destroy()
{
    List_clear_destroy(list);

    return NULL;

}


char *test_push_pop()
{
    List_push(list, test1);
    mu_assert(List_last(list) == test1, "Wrong last value.");

    List_push(list, test2);
    mu_assert(List_last(list) == test2, "Wrong last value");

    List_push(list, test3);
    mu_assert(List_last(list) == test3, "Wrong last value.");
    mu_assert(List_count(list) == 3, "Wrong count on push.");

    char *val = List_pop(list);
    mu_assert(val == test3, "Wrong value on pop.");

    val = List_pop(list);
    mu_assert(val == test2, "Wrong value on pop.");

    val = List_pop(list);
    mu_assert(val == test1, "Wrong value on pop.");
    mu_assert(List_count(list) == 0, "Wrong count after pop.");

    return NULL;
}

char *test_unshift()
{
    List_unshift(list, test1);
    mu_assert(List_first(list) == test1, "Wrong first value.");

    List_unshift(list, test2);
    mu_assert(List_first(list) == test2, "Wrong first value");

    List_unshift(list, test3);
    mu_assert(List_first(list) == test3, "Wrong last value.");
    mu_assert(List_count(list) == 3, "Wrong count on unshift.");

    return NULL;
}

char *test_remove()
{
    // we only need to test the middle remove case since push/shift 
    // already tests the other cases

    char *val = List_remove(list, list->first->next);
    mu_assert(val == test2, "Wrong removed element.");
    mu_assert(List_count(list) == 2, "Wrong count after remove.");
    mu_assert(List_first(list) == test3, "Wrong first after remove.");
    mu_assert(List_last(list) == test1, "Wrong last after remove.");

    return NULL;
}


char *test_shift()
{
    mu_assert(List_count(list) != 0, "Wrong count before shift.");

    char *val = List_shift(list);
    mu_assert(val == test3, "Wrong value on shift.");

    val = List_shift(list);
    mu_assert(val == test1, "Wrong value on shift.");
    mu_assert(List_count(list) == 0, "Wrong count after shift.");

    return NULL;
}



char *all_tests() {
    mu_suite_start();

    mu_run_test(test_create);
    mu_run_test(test_push_pop);
    mu_run_test(test_unshift);
    mu_run_test(test_remove);
    mu_run_test(test_shift);
    mu_run_test(test_destroy);

    return NULL;
}

RUN_TESTS(all_tests);

它简单地遍历了每个操作，并且确保它们有效。我在测试中做了简化，对于整个程序我只创建了一个List *list，这解决了为每个测试构建一个List的麻烦，但它同时意味着一些测试会受到之前测试的影响。这里我试着是每个测试不改变链表，或实际使用上一个测试的结果。

你会看到什么

如果你正确完成了每件事，当你执行构建并且运行单元测试是，你会看到：

$ make
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG  -fPIC   -c -o src/lcthw/list.o src/lcthw/list.c
ar rcs build/liblcthw.a src/lcthw/list.o
ranlib build/liblcthw.a
cc -shared -o build/liblcthw.so src/lcthw/list.o
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG  build/liblcthw.a    tests/list_tests.c   -o tests/list_tests
sh ./tests/runtests.sh
Running unit tests:
----
RUNNING: ./tests/list_tests
ALL TESTS PASSED
Tests run: 6
tests/list_tests PASS
$

确保6个测试运行完毕，以及构建时没有警告或错误，并且成功构建了build/liblcthw.a和build/liblcthw.so文件。

如何改进

我打算告诉你如何改进代码，而不是使它崩溃。

• 你可以使用LIST_FOREACH并在循环中调用free来使List_clear_destroy更高效。
• 你可以为一些先决条件添加断言，使其部结构NULL值作为List *list的参数。
• 你可以添加不变了，来检查列表的内容始终正确，例如count永远不会< 0，如果count > 0，first不为NULL。
• 你可以向头文件添加文档，在每个结构、函数和宏之前添加描述其作用的注释。

这些改进执行了防御性编程实践，并且“加固”了代码来避免错误或使用不当。马上去做这些事情，之后找到尽可能多的办法来改进代码。

附加题

• 研究双向和单向链表，以及什么情况下其中一种优于另一种。
• 研究双向链表的限制。例如，虽然它们对于插入和删除元素很高效，但是对于变量元素比较慢。
• 还缺少什么你能想到的操作？比如复制、连接、分割等等。实现这些操作，并且为它们编写单元测试。