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

Question

这个问题可能过于宽泛,或者存在意见偏见,但我知道这个网站充满了经验丰富的程序员,我认为这可能会鼓励一个好的讨论.

我在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];

但是,这种方法存在某些困难,例如,有时我需要从列表中删除一个元素,然后它会留下一个空元素,迫使我用一个索引重写所有其他元素.

是否有任何干净,优雅的方式来实现类似于链表的功能,而不使用它们？

Answer 1

您可以在静态数组上使用链接列表.唯一的区别是,不是指向动态分配的内存块的指针,而是使用指向数组内部元素的指针.如果您愿意,可以只使用数组索引而不是指针.当然,实现会有一些不同之处: - 在添加或删除元素时,您不必(un)分配内存 - 相反,您必须自己管理空闲插槽,使用其他结构,如队列甚至另一个空元素列表