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.
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;
};
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.
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