c - 没有自引用结构的链表

Question

我正在学习数据结构，在做链表的时候，我在想除了 C 中的自引用结构之外，是否还有另一种类型的声明来实现链表。

这是我第一次需要在 C 中使用结构，每个人都只使用自引用结构来实现。我想知道是否有任何其他可能的方式来实现没有自引用结构的链表。

标签： cdata-structures

Answer 1

我在想除了 C 中的自引用结构之外，是否还有另一种类型的声明来实现链表。

不，链表只能通过使用指向它们自己类型的显式或隐式指针来实现。

使用指针屏蔽这种自引用void*是可能的，但它只会使代码复杂化，使自引用隐含并且使代码更难阅读。

数组：

当然，您可以使用无序数组并通过看起来像链表的内部索引方案将其“排序” - 但它仍然是一个数组，并且它不会具有与经典链表相同的行为。

例如，基于数组的链表可能会绑定到预先选择的元素数量（在编译期间选择），当列表未满时会导致更高的内存消耗，并且无法在某个点之后添加元素。

另一方面，如果您的基于数组的链表是动态的，则项目复制期间realloc可能会引入性能成本（例如，使 O(1) 操作以 O(n) 执行）。

另一件需要考虑的事情是，基于动态数组的链表将导致每次数组更改其地址时指向数据的指针都无效（realloc）。