这篇文章同样是写给同学们滴，我在机房承诺给同学们的链表源代码现在终于兑现啦。

从前我从 VB 转向 C 时，被一个前辈“警告”说，C 语言的指针很难，在 VB 里没有指针的概念，所以我会经历一个相当困难的转型时期。事实证明，这个转型时期比较困难是没错，但是困难并不在指针上。所以其实指针就是个纸老虎，大家不要怕。

什么？哦，什么是链表？好吧……先说说链表本身。链表是由若干个有先后次序的节点组成的图结构，画成图就是这个样子：

单向链表示例

单向链表示例

其中，上图的圆圈代表节点，圆圈里的数字是节点里的数据（当然节点的数据可以是数字以外的很多东西），箭头表示节点之间的连接关系。什么？那六个点是什么？那六个点是省略号啊……

这个时候就要说到链表的作用了。链表能表示怎样的一种情况？看看窗外一排停车位，链表就可以表示那一排停着的车，奔驰的下一个是宝马，宝马下一个是保时捷，保时捷下一个是兰博基尼，还有省略号……此时就有如下一种链表关系：

脑海中高档住宅小区的停车场示意图

脑海中高档住宅小区的停车场示意图

大家不要觉得链表只能写在一行上，像上面这样也是链表，一条蛇扭了扭应该也算是蛇吧。

现在链表是什么、用来做什么都已经说了，那么怎样用 C 语言来表示链表就成了问题了。

C 语言中链表的表示

（本文中对于链表的实现是双向链表，就是说一个节点不仅指向下一个节点，还指向上一个节点。）对于这个问题，我是这样写的：

1
2
3
4
5
struct Node {
    char name[256];
    struct Node *previous;
    struct Node *next;
};

那么，停车位上的车，在内存中的表示可以是这样的：

内存中的车链表

内存中的车链表

上图中的 Address 是指每个对象的内存地址，其值只是举例用，并不是说一定会是这样的。这些地址很可能每次都会不一样。

现在如果表示链表没有问题了，接下来就是，怎样才能创建出一个这样的链表，怎样使用这个链表等。

我需要一架“法拉利”——链表节点的创建

创建链表节点，其实就是动态分配一段内存，再进行一个初始化的过程。我们可以写一个这样的函数：

1
2
3
4
5
struct Node *CreateNode(const char *nodeName) {
    struct Node *p = (struct Node *)malloc(sizeof(struct Node));
    memset(p, 0, sizeof(struct Node));
    strcpy(p->name, nodeName);
}

这个函数将会根据传入的参数，建立一个以参数为名称的节点对象。

我似乎曾经提到过，“谁创建谁释放”，那么接下来就要说链表节点的释放。

链表节点的释放

可能有的同学会说，节点的释放不容易吗，直接进行类似 free(p); 的操作不就可以了吗？这的确是没错的，但是有这么一个“谁创建谁释放”的原则，要是我们想写出更优雅的代码，就需要我们自己写一个函数来释放，当然这不是必须的啦，只是我喜欢……

1
2
3
void ReleaseNode(struct Node *p) {
    free(p);
}

其实在创建和释放的时候，有一些“约定的配对”很有趣，比如 Create 配 Release, Construct 配 Destruct, New 配 Delete 之类的。还有 Remove 与 Delete 是有区别的，Remove 往往是把一部分从一个整体中剥离出来，翻译为“移除”；而 Delete 是指让一个东西永远地消失，翻译为“删除”。不过这些都是题外话，题外话。

链表节点的插入

链表节点的插入，比起之前讲的创建和释放两种操作要复杂。想象一架新的法拉利要停在宝马和保时捷之间，如果我们要这样表达的话，这个插入函数就必须给出三个参数，一个是你想插入什么节点，第二个和第三个表示这个节点要插入在哪两个节点之间。这样做是很麻烦的，需要 3 个参数，还需要指定链表中的两个元素。万一有程序员耍赖，说我要插在宝马和兰博基尼之间，但是之间还有一个保时捷，你是插在它前面呢还是后面呢？

解决的方法还是有的。如果我们认为宝马在保时捷的“前面”的话，那么我们就可以说这个新的法拉利想停在宝马的“后面的空当”，也就是保时捷的“前面的空当”。所以这样的话，我们就可以写一个只有两个参数又无歧义又没有明显漏洞可钻的函数：

1
2
3
4
5
6
7
8
9
10
11
12
struct Node *InsertNodeAfter(struct Node *insertThis, struct Node *afterThis) {
    struct Node *beforeThis = afterThis->next;

    insertThis->next = beforeThis;
    insertThis->previous = afterThis;

    afterThis->next = insertThis;
    if (beforeThis != NULL)
        beforeThis->previous = insertThis;

    return insertThis;
}

现在可能有的同学会说，如果我要把节点插入在链表的开头，那我应该插入在哪个节点“之后”呢？当然，这就是上面的那个函数的局限性。不过，你可以写一个类似于上面的函数的 InsertNodeBefore 或者 InsertNodeFirst 也可以啦。限于篇幅，就不写出来了。文章末尾有源码可下载，大家可以参考参考。

链表是怎样“链”成的——链表的形成

有的同学问：“光说插入，插入的话也需要原来有一个链表吧，那原来的链表是怎么出来的？”有句话说得好，世界上本没有路，走的人多了，也就成了路。其实链表的形成也是同理的，世界上本没有链表，节点多了，插入得多了，也就成了链表。

让我们链一个豪华车队吧：

1
2
3
4
5
struct Node *p = CreateNode("Benz");
struct Node *t = CreateNode("BMW");
t = InsertNodeAfter(t, p);
t = InsertNodeAfter(t, CreateNode("Porsche"));
t = InsertNodeAfter(t, CreateNode("Lamborghini"));

经过这一番折腾之后，p 指向了这个豪华车队的第一辆车：奔驰；t 指向了这个豪华车队的最后一辆车：兰博基尼。不知道大家有没有看出来呢？上面的代码创建的就是更上面图示的“车队”。

链表的移除

链表的移除与链表的插入是有些类似的，它们算是“相反的操作”。大家可能注意到我这里用词用的是“移除”，为什么不用“删除”呢？上面解释过了，而且也是题外话，就不多说啦。直接上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Node *RemoveNode(struct Node *p) {
    struct Node *previous = p->previous;
    struct Node *next = p->next;

    if (previous != NULL)
        previous->next = next;
    if (next != NULL)
        next->previous = previous;

    p->previous = NULL;
    p->next = NULL;

    return p;
}

OK. 双向链表的实现基本上讲到这里，其实对于双向链表，我还有很多话要说，嘿嘿。

什么？源代码？哦对，代码地址在这里：双向链表的 C 语言实现。

最后，欢迎各位提出宝贵建议。如果我哪里有错误，更请无情地指出，谢谢啦！

原创文章，转载请注明来源：http://euyuil.com/2064/bi-directional-linked-list-in-c/