记录一个链表的实现

前言

时隔半年多没有敲代码了，既然已经在iPad上安装好了iVim，接下来就又可以敲代码了，所以就打算先搓一个最基本的数据结构——链表。

虽然很早以前就看过数据结构，但是一个真正的完整的自己用的链表我还是第一次写，以前的都是在写算法题时需要写的半成品，而且封装非常丑陋，甚至不封装，毕竟是一次性的代码，只要运行通过了就不会再看了。所以这次要写的，是一个完整的封装好看的链表。

准备工作

在正式开始写代码之前还需要一些准备工作，虽然链表是个很简单的数据结构，但是在一些地方的实现上会有所不同，首先需要明确自己要写的是一个什么样的链表。我的想法是，既然不是写算法题，而是自用，那就不用死扣性能，而是要让一个链表包含尽可能多的功能，而且有可复用性，所以列出了以下几点：

带有头节点，头节点用于保存链表的属性，例如长度。
具有前继和后继，能够双向遍历，既双向链表。
头节点的前继指向链表的尾节点，尾节点的后继指向头节点，既循环链表。
保存的数据类型用void*，用memcpy赋值，这个是看大佬的代码学到的，如果是以前我应该会直接使用传入的数据的指针。

所以综上所述，我要写的是一个，带有头节点的万能双向循环链表。

链表的结构体

首先在头文件中创建Node结构体，有三个成员变量，前继、后继和保存的数据：

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

为了后续方便使用，我们再为Node*创建一个别名为LinkList。

1	typedef Node *LinkList;

链表的基本函数

链表的结构就建立好了，接下来就是实现链表的主要功能创建、插入、删除和查找了。

实用的函数

本来应该是这样，我一开始也确实是这样做的，但是在后面写了很多重复的代码之后，才发现有一些重要的会在其他函数中用到的东西应该写在前面，之后在推倒重写了几次之后，才最终得到了令我满意的链表，所以我们先从实用的功能开始写起。

链表头

前面也说过，头节点不用于保存数据，但是我看着头节点的data一直空着，觉得不顺眼，于是就想着让它保存一些其他的东西，最开始想到的就是链表的长度，但是后来又想到，链表的属性可能不止长度呢，只是我现在没想到，如果直接将data用作长度，万一以后我想加入其他的数据该怎么办？于是为了可扩展性，我们再为头节点创建个链表头结构，用于保存长度，和以后可能需要保存的属性：

typedef struct LinkListHeader LinkListHeader;
struct LinkListHeader
{
    size_t length;
    void *info;
};

我为了省事，几乎所有的长度都用size_t代替了，所以记得加上#include<stddef.h>
以后有空再去写个头文件把什么uint之类的都define了，以后就又省事一点了。

因为不是每一个链表都会带有额外的信息，所以为了保持创建函数的简便，我们再单独创建两个函数来获取和设置链表头：

void LinkListSetHeaderInfo(LinkList l, void *info, size_t size)
{
    LinkListHeader *h = (LinkListHeader *)l->data;
    h->info = malloc(size);
    memcpy(h->info, info, size);
}

void *LinkListGetHeaderInfo(LinkList l)
{
    return ((LinkListHeader *)l->data)->info;
}

获取长度和判空

获取长度和判空都是后面常用的函数，所以现在先实现了以后使用也方便。现在已经有了链表头，链表头保存有长度，所以我们可以很轻易的获取链表的长度：

size_t LinkListGetLength(LinkList l)
{
    return ((LinkListHeader *)l->data)->length;
}

既然有了长度，那判空也容易:

int LinkListIsEmpty(LinkList l)
{
    return LinkListGetLength(l) == 0;
}

根据索引获取节点

这个是重点，我就因为这个推倒重写了两次，后面的增删改查都会使用到这个，先声明原型。

1	Node *LinkListGetNode(LinkList l, size_t index);

首先需要制定个标准，例如我的这个链表是从1开始计数，既1就是第一个节点，n就是第n个节点。那么接下来还有两个问题：

当index = 0时应该返回什么？（size_t是无符号的，所以不考虑负数）
当index大于链表的长度时应该返回什么？

首先，这个函数是用于获取数据节点，这个函数不管在什么情况下，都不应返回头节点。试想如果在删除的时候，如果给出了个特殊值，返回了头节点，然后将头节点删除了，后果是非常严重的。而且头节点就是我们的LinkList的变量，不需要通过其他函数获取。

当index=0时，一般来想应该是返回头节点，但是前面说过了如果在删除函数中出现了头节点会很危险。考虑了删除函数，那还要考虑插入函数。假设一个链表含有n个数据，那就有n+1个插入点，所以为了满足插入的需求，我们除了需要返回n个数据节点还需要返回一种特殊值，除了头节点以外，那当然就是NULL了。所以在思考这个的时候我们对于插入的实现也有个基本的想法了，对于NULL做特殊处理也就是在头节点的后面插入，即第一个数据节点之前插入，对于其他数据节点则是在后面插入。

第二个问题，当index大于链表长度时应该返回什么。这个就看个人的想法了，我能想到的就是两种情况，一、返回NULL，二、返回尾节点。正常做法应该是返回NULL，但是上面也提到了，插入函数会对NULL进行特殊处理，也就是说如果在插入时指定了一个很大的数，那它有可能会插入到链表的第一位，这样看起来就非常反直觉，如果返回尾节点，那在删除和通过索引查找的时候也会出现反直觉的情况。所以这个怎么实现就看个人了，下面给出的只是我的写法：

if (LinkListIsEmpty(l) || index == 0)
{
    return NULL;
}
if (index > LinkListGetLength(l))
{
    return l->pre;// 看需求也可NULL
}

在考虑了特殊情况处理之后，就开始写查找的代码了。因为这是一个双向循环链表，所以当然要好好利用它反向查找的特性，如果index大于长度的一半时，我们可以反向查找，这样在最坏的情况下也只用遍历一半的链表。

Node *p = l;
if (index > LinkListGetLength(l) / 2)
{
    for (size_t i = LinkListGetLength(l); i >= index; i—)
    {
        p = p->pre;
    }
}
else
{
    for (size_t i = 0; i < index; i++)
    {
        p = p->next;
    }
}

将上面的代码整合一下就得到了最终的函数了，这里就不重新贴出来了。

链表的创建

首先，我们的链表带有头节点，那么创建的过程就是建立一个头节点：

void LinkListCreate(LinkList *l)
{
    LinkList a = (LinkList)malloc(sizeof(Node));
    a->pre = a;
    a->next = a;
    a->data = malloc(sizeof(LinkListHeader));
    memset(a->data, 0, sizeof(LinkListHeader));
    *l = a;
}

注意，我们要创建的是双向循环链表，所以在初始化头节点时要将前继和后继都指向头节点，这个对于后面的插入操作很重要。以及不要忘记了初始化我们的链表头。

链表的插入

简单说一下链表的插入，假设要在p、q两个节点中插入一个节点a，只需要让a的前继指向p，后继指向q，p的后继指向a，q的前继指向a，节点a就插入到p、q中间了，然后再将链表长度加1就完成了。

依然从简单的开始，双向循环链表可以很容易的实现前插和后插。前插就是在头节点和第一个数据节点之间插入新节点，尾插就是在头节点和尾节点之间插入新节点。

void LinkListInsertFront(LinkList l, void *data, size_t size)
{
    Node *a = (Node *)malloc(sizeof(Node));
    a->pre = l;
    a->next = l->next;
    l->next->pre = a;
    l->next = a;
    a->data = malloc(size);
    memcpy(a->data, data, size);
    ((LinkListHeader *)l->data)->length++;
}

void LinkListInsertTail(LinkList l, void *data, size_t size)
{
    Node *a = (Node *)malloc(sizeof(Node));
    a->pre = l->pre;
    a->next = l;
    l->pre->next = a;
    l->pre = a;
    a->data = malloc(size);
    memcpy(a->data, data, size);
    ((LinkListHeader *)l->data)->length++;
}

这里就能体会到创建的时候，将头节点的前继后继都设为自身的巧妙之处了，这样在链表为空时也能够正常插入，不需要做特殊处理。

然后再实现指定位置插入，这里就要用到前面实现的，通过索引获取节点的函数了，然后在获取插入的节点后面插入新节点：

void LinkListInsert(LinkList l, size_t index, void *data, size_t size)
{
    Node *p = LinkListGetNode(l, index);
    if (p == NULL)
    {
        p = l;
    }
    Node *a = (Node *)malloc(sizeof(Node));
    a->pre = p->pre;
    a->next = p;
    p->pre->next = a;
    p->pre = a;
    a->data = malloc(size);
    memcpy(a->data, data, size);
    ((LinkListHeader *)l->data)->length++;
}

链表的删除

链表的删除让我想起某个漫画，一个女主因为过度使用结怨的能力，然后失去了所有的缘，这里说的缘是和他人的联系，她失去了所有的缘，就是失去了和所有人的联系。实际表现就是，人们不记得有这个人存在，虽然她还活着，但是她无法被任何人察觉。或许，这就是传说中的内存泄漏吧。

链表的删除比插入要简单一点，只要它的前继和后继越过它直接连在一起，它就已经从链表中被删除了，因为它没有被任何一个节点指向。注意，在它彻底被删除之前要先把它释放，不然很有可能就是内存泄漏了（至于为什么只是可能不是肯定，万一在其他地方留有指向它的指针，那还是可以手动释放，但是为了防止忘记释放，应该在删除时就将节点释放）。

这里的删除有两种，删除数据的和不删除数据的。不删除数据是因为之后可以用这个链表实现栈和队列，出栈和出队是弹出数据，而不是把数据一起释放了，所以我们可以把从链表中移除节点和删除数据分开，从链表中移除节点只会释放节点，返回被移除节点的数据。

一样的先从前删和尾删开始：

void *LinkListRemoveFront(LinkList l)
{
    if (LinkListIsEmpty(l))
    {
        return NULL;
    }
    void *data = l->next->data;
    Node *p = l->next->next;
    free(l->next);
    l->next = p;
    p->pre = l;
    free(p);
    ((LinkListHeader *)l->data)->length--;
    return data;
}

void *LinkListRemoveTail(LinkList l)
{
    if (LinkListIsEmpty(l))
    {
        return NULL;
    }
    void *data = l->pre->data;
    Node *p = l->pre->pre;
    free(l->pre);
    l->pre = p;
    p->next = l;
    ((LinkListHeader *)l->data)->length--;
    return data;
}

删除指定索引的节点只需要把删除的节点换成通过索引获取的节点p，然后判空改判断p是不是NULL就可以了：

void *LinkListRemove(LinkList l, size_t index)
{
    Node *p = LinkListGetNode(l, index);
    if (p == NULL)
    {
        return NULL;
    }
    void *data = p->data;
    p->next->pre = p->pre;
    p->pre->next = p->next;
    free(p);
    ((LinkListHeader *)l->data)->length--;
    return data;
}

实现了移除节点之后，删除数据的移除节点就非常简单了，直接在上面3个函数外面套上free就好了，代码如下：

void LinkListErase(LinkList l, size_t index)
{
    free(LinkListRemove(l, index));
}

void LinkListEraseFront(LinkList l)
{
    free(LinkListRemoveFront(l));
}

void LinkListEraseTail(LinkList l)
{
    free(LinkListRemoveTail(l));
}

我还特地试了一下，C语言free(NULL)不会报错，所以这里就偷懒不判断返回值是不是NULL了。

链表的查找

首先是通过索引获取节点的数据，经过上面的查找和删除，现在写这个应该很简单了，就不过多赘述，直接贴代码：

void *LinkListGetData(LinkList l, size_t index)
{
    Node *p = LinkListGetNode(l, index);
    if (p == NULL)
    {
        return NULL;
    }
    return p->data;
}

void *LinkListGetDataFront(LinkList l)
{
    if (LinkListIsEmpty(l))
    {
        return NULL;
    }
    return l->next->data;
}

void *LinkListGetDataTail(LinkList l)
{
    if (LinkListIsEmpty(l))
    {
        return NULL;
    }
    return l->pre->data;
}

链表的修改

这个也简单，同样是在链表的查找外面套东西，值得注意的就是赋值用memcpy，代码如下：

void LinkListSetData(LinkList l, size_t index, void *data, size_t size)
{
    void *p = LinkListGetData(l, index);
    if (p == NULL)
    {
        return ;
    }
    memcpy(p, data, size);
}

void LinkListSetDataFront(LinkList l)
{
    void *p = LinkListGetDataFront(l);
    if (p == NULL)
    {
        return ;
    }
    memcpy(p, data, size);
}

void LinkListSetDataTail(LinkList l)
{
    void *p = LinkListGetDataTail(l);
    if (p == NULL)
    {
        return ;
    }
    memcpy(p, data, size);
}

链表的遍历

链表也是一个数组，数组最常用的一个操作应该是遍历，所以还需要实现链表的遍历。直接按索引用for循环来遍历当然也可以，但是通过索引查找数据会重复遍历很多次，性能会很差，所以最好不要通过索引遍历。当然还有可能会这样写for(Node *p = l->next; p != l; p = p->next)这样就不会有上面的问题，但是根据操作的规范，我们不应该直接操作结构的内部数据，应该将它当作黑箱，只使用它的接口。所以我的想法就是为节点也实现几个接口。

首先应该给节点增加Next和Previous操作，但是我这个是循环链表，还需要判断指向的是不是头节点，要解决这个问题有两种方法：

给头节点新增一个parent节点，用于保存头节点，然后将头节点的parent设为NULL，这样就可以很好的辨别头节点了，缺点是节点的成员变量从3个变成了4个，所占的空间增加了33%。
Next和Previous增加一个参数，传递头节点，然后判断返回的节点不为头节点，缺点是多一个参数，而且不好看，反直觉，要是长期使用，那就不应该写得这么奇怪。

这里我选择了第一种，增加parent节点，并且为Node新建一个头文件和c文件，将节点和链表分离，因为事到如今我觉得这个节点不再是链表的附庸了，它也有了自己的函数，和自己的作用，所以是时候把它从链表的文件里分离出来了。

Node的接口也很简单，就是对每个成员变量写个Get/Set，就完成了，因为过于简单繁琐，就不贴代码了，记得再把所有的创建节点的函数都加上parent的赋值。然后给出个用Node遍历的示范，代码如下：

1	for(Node *p = LinkListGetFront(l); NodeGetParent(p); p = NodeGetNext(p))

写到一半人就犯懒了，如果以后每次都写这么长一个for那人肯定会疯掉，这里面有价值的就两个东西，遍历的变量名，也就是p，还有起始位置，所以我们再写个define，代码如下：

1	#define LinkListFor(p,q) for(Node *p = q; NodeGetParent(p); p = NodeGetNext(p))

p为循环用的变量名，q为起始位置。下面附带个反向版本的：
如下：

1	#define LinkListForReverse(p,q) for(Node *p = q; NodeGetParent(p); p = NodeGetPrevious(p))

链表头保存数据大小

这个是可选的，因为突然想到，所以就加进来了。一般链表保存的都是同一种类型的数据，所以它们应该具有相同的大小（如果大小真的不同那就保存指针，指针大小都是相同的），而且链表保存的数据类型在创建时就可以确定，所以我们可以在LinkListHeader里面增加一个成员变量size来保存一个数据的大小，这样就只需要在创建链表的时候指定一次大小，往后的操作都不需要额外传入数据的大小了，这样一行的长度就可以短一些，但是需要写一个函数来获取数据的大小，因为整体比较简单，就不贴代码了，记得修改之前的插入函数和创建函数。

结束

至此链表结构和功能已经基本完成了，能够完成增删查改和遍历，应该就能正常使用了，后续可能会出文章改进，或者先来使用一下我的链表。