为什么会有链表

Array 这个数据结构可以定义为是程序在内存中申请的一段连续的内存用于存储特指的数据类型。那么这个时候问题就来了，如果我们希望往表中动态的添加值或删除值该怎么办呢？

以char *s[] 来举例，当我们定义一个s 的字符串，实际上是做了两个动作：

  1. 创建了一个*s 的指针
  2. 并将内存中一个地址赋值给*s

这时我们初始化s 给他一个值hi!，实际上会从s 这个指针指向的地址开始往后写4个char 类型，即4 字节。h i ! 和 \0，我们会注意到s 中的数据只有字符串在内存中的起始地址，没有结尾地址，字符串的结尾是依靠程序读取到\0 来判断的。

这个时候如果我们希望往字符串中再写入，例如ray ，我们就需要先向操作系统申请一块内存空间为7个字节的内存块，然后将原始字符串*s 到\0 之间的所有值（排除\0）依次拷贝给新的字符串，再添加ray\0 ，释放掉原来的*s 来达成目的。这样的拷贝在大段的字符串操作中是inefficient 的，所以如果我们能够通过为每个字符申请更多的空间例如每个字符2 字节，这时既保存字符的值，又保存下一个字符的地址，是不是就能解决动态增加和删除字符串的操作，且更有效率，这就是链表出现的场景。

链表 - 前插型

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int number;
    struct node *next;
} node;

// prepend processing
int main(int argc, char *argv[])
{
    // 1. 定义一个链表
    node *list = NULL;

    for (int i = 1; i < argc; i++)
    {
        // 定义temp 变量
        node *temp = malloc(sizeof(node));
        if (temp == NULL)
        {
            return 1;
        }

        // 对temp 赋值
        temp->number = atoi(argv[i]);
        temp->next = list; // 当保存第一个值时，因为list 初始值为NULL，所以链表的第一个值的next
                           // 就成了NULL 也是十分安全的操作
        list = temp;
        // 释放temp 变量
        // 注意这里，千万不能释放temp，因为会导致刚刚存储的值直接被释放
        // 即使list 已经保存了temp 的地址，但是temp 被释放了，list 指向了一个
        // undefined 内存空间，这个问题是我第一次独立编写链表时写出来的，一定要警戒
        // free(temp);
    }

    node *ptr = list;
    while (ptr != NULL)
    {
        printf("%i\n", ptr->number);
        ptr = ptr->next;
    }
}

链表 - 后插型

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int number;
    struct node *next;
} node;

int main(int argc, char *argv[])
{
    // init list
    node *list = NULL;

    for (int i = 1; i < argc; i++)
    {
        // 申请临时指针temp，为它申请1个node 的空间
        node *temp = malloc(sizeof(node));
        if (temp == NULL) {
            // 判断是否成功为temp 申请到空间
            return 1;
        }
        // 为指针赋值
        temp->number = atoi(argv[i]);
        temp->next = NULL;

        if (list == NULL)
        {
            // 如果此时list 为NULL，则是链表的第一个值，将temp 指针的地址保存到list
            list = temp;
        }
        else
        {
            // 如果list 不为NULL，则要去查找当前链表的最后一个值
            for (node *ptr = list; ptr != NULL; ptr = ptr->next)
            // 做一个迭代，初始值为链表的第一个值
            // 如果当前值的next 值不为NULL，既不为链表的最后一个值
            // 则跳过将表中下一个值的地址赋给ptr
            {
                if (ptr->next == NULL)
                // 直到当前值的next 为NULL，表明该值为这个时候链表的最后一个值
                {
                    // 将temp 新加入的值的地址保存到当前最后一个值的next 中，并跳出循环
                    ptr->next = temp;
                    break;
                }
            }
        }
    }

    node *ptr = list;
    while (ptr != NULL) {
	    // 打印链表
        printf("%i\n", ptr->number);
        ptr = ptr->next;
    }
    // 注意这个版本没有释放链表空间，用free(list) 只能释放指针的空间
}

此时程序的时间复杂度为O(n)。因为每一次添加一个新的值，都需要从第一个值开始迭代查找当前链表的最后一个值，所以我们可以考虑在往链表中写入的同时，来对值进行排序，以减少后续的索引或者说查找的难度。

链表 - 排序的后插型

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int number;
    struct node *next;
} node;

int main(int argc, char *argv[])
{
    node *list = NULL;

    for (int i = 1; i < argc; i++)
    {
        node *temp = malloc(sizeof(node));
        temp->number = atoi(argv[i]);
        temp->next = NULL;

        if (list == NULL)
        {
            list = temp;
        }
        else if (temp->number < list->number)
        {
            // 如果当前插入的值小于链表的第一个值
            // 则将当前值的next 设为链表第一个值的地址
            // 同时将链表的第一个值设置为当前值的地址
            temp->next = list;
            list = temp;
        }
        else
        {
            for (node *ptr = list; ptr != NULL; ptr = ptr->next)
            {
                if (ptr->next == NULL)
                {
                    ptr->next = temp;
                    break;
                }
                if (temp->number < ptr->next->number)
                {
                    temp->next = ptr->next;
                    ptr->next = temp;
                    break;
                }
            }
        }
    }

    node *ptr = list;
    while (ptr->next != NULL)
    {
        printf("%i\n", ptr->number);
        ptr = ptr->next;
    }
}

如上面的代码，我们在每次往链表中添加值时都会检查当前值与迭代中的链表的值的大小，然后判断是插入到链表的开始、中间还是末尾。

for (node *ptr = list; ptr != NULL; ptr = ptr->next)
            {
                if (temp->number < ptr->next->number)
                {
                    temp->next = ptr->next;
                    ptr->next = temp;
                    break;
                }

                if (ptr->next == NULL)
                {
                    ptr->next = temp;
                    break;
                }
            }

注意上面的这段代码，可以编译但是运行会报错Segmentation fault (core dumped)。注意和更上面版本中对于判断值插入到链表中间还是末尾的判断顺序，如果按照下面这段代码的写法，报错的原因在于，我们首先要判断是否有下一个ptr->next，如果有才有ptr->next->number 与当前temp-number 的值的判断，否则会有引起故障（例如在往链表中加入第二个值时，只要当前值比链表的第一个值大，都不会有ptr->next->number 这个值存在，这时就引起报错了）。

链表的优缺点

对于prepend 型的链表来说，每一个insert 的动作，它的时间复杂度是O(1) 这是相当快的。对于append 型的链表来说，每一个insert 的动作，它的时间复杂度是O(n) 相较于不停地申请内存然后进行拷贝，这个效率也不错。所以链表的优势是在它的insert 效率上，这是通过使用更多的内存来达成的（在计算机中通过使用一种资源来减轻对另一种资源的消耗是非常常见的）。

但是链表在search 的时候，相较于固定长度的Array 使用binary search (O(logn))的方法查询值来说，效率就低了。这是因为链表的每一块数据都分散在内存的不同地方，我们只知道链表开始的地址，要想知道链表结束的地址需要不停地迭代通过链表值中的next 中的地址去到下一个内存读取数据，最终到达最后一个值，所以无论是对prepend 还是append 型的链表，其时间复杂度都是O(n)，是无法与binary search 的效率相提并论的。

既然我们知道在计算机中通过多使用一种资源去获得另一种资源的优势（例如链表我们通过多使用内存来达到insert 的高效），那么是否能够通过为每一个值分配更多的内存来实现，不仅insert 的效率更高，同时search 的效率也更高。这是树或者说二叉树就走进了我们的视线，来解决类似的问题。