在C这种没有提供基础数据结构的语言里，最适合自己来学习链表的结构了。在上次学C的时候，知道了链表的基础，所以写起来还是比较简单的。最基础的单项链表，每一个节点存储数据和指向下一个节点的指针就可以了。在制作链表的时候，如果使用typedef，一定要给结构起一个名字，因为之后要包含同种类型的指针，会反复使用到。

创建链表和遍历

最简单的单链表，每个节点指向下一个链表，如果没有，就指向NULL。在遍历的时候，时刻检查当前节点的下一个是不是NULL，是的话说明到达了链表的底部。

#include "chapter06/linkedlist.h"

void walk(struct island * islands){

    for (; islands != NULL; islands=islands->next) {
        printf("%s %s %s\n", islands->name, islands->opens, islands->closes);
    }
}

int main(int argc, char *argv[]){

    //创建四个结构
    island island1 = {"island1", "09:00", "17:00", NULL};
    island island2 = {"island2", "08:00", "18:00", NULL};
    island island3 = {"island3", "10:00", "16:00", NULL};
    island island4 = {"island4", "09:00", "15:00", NULL};

    //链在一起
    island1.next = &island2;
    island2.next = &island3;
    island3.next = &island4;

    //用指向第一个节点的指针当做整个链表的指针
    island *linked_islands = &island1;

    //遍历链表
    walk(linked_islands);

}

单链表直接就用指针遍历就可以了，如果当前指针不是null，说明至少存在一个节点，处理完当前节点的数据后，将指针指向next，这样继续判断，如果是NULL了，说明已经遍历完了所有节点。

动态内存分配

在上边的程序中，实际上是写死了4个节点，编译器已经为这个四个节点分配完了空间。在现实里，可能不知道会有几个节点，需要动态的扩展内存，此时就要使用stdlib.h标准库中的malloc和free函数用来动态申请内存和释放内存了。先来创建一个返回一个新建岛的函数：

island * create_new_island(char * name){
    //将void * 指针赋值给 island * 指针
    island *i = malloc(sizeof(island));

    i->name = name;
    i->opens = "09:00";
    i->closes = "18:30";
    i->next = NULL;
    return i;
}

malloc返回的是一个通用指针类型，也就是void * 类型，实际上malloc只是按照大小来申请，所以需要将其转换成我们需要的类型。为了验证可以动态添加，来让用户输入名称：

    //动态输入2个岛名字
    char name[80];

    scanf("%s", name);
    island *i1 = create_new_island(name);

    scanf("%s", name);
    island *i2 = create_new_island(name);

    island5.next = i1;
    i1->next = i2;

    //遍历链表
    walk(linked_islands);

但是遍历之后，发现两个岛的名字是一样的，这是因为我们使用了同一个char 数组指针，只要修改了其中一个，另外一个也会修改，这里可以使用一个新的库函数：string.h库中的strdup()函数。这个函数接受一个char*，然后会将其中的内容复制到堆上，之后返回一个指向这个字符串。注意，由于这个也是动态申请的字符，所以一样需要释放。然后来修改新建岛的代码：

island * create_new_island(char * name){
    island *i = malloc(sizeof(island));

    i->name = strdup(name);
    i->opens = "09:00";
    i->closes = "18:30";
    i->next = NULL;
    return i;
}

这里其他的内容我们都传入了字符串字面量也就是常量，所以没有问题（这里没有用fgets是因为会读取换行符）。之后就可以用全部动态的方式来组成链表了。组成的方式是：首先用一个指针当做链表的头部，设置初始值为NULL。生成第一个节点的时候，这个指针就指向其，然后不再变动。再使用第二个指针表示链表的尾部，最开始的时候也指指向NULL。在第一次新增的时候，指向第一个节点。之后新增加一个节点的时候，先把自己当前指向的节点的next指向下一个节点，然后自己去指向下一个节点也就是最后一个节点。

int main(int argc, char *argv[]){

    island *start = NULL;
    island *current = NULL;
    island *end = NULL;

    char name[6];
    name[0] = 'c';
    name[1] = 'o';
    name[2] = 'n';
    name[3] = 'y';
    name[5] = '\0';

    int j = 33;

    for (; j < 127; j++) {
        name[4] = (char) j;
        current = create_new_island(name);

        if (start == NULL) {
            start = current;
            end = start;
        }

        end->next = current;

        end = end->next;

    }

    walk(start);
}

这里只是一个最简单的用链表存储内容。这里还没有用到增删改查，实际上用到增删改查的时候，选择指针指向那个元素很重要。比如删除的时候，就不能仅仅只用最后一个指针，这样无法完成操作。要遍历到next的next为null，也就是倒数第二个才可以，然后先回收最后一个，然后将倒数第二个的next置为NULL。

释放链表

有了新建链表，就要释放链表，注意释放的顺序很重要。首先是节点里的字符串释放，一个字符串放在堆上，要先释放，否则释放链表的节点之后就要失去对这个字符串的引用。第二是释放链表的顺序，在链表生成的时候，是一个一个链上去，那需要一个一个从尾部释放吗。如果需要一次性释放全部的链表，是不需要的，只需要从最前边开始，用两个指针，一个指向当前，一个指向下一个，先释放当前，然后让当前的指针指向下一个，下一个指向再下一个，再释放当前，一直到当前的指针为NULL为止。

void releaseall(island * linked_island){
    island *current = NULL;
    island *next = NULL;


    if (linked_island == NULL) {
        return;
    } else{
        current = linked_island;
    }

    while (current != NULL) {
        free(current->name);
        next = current->next;
        free(current);
        current = next;
    }

    printf("释放完成\n");

}

Head First C的书里代码和这个逻辑一样，只不过将每个循环最后都做的current = next;放到for循环体里，看着更简明。这是按顺序释放一整条链表。如果从链表中删除元素，就不能简单的这么操作了，必须有一个引用指向被删除的元素，释放完字符串和节点才行。这就是最基础的数据结构了。待之后到专门的数据结构C语言实现中再来看。感觉读入字符串的玩意也很绕，fgets，get,和scanf也各不相同。