什么是C中链表的忠实替代品? [英] What is a faithful alternative to a linked list in C?

问题描述

这个问题可能太宽泛或偏见，但我知道这个站点充满了经验丰富的程序员，我认为这可能会鼓励进行很好的讨论.

This question might be too broad, or opinion-biased, but I know this site to be full of experienced programmers, and I think it might encourage a good discussion.

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

I am implementing an embedded application in C, in which I use a linked list, containing structures:

struct my
{
    uint16_t x;
    uint16_t y;

    char *text;

    struct my *next;
    struct my *prev;

};

总体上来说效果很好，但是现在在该项目中，我正在朝着MISRA-C编程准则发展. MISRA禁止使用任何动态数据结构，因为它可能会在内存有限的嵌入式系统中引起未指定的行为.

It worked fine in general, however in the project right now I'm shifting towards the MISRA-C programming guidelines. MISRA precludes the use of any dynamic data structures, as it might cause unspecified behavior in an embedded system with limited memory.

首先想到的当然是具有固定大小的经典静态数组结构.此结构的实例永远不能超过30个，并且我们仍然仅使用少于可用内存的5％，因此即使未使用所有此内存，也不会影响我们的程序性能.像这样:

What first came to my mind, is of course, a classical static array of structures, with a fixed size. There can never be more than 30 instances of this struct, and we are still only using less than 5% of our available memory, so even if not all of this memory is used, it will not affect our program performance. Like this:

extern struct my arr[30];

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

There are, however, certain difficulties in this approach, for example, sometimes I need to remove an element from the list, and then it would leave an empty element, forcing me to rewrite all further elements by one index.

是否有任何干净，优雅的方法无需使用链接列表即可实现类似于链表的功能?

Is there any clean, elegant way, to achieve a functionality similar to a linked list, without using them?

推荐答案

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

You can use a linked list over a static array. The only difference is that instead of pointer to a dynamically allocated chunck of memory, you use a pointer to an elementet inside the array. If you prefer, you can use just the array index instead of a pointer. Of course, the implementation would have some differences: - You don't have to (un)alloc memory when adding or removing elements - Instead, you'll have to manage free slots by yourself, using another structure, like a queue or even another list of empty elements

这篇关于什么是C中链表的忠实替代品?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！