什么是 C 中链表的忠实替代品？

What is a faithful alternative to a linked list in C?

这个问题可能太宽泛，或者观点有偏见，但我知道这个网站上有很多经验丰富的程序员，我认为它可能会鼓励进行很好的讨论。

我正在用 C 实现一个嵌入式应用程序，我在其中使用 链表 ，包含结构：

struct my
{
    uint16_t x;
    uint16_t y;

    char *text;

    struct my *next;
    struct my *prev;

};

它总体上运行良好，但在项目中，我现在正在转向 MISRA-C 编程指南。 MISRA 禁止使用任何动态数据结构，因为它可能会在内存有限的嵌入式系统中导致未指定的行为。

我首先想到的当然是经典的静态数组结构，具有固定大小。这个结构的实例永远不会超过 30 个，而且我们仍然只使用了不到 5% 的可用内存，所以即使没有使用所有这些内存，也不会影响我们的程序性能。像这样：

extern struct my arr[30];

然而，这种方法也有一定的困难，例如，有时我需要从列表中删除一个元素，然后它会留下一个空元素，迫使我通过一个索引重写所有其他元素。

有没有什么干净、优雅的方法可以在不使用链表的情况下实现类似于链表的功能？

您可以在静态数组上使用链表。唯一的区别是，您使用的不是指向动态分配的内存块的指针，而是指向数组内元素的指针。如果您愿意，可以只使用数组索引而不是指针。 当然，实现会有一些不同： - 添加或删除元素时不必（取消）分配内存 - 相反，您必须自己管理空闲槽，使用另一种结构，例如队列甚至另一个空元素列表

您可以使用数组索引代替指针。然后，您可以构建链接列表并使用索引值来访问下一个或上一个小部件。

您可以使用另一个 bool 数组来标记使用了哪些条目。

有很多现有的 API 提供这种在编译时为最大数量的实体保留内存的功能，并提供分配和释放它们的函数。有关示例，请参阅 Contiki memb API and implementation。

有很多方法可以实现这一点，但这里有一个：您可以创建一个 struct widget 数组 + 一个布尔值数组来标记它们是否空闲。然后你可以用找到第一个 struct widget 可用的函数替换你的 malloc。这类似于各种内核中的 slab 分配器。

最好使用静态数组方法，而不是指针，您可以访问需要访问的元素的索引。

虽然您会遇到一些常见问题，例如；

  • 数组固定长度（最大限制需自行决定）
  • 使用内存的数组不会被用于其他用途。
  • 它和指针有同样的问题。

优点是；

  • 知道位置后更简单/更快，
  • 问题检测会很容易，因为内存分配会很方便。
  • 列表中的条目更有可能（在内存中）彼此更接近（与 malloc() 不同，在 malloc() 中，您的条目分散在您分配的所有其他内容中），这可以提高性能（缓存位置）。