为什么我们需要链接列表的C实现中的指针？

Question

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

例如:

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

typedef struct list                                          
    Item *head;
} List;

如果Ill在没有指针的情况下使用相同的实现会发生什么？

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等语言中这样做,你也会隐含地存储一个指针(他们说引用)来打破循环.他们只是向你隐瞒事实.

Answer 2

实际上,您不需要使用指针来实现公开链接列表的接口的数据结构,但是您确实需要它们以提供链接列表的性能特征.

指针的替代品是什么？那么,item需要有一些方法来参考下一个项目.由于各种原因,它无法聚合下一个项目,其中一个原因是这会使结构"递归",因此无法实现:

// 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操作无法在恒定时间内实现,因为您现在需要搜索数组并在空间不足时重新分配它.

由于常量时间添加/删除是人们使用链表的原因,这使得非指针方法仅用作智力练习.对于真实列表,使用指针意味着您可以在恒定时间内执行这些操作.

Answer 3

如果没有指针，每个列表项都包含另一个列表项 ( next)，该列表项又包含另一个列表项。其中又包含另一个列表项。等等。

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