在C语言中的链表中，为什么节点也是指针？

Question

当我们尝试实现链表时，为什么要创建节点指针而不是节点结构的原因我无法理解：

typedef struct node {
    int val;
    struct node * next;
} node_t;

并且

node_t * head = NULL;
head = malloc(sizeof(node_t));
if (head == NULL) {
    return 1;
}

head->val = 1;
head->next = NULL;

在这里，为什么我们要将像head这样的节点声明为结构体指针而不是直接结构体呢？

- Huzo

---

如果“head”已经是一个保存节点所有数据的结构体，那么如何表示一个空链表？ - Gerhardh

“the rest as structure” 是什么意思？node_t 应该包含一个 node_t next 字段吗？这不会形成链接，而是嵌套的，导致一个无限大小的递归增长结构。 - Gerhardh

如果一个 node_t 类型的变量包含另一个 node_t 类型的变量作为成员，那么这个被包含的 node_t 变量也会有一个 node_t 类型的变量作为成员。你有没有尝试过实现这个功能？但是实际上它是行不通的。 - Cubic

我看到这个问题感觉有些似曾相识...[为什么链表使用指针而不是将节点存储在节点内部？]（https://dev59.com/E10b5IYBdhLWcg3wJ-bb） - emlai

仅就标题中所写的文本作出回应，节点并不是指针。它们是包含负载（有趣的东西）和指针的结构体。而指针就是“链接”，将列表连接在一起，因此使列表“链接”，但通常您关心的是负载。指针只对实现列表代码的人（当然，这在课堂上就是你）有兴趣，但不适用于抽象概念“这里是一组数据列表”的用户。 - dmckee --- ex-moderator kitten

Answer 1

将 head 作为指针可以实现像空列表（head == NULL）或通过将 head 指针移动到列表中的另一个元素（例如第二个元素）来删除列表前面的元素的简单方法。如果将 head 作为结构体，则这些操作将不可能进行，或者至少要实现得低效得多。

- Mithrandir

---

我明白了，但我们能否将其他节点用作结构体呢？ - Huzo

@Huzo 链表中的每个元素都是一个结构，但是该列表应该根据需要增长（或缩小）。只有使用指针才能让您的列表在运行时增长或缩小。 - Mithrandir

Answer 2

主要原因是C语言不允许这样做-结构体类型不能包含自身的实例。这有两个原因：

1. 结构体类型在遇到结束符号}之前是不完整的，你不能创建一个不完整类型的实例；

2. 如果结构体类型可以包含自身的实例，那么该实例将会是无限大的（struct foo 包含一个 struct foo 的实例，它又包含一个 struct foo 的实例，以此类推，无穷无尽）。

然而，你可以创建一个指向不完整类型的指针（因为指针的大小不取决于指向的类型的大小）。所以，如果你想让一个结构体类型包含一个引用同一类型的另一个实例的成员，必须通过指针来完成。

- John Bode

---

实际上，如果您使用联合（或在类型转换方面有些自由），则可以拥有许多不同类型的列表。例如，在X中的事件。 - jamesqf

问题并不是在问为什么节点结构包含指向下一个节点的指针。而是在问为什么整个链表使用指向头部的指针来操作，而不是直接使用头部本身。 - Vaelus

@Vaelus：实际上它在询问两个问题。为什么我们在“struct”类型中使用指针，以及为什么我们使用指针来跟踪列表。 - John Bode

Answer 3

为什么我们将诸如头节点之类的节点声明为结构体指针而不是直接的结构体呢？将head声明为指针允许我们拥有一个空链表，即当head为NULL时。

- Andriy Berestovskyy

---

哦，所以优势在于能够释放空间和操纵内存？ - Huzo

那是唯一的优势吗？ - Huzo

@Huzo 空列表的优点在于知道列表为空 ;) 关于动态内存分配，即 malloc() 我们按需分配内存，而不是一次性分配所有节点。如果您关心内存，这是一个优点，但从性能上来看，它比简单的节点数组慢。所以这取决于... - Andriy Berestovskyy

Answer 4

因为这就是重点：一系列像链条一样链接的节点。你可以轻松地分离和重新连接节点，因为这只需要更改指针值。如果您想要的话，这在数组中是不可能的。此外，一个类型不可能包含其自身的实例。所以一个node包含一个node，它又包含一个node，依此类推...那怎么可能行得通呢？

- Lightness Races in Orbit

---

问题并不是在问为什么节点结构体有一个指向下一个节点的指针。 - Vaelus

@Vaelus：对我来说，似乎是这样，而且显然对这个页面上的每个人都是这样。 - Lightness Races in Orbit

问题在于为什么使用指向头部的指针来管理列表，而不是直接使用头节点。这就是被接受的答案。 - Vaelus

@Vaelus：我不同意。标题和大部分内容都表明OP的意思是“所有”节点，而不仅仅是头节点。OP甚至在接受的答案下面的评论中自己也这样说了；所以接受的答案实际上并没有回答问题。 - Lightness Races in Orbit

我认为这个问题的措辞不太好，但考虑到被接受的答案仅讨论了为什么使用指针来管理列表，以及OP仅对此类答案做出了回应，我认为我的解释是OP的意思。 - Vaelus

@Vaelus：那么我们就不得不同意不同意见了。 - Lightness Races in Orbit

Answer 5

正如其他人所说，通过使用指针，我们可以方便地使用NULL指针来表示空列表或列表的末尾。

当然，我们可以修改节点以具有标志，指示它是“列表的末尾”（EOL）。然而，另一个重要原因是，它使列表能够轻松增长（最多可用内存量）或动态缩小，而无需重新分配内存来容纳整个列表并在每次增长或缩小时复制它。它还使插入或删除项目变得更加容易。

- Marker

---

你的方法中，节点之间的链接是如何工作的？你是指一个结构体数组吗？ - Gerhardh

是的，如果您不使用指针，您需要一个结构体数组。它可以是固定容量的，或者每次超出其容量时，您需要重新分配一个更大的数组，将旧数组复制到其中，然后删除旧数组。插入和删除也涉及大量复制或以某种方式标记项目为空。在我开发嵌入式系统时，有时会使用固定列表，特别是在简单处理器上，我知道最大列表大小永远不会改变。 - Marker

Answer 6

如果节点之间没有实际链接，那么它就不是一个“链接”列表。它可能仍然是某种类型的列表，但它不会是链接的。

与互联网上的“链接”或超链接相比较。它们也是指针，因为几乎没有站点存储链接站点的实际内容。

- mathreadler