2.12.1 链表

链表，是一种和数组并不相同的数据结构

链表的内存并不要求连续，它们通过彼此的指针(地址)连接

即链表由多个节点构成，每个节点之间通过指针进行连接

单个节点的定义

我们举个例子我们现在要做一个存储int类型数据的链表并且我只进行单向连接(即只能从上个节点找到下个节点，但不能从下个节点回到上个节点)

typedef struct Node
{
    int data;
    struct Node* next;
}node;

这就是一个节点 data存储我们要存储的数据而struct Node* next就是指向下一个节点的地址的指针

创建一个节点的函数

Node* createNode(int data)
{
    Node* newNode = (Node*)malloc(sizeof(Node));

    newNode->data = data;
    newNode->next = NULL;

    return newNode;
}

这个函数只负责创建一个节点

但我们如果要真正操作一个链表我们肯定还需要链表首节点的地址

往后看，我们会发现，这个函数事实上是辅助其他函数实现功能的辅助函数

初始化一个链表

Node* initList(int data)
{
    Node* headNode = createNode(data);

    return headNode;
}

这个函数就是创建一个节点，然后返回首节点

好了，接下来，我们要对初始化好的链表操作了

现在，我们要实现节点最基本的增、删、改、查

增加节点

我们可以先考虑一下要怎么增加节点其实也就是怎么设计函数

我们要做一个只能在末尾增加节点的函数，还是只能在首增加节点的函数? 还是说，我们要做一个可以添加到指定位置的函数?

其实都可以，这里以添加到指定位置为例子

那么我们的函数需要三个形参:分别是链表的头节点、新节点的数据和新节点的位置

而增加节点就需要新节点的next指向下一个节点，同时让上一个节点的next指向新节点

同时我们还要考虑一个问题。如果我们输入的位置比链表长度还要长怎么办? 我们可以设计一个函数获取链表长度，然后再判断位置的值是否合适\

int getListLength(Node* headNode)
{
    int len = 1;
    Node* temp = headNode;//一个临时的工具节点指针，单纯辅助作用

    if (temp == NULL)//防止传入空链表的情况
    {
        return 0;
    }

    while (1)
    {
        temp = temp->next;  //将指针指向下一个节点
        if (temp == NULL)
        {
            return len;
        }
        else
        {
            len++;
        }
    }
}
int addNode(Node* headNode,int data, int index)//将新节点添加到index位置的节点后面。index取值规则和数组一样从0开始。函数返回1表示操作成功
{
    Node* temp = headNode;//一个临时的工具节点指针，单纯辅助作用

    int len = getListLength(headNode);
    if (index >= len || index  < 0)
    {
        return -1;
    }
    else
    {
        for (int i = 0;i < index;i++)
        {
            temp = temp->next;  //偏移到指定位置
        }
    }

    Node* newNode = createNode(data);
    newNode->next = temp->next;
    temp->next = newNode;

    return 0;
}

在传统 C 编程中：

不需要用返回值表示某些计算结果，而只是“做某件事”的函数一般返回 0 表示成功，返回非零值（并且经常是负值）表示失败。
“判断某个条件是否成立”的函数一般返回 1 表示成立，返回 0 表示不成立，因为前面的章节说过，非零值是真，零值是假。这样我们就能像这样写条件了： if (isOk()) 。这其实也就是“用返回值表示计算结果”的一种情况了。

最知名的开源 C 项目 Linux 操作系统内核就遵循了这一设计思路。

我们的 addNode 函数就是“做一件事”的函数，所以成功返回 0，失败返回 -1 。

删除节点

和增加节点是类似的，我们来做一个删除指定位置的节点的函数

我们讨论一下如何删除一个节点

如果要删除一个节点，我们就要让上一个节点的next指向下一个节点够了，对于单向链表就这么简单，然后把要删除的节点free掉就行

如果是双向链表(即节点内除了next还有一个prev指向上一个节点) 那可能会复杂一点:我们在让上一个节点的next指向下一个节点的之后，还要让下一个节点的prev指向上一个节点

同时我们还要考虑一种特殊的情况:如果是删除头节点呢? 我们还要更新一下头节点

Node* delNode(Node* headNode, int index)//操作成功后会返回新的头节点。index取值规则和数组一样从0开始
{
    if (headNode == NULL)//防止传入空链表
    {
        return NULL;
    }
    Node* temp = headNode;
    int len = getListLength(headNode);

    if (index >= len || index < 0)//先判断index是否合理
    {
        return NULL;
    }
    else//之后判断是否为头节点
    {
        //如果是头节点
        if (index == 0)
        {
            headNode = temp->next;
            free(temp);
            return headNode;
        }
        //如果不是头节点
        else
        {
            for (int i = 0;i < index - 1;i++)
            {
                temp = temp->next;
            }
        }
    }

    //现在，temp指向的就是我们要删除的节点的上一个节点
    Node* target = temp->next;//保存要删除的节点

    temp->next = temp->next->next;//修改连接关系
    free(target);

    return headNode;
}

修改节点

这里就比较简单了，我们只需要找到对应的节点，然后修改一下数据就行

href="#__codelineno-5-1">int editNode(Node* headNode, int index, int newdata) pan> // 其实这个 if 可以不需要。headNode == NULL 其实就是链表长度为 0 的情况，它并不特殊。 if (headNode == NULL) { return -1; } Node* temp = headNode; int len = getListLength(headNode); if (index >= len || index < 0) { return -1; } else { for (int i = 0;i < index;i++) { temp = temp->next; } } temp->data = newdata; return 1; }

查找节点

我们做这种函数，其实一般就是为了找到存储某个数据的节点的索引是多少

在 C 语言中，一般使用 size_t 这个类型来表示索引。

size_t 也是一个类型别名，也是用 typedef 定义出来的，定义在 stddef.h 文件中。它是一个无符号整数，通常用来表示长度和索引等。

至于怎么找? 由于链表是链式结构，我们只有知道了一个节点是什么，才能得到下一个节点因此，我们只能遍历链表慢慢找

但是这里又有一个问题。 size_t 作为无符号整数，用它做返回值的话如何表示“未能找到”呢？

因此我们不将返回值定义为 size_t 类型，而是定义为 int 类型，让这个 int 表示函数做事是否成功。

那么如何将我们的 size_t 结果传输到调用者那里呢？用参数吗？但在函数里修改参数的值并不会影响到调用者。

我们可以用指针。我们添加一个类型为 size_t* 的参数，在函数完成计算时，把结果放在这个指针指向的位置。这样的参数可以称为“出参”。

int searchNode(Node* headNode, int target, size_t* out_index)
{
    size_t index = 0;
    Node* temp = headNode;

    while (temp != NULL)
    {
        if (temp->data == target)
        {
            // 将计算结果放在指针指向的位置；返回值为 0，表示成功
            *out_index = index;
            return 0;
        }
        else
        {
            temp = temp->next;
            index++;
        }
    }

    // 返回值为 -1，表示失败
    return -1;
}