C/C++ 中的链表入门

引言

数组的问题？

在 C/C++ 等低级语言中，如果你想存储一组相关的数据，本能的选择就是使用数组。数组创建时，编译器会保留一块内存来存储数据。例如，如果我们有 3000 个 `float` 类型的数据，编译器会计算 `float` 的大小（32 位系统上为 4 字节），并保留足够存储 3000 个该大小数据的内存，每个元素会紧挨着前一个元素存储在内存中。编译器只记录数据块起始的内存地址、元素的类型以及元素的数量。

在检索数据时，编译器会使用数据块的起始地址，并根据每个元素的大小和存储方式，数学上计算出所需元素的相对位置。可以使用一个简单的公式：

Element Address = Array Start Address + (Element Index * Size Of Element)

例如，要获取一个 `float` 数组中第 100 个元素，编译器会获取数组起始地址的指针，然后将地址移动 `100 *` 一个 `float` 元素的大小。我们可以通过下面的表格来可视化这个过程，该表格表示了一个包含五个 `float` 的数组在内存中的布局。编译器已从地址 `245` 开始为该数组保留了内存。

这种存储数组的方式符合 C\C++ 的低级方法论，即保持效率和简洁性。然而，它有一个主要的缺点，即原生 C\C++ 数组无法调整大小。这意味着无法动态地添加或删除元素。

很多情况下，你需要一种数据结构，与 C\C++ 原生数组不同，它可以动态调整大小。例如，飞机的座位预订系统可能需要根据航班型号调整可用座位列表。因此，我们需要寻找其他可以做到这一点的数**据结构，链表就是其中一种。**

为什么 C/C++ 数组无法调整大小？ 编译器寻址数组元素所使用的简单逻辑不允许除了假定所有元素都连续存储之外的其他方式。想象一下，如何在不破坏这种逻辑的情况下向数组开头添加一个新元素。你必须将后续的每个元素向下移动一个位置，前提是内存块的末尾有足够的可用空间来容纳这个扩展。如果没有，你就必须在新内存位置创建一个新数组，复制所有现有数据，并将新元素放在开头。如果 C\C++ 内置了像这样的数组调整大小操作，它们的使用可能会导致程序涉及大量耗时且不可接受的内存操作。

链表数据结构

链表是一种数据结构，它为这个问题提供了一个简单但非常优雅的解决方案。C\C++ 中没有原生的“链表”数据类型，所以你需要自己编程实现（尽管 C++ 标准库中有一个，但稍后会详细介绍）。

链表由节点组成，节点包含你列表中的数据。每个链表必须有一个头节点，它指向第一个数据节点；每个数据节点包含该列表项的数据以及指向列表中下一个节点的引用。当一个节点引用一个终止符时，就表示列表的结束。

关于这一点，关键要记住的是，每个节点不必像前一个节点那样连续存储在内存中，因为链表的结构包含了指向下一个元素位置的引用。这意味着我们可以动态地添加和删除链表中的元素，所涉及的内存操作比尝试在数组上执行相同操作要少得多。

现在我们已经能够可视化链表数据结构的模样，就可以考虑实现。最基本的链表实现至少会涉及以下操作：

遍历链表：你从头节点开始获取第一个节点。完成第一个节点后，读取指向下一个节点的引用，然后移动到该节点。这个过程可以无限重复，直到找到终止符，通常实现为一个循环。

添加元素：在特定位置添加元素需要一些考虑，因为你需要确保不破坏链表的连续性。如果你插入一个新节点，你需要记录前一个节点中包含的“下一个节点”引用，并将其作为新节点中的“下一个节点”引用。然后，你需要覆盖前一个节点的“下一个节点”引用，使其指向你的新节点。

删除元素：当你删除一个节点时，你需要记录要删除节点中包含的“下一个节点”引用，并用它来覆盖前一个节点的“下一个节点”引用。这同样可以确保节点之间的链接不会中断。

在 C\C++ 中实现（入门）

C 语言有许多特性非常适合实现链表。在这里，我们将研究可以使用哪些特性来表示一个简单的链表。示例代码摘自：

数据节点

数据节点可以通过 `struct` 来定义。在该 `struct` 中，我们需要存储节点的数据以及一个指向同类型另一个 `struct` 的指针。

struct data_node
{
  data_node *NextNode; // Pointer to next node
  int MyValue; // node data.
};

头节点

头节点可以简单地实现为指向我们之前定义的 `data_node` `struct` 的指针。

struct data_node *RootNode;

内存分配注意事项

在 C 中添加和删除节点时，你需要向编译器请求一个节点大小的内存区域，或者释放之前由节点使用的内存。我们可以使用 `sizeof()`、`malloc()`、`free()` 函数来完成。

CurrentNode->NextNode = malloc(sizeof(struct data_node)); 
// allocate memory for a new node.

有了这些基础知识，我们就可以着手在原生 C 代码中实现一个功能齐全的链表，包括遍历链表、添加节点和删除节点的函数以及任何其他所需功能。完整的实现超出了本入门教程的范围，但你可以在网上找到许多示例。

C++ 标准库：C++ 的标准库提供了用于程序开发的各种类和函数。其中包括许多你可以使用的数据结构。单向链表实现为一个名为 `forward_list` 的容器类模板，双向链表则实现为 `list`。开发者通常使用这些模板作为链表的基础，而不是从头开始编写完整的实现，以节省时间。