在C语言中实现链表时，为什么需要使用指针？

Question

在C语言中使用指针实现链表为什么很重要呢？

比如：

typedef struct item                                     
{
    type data;
    struct item *next;
} Item;

typedef struct list                                          
    Item *head;
} List;

如果我不使用指针，仅使用相同的实现会发生什么？

- Joni

---

由于你使用动态内存分配，需要存储链表中下一个节点的地址。假设如果你使用自己预分配的数组作为内存，则可以直接使用数组中的索引值。 - Grijesh Chauhan

你试过吗？ - Ingo

我认为你的第一个问题应该是“指针是什么？” - Grijesh Chauhan

如果每个“项”都包含另一个“项”，那么它怎么会结束呢？分配一个项目将自动创建另一个项目，然后创建另一个项目，再创建另一个项目... - Joachim Sauer

你是在与其他语言中的列表进行比较吗？如果是这样，请在问题中添加该定义。差异有助于更容易地理解。 - Suvarna Pattayil

Answer 1

那么你最终会得到这样的东西

typedef struct item                                     
{
    type data;
    struct item next;
} Item;

现在C编译器将尝试计算Item有多大。但由于next嵌入在Item中，它最终会得到这样一个方程式：

size-of-Item = size-of-type + size-of-Item

这意味着它是无限的。因此我们有了一个问题。由于这个原因，C需要指针，这样你就可以

size-of-Item = size-of-type + size-of-pointer

这会关闭它。更有趣的是，即使你在Java、Python或Haskell等语言中这样做，实际上你仍然会隐式存储指向（他们称为引用）来打破循环的指针，只不过他们将这个事实隐藏了起来。

- Daniel Gratzer

Answer 2

你实际上不需要使用指针来实现一个暴露链表接口的数据结构，但是你需要使用它们才能提供链表的性能特征。

那么指针的替代品是什么呢？嗯，item需要有一种方式来引用下一个item。由于某些原因，它不能聚合下一个item，其中之一是这将使struct"递归"，从而无法实现：

// does not compile -- an item has an item has an item has an item has...
typedef struct item                                     
{
    type data;
    struct item next;
} Item;

你可以做的是创建一个项目数组，并在其上实现链表：

Item *storage[100];

typedef struct item                                     
{
    type data;
    int next; // points to the index inside storage of the next item
} Item;

看起来这会奏效；你可以有一个函数将项目添加到列表中，另一个函数从列表中删除项目：

void add_after(Item *new, Item *existing);
void remove(Item *existing);

这些函数要么从数组中删除existing（确保更新前一项的next“指针”），从而创建一个空槽，要么找到existing项目并将new插入storage中的空槽（更新next以指向那里）。

问题在于，这会使add_after和remove操作无法在常数时间内实现，因为现在需要搜索数组并在空间不足时重新分配它。

由于常数时间的添加/删除是人们使用链表的主要原因，这使得非指针方法只能用作知识性的练习。对于真正的列表，使用指针意味着您可以在常数时间内执行这些操作。

- Jon

---

对于OP的问题，请参阅：使用数组实现链表 - 优势和劣势 - Grijesh Chauhan

Answer 3

指针用于动态分配内存。

你可以将列表实现为一个简单的数组，但这意味着你分配了一个连续的内存区域，对于一个大的列表来说并不高效。此外，数组更难以扩展（如果达到其最大大小，你必须重新分配它）。

因此，对于大型列表，首选动态分配，在每个元素中可以在任何地方连续或不连续地分配内存，并且可以轻松地扩展它。

此外，不能在struct item中存储另一个struct item，因为结构体尚未定义，无法确定结构体的大小：

这是不可能的：

typedef struct item                                     
{
    type data;
    struct item next;
} Item;

因此，使用指针是因为在编译结构时可以确定指针的大小（在该平台上整数的大小）。

- ionela.voinescu

Answer 4

没有指针，每个列表项都包含另一个列表项(next)，该列表项又包含另一个列表项，依此类推。

你最终会得到一个无限大的数据结构，它将使用无限量的内存，当然这是不可行的。

- sth

Answer 5

你不需要使用指针来创建C语言中的列表。使用指针列表取决于你的应用程序。在编程语言中实现指针概念之前，人们就已经使用了链表。对于一些人来说（使用指针），这有时更容易理解。你也不需要一个带有数据的结构。

一个简单的数组就可以了。你需要：

- 一个整数数组来保存索引（类似指针）。数组内容是 -1（表示指针术语中的nil或NULL），或者是 0 .. N-1，表示：下一个链接元素的数组索引。索引数组的索引表示数据数组中的项目索引。 - 一个用于连接“列表”中任何数据的数组。

这就是你所需要的全部。

使用数组而不是指针列表可能会有

• 优点，如果您的数据量不变（不增长）。在这种情况下，优点是巨大的。如果您知道您将遇到的最大数据量并且可以预先分配数据，则数组实现将比任何指针链接列表快得多。特别是，如果您只插入但不需要删除。
• 缺点，否则。在这种情况下，缺点可能非常大。

请阅读此处。

因此，您的示例看起来像：

type data[N];  // or: type *data = new type [N];
int links[N];  // or:  int *links = new int [N];

这应该是您开始进行简单测试的所有所需内容。

- rubber boots

Answer 6

指针在C语言中的重要性

优点：

1. 执行速度会更快。

2. 指针允许我们访问函数外部的变量。

3. 减少代码的大小。

没有指针：

1. 代码大小会增加。

2. 我们无法有效地维护数据。

3. 在列表中，指针用于指向列表中下一个项。如果您没有声明指针，则无法访问列表中的多个项。

4. 如果您在运行时动态分配一些内存，则确实需要使用指针。

- reegan vijay

Answer 7

有不止一种“列表”。你展示的实现是一个“链表”。没有指针就没有“链接”，所以我们需要看其他类型的列表。

那么，首先，如果从结构定义中删除*会发生什么：它将无法编译。你可以在另一个结构体内包含一个结构体，但如果存在递归，则结构的大小将无限增大，这是不可能的！

用数组作为列表如何：

struct item list[100];

没错，那可以运行，但是现在你的列表大小是固定的。

好的，那我们来动态分配这个列表：

struct item *list = malloc(sizeof(struct item));

然后，每次你添加到列表中时，你都需要这样做：

list = realloc(list, newcount * sizeof(struct item));
list[newitem] = blah;

好的，这样做是可行的，但现在我们经常重新分配内存，这会导致大量的内存复制和低效。

另一方面，如果列表更新得非常不频繁，那么这种方法更节省空间，这可能是一个好事情。

使用数组的另一个缺点是像push、pop、sort、reverse等操作变得更加昂贵；它们都意味着多次内存复制。

还有其他类型的“列表”，但它们都涉及指针，所以我认为我们可以在这里忽略它们。

- ams

---

我不是那个给你点踩的人，但我觉得可能是因为你把数组说成了列表，这就否定了链表的优势（例如，在中间插入元素很便宜）。由于这是一个初学者问题，我认为很重要的一点是要清楚地区分链表和数组，就像Jon的回答所做的那样。 - Timothy Jones

是的，我相信这也是我要表达的观点。显然，我没有表达清楚 :( - ams