在C链表中为什么节点也是指针？ [重复]

This question already has an answer here:

这个问题在这里已有答案:

Why do linked lists use pointers instead of storing nodes inside of nodes 10 answers

为什么链表使用指针而不是在节点10的答案中存储节点

I could not grasp the reason we create pointers of nodes instead of node structures when we try to implement linked lists as here:

当我们尝试实现链接列表时,我无法理解我们创建节点指针而不是节点结构的原因:

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

and

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

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

here, why do we declare nodes such as head as pointers of structures instead of direct structures>

在这里,为什么我们将诸如head之类的节点声明为结构的指针而不是直接结构>

6 个解决方案

#1

Having head as a pointer allows for things like empty lists (head == NULL) or a simple way to delete elements at the front of the list, by moving the head pointer to another (e.g. second) element in the list. Having head as a structure, these operations would be impossible or at least much less efficient to implement.

通过将头指针移动到列表中的另一个(例如第二个)元素,将头作为指针允许诸如空列表(head == NULL)之类的东西或者删除列表前面的元素的简单方法。将头部作为结构,这些操作将是不可能的,或者至少实现效率低得多。

#2

The primary reason is that the C language simply won't allow it - a struct type cannot contain an instance of itself. There are two reasons for this:

主要原因是C语言根本不允许它 - 结构类型不能包含它自己的实例。有两个原因:

The struct type is not complete until the closing }, and you cannot create an instance of an incomplete type;

结构类型直到关闭}才完成,并且您无法创建不完整类型的实例;
If a struct type could contain an instance of itself, then the instance would be infinitely large (struct foo contains an instance of struct foo, which contains an instance of struct foo, which contains an instance of struct foo, ad infinitum).

如果结构类型可以包含自身的实例,那么实例将是无限大的(struct foo包含struct foo的实例,其包含struct foo的实例,其包含struct foo的实例,ad infinitum)。

You can, however, create pointers to incomplete types (since the size of the pointer doesn't depend on the size of the pointed-to type). So if you want a struct type to contain a member that refers to another instance of the same type, it must be done through a pointer.

但是,您可以创建指向不完整类型的指针(因为指针的大小不依赖于指向类型的大小)。因此,如果您希望结构类型包含引用同一类型的另一个实例的成员,则必须通过指针完成。

#3

why do we declare nodes such as head as pointers of structures instead of direct structures

为什么我们将诸如head之类的节点声明为结构的指针而不是直接结构

Declaring head as a pointer allows us to have an empty list, i.e. when head is NULL

将head声明为指针允许我们有一个空列表,即当head为NULL时

#4

Because that's the whole point: a collection of nodes, that are linked like a chain. You can detach and re-attach nodes with ease and poise, because to do so you need only change pointer values. This would be impossible if your type were more like an array. If you want that, use an array.

因为这就是重点:节点的集合,像链一样链接。您可以轻松,轻松地分离和重新连接节点,因为这样做只需要更改指针值。如果你的类型更像是一个数组,这将是不可能的。如果需要,请使用数组。

Besides which, it is impossible for a type to contain an instance of itself. So a node contains a node, which contains a node, which contains a node, which contains a node, and so forth… how can that work?

除此之外,类型不可能包含自身的实例。因此,一个节点包含一个节点,该节点包含一个节点,该节点包含一个节点,该节点包含一个节点,等等......如何才能工作?

#5

As someone else has already said, by using pointers we have a convenient way of indicating an empty list or the end of the list by using a NULL pointer.

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

We could of course modify our nodes to have a flag indicating that it is "the end of the list" (EOL). However, another important reason it that is give the list the ability to easily grow (up to the amount amount of available memory) or shrink dynamically without having to reallocate memory to hold the entire list and copy it every time that it grows or shrinks. It also makes it easier to insert or remove an item.

我们当然可以修改我们的节点,使其有一个标志,表明它是“列表的末尾”(EOL)。然而,另一个重要原因是它使列表能够轻松增长(达到可用内存量)或动态缩小,而无需重新分配内存来保存整个列表并在每次增长或缩小时复制它。它还使插入或移除项目更容易。

#6

It would not be a "linked" list if the nodes are not actually linked to each other. It could still be a list of some sort, but it would not be linked.

如果节点实际上没有彼此链接,那么它将不是“链接”列表。它仍然可以是某种列表,但它不会被链接。

Compare to the word "link" or hyperlink on the internet. They are also pointers, because almost no site store actual contents of the linked sites.

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

#1

#2