Marko Marko - 3 months ago 13
C Question

Nested linked lists in C

I'm trying to implement a nested linked list in C, that will be used for a hierarchical menu. However, the GCC (v4.9.3-1) is complaining to nested structures, and I have no idea how to fix this. Here is the minimum (non)working example.

Is this nesting even possible in C?

main.c

#include "menu.h"

int main(void) {
Init_Menu();
return 0;
}


menu.c

#include "menu.h"

MenuItem_t LVL_0_MainMenu = {
.size = 0,
};

MenuItem_t LVL_1_Measurements = {
.size = 0,
};

void Init_Menu(void) {
Menu_Add_Child(&LVL_0_MainMenu, &LVL_1_Measurements);
}

void Menu_Add_Child(MenuItem_t *parent, MenuItem_t *child) {
parent->children[parent->size] = child;
child->parent = parent;
parent->size++;
}


menu.h

typedef struct {
unsigned char size;
MenuItem_t children[10];
MenuItem_t *parent;
} MenuItem_t;

extern MenuItem_t LVL_0_MainMenu;
extern MenuItem_t LVL_1_Measurements;

void Init_Menu(void);
void Menu_Add_Child(MenuItem_t *parent, MenuItem_t *child);

Answer

You need to use struct for the type used inside itself, even if you typedef it later on.

E.g. this won't work:

struct X_ {
  X* next;
};

typedef struct X_ X;

But this will

struct X_ {
  struct X_* next;
};

As a side note, I really don't like this form:

typedef struct {
} X;

I use:

struct X {
};
typedef struct X X;

But maybe this is just me being more fond of C++.

If you want to use that form, it's the same: you need to add struct and it works:

typedef struct {
  struct X2* next;
} X2;

regarding:

struct X {
   struct X arr[10];
};

You can't have that! The array is just in our way to understand why. So let's simplify:

struct X {
   int a;
   struct X var;
};

This can't be. What size would X be? sizeof(X) = sizeof(int) + sizeof(X). Do you see the problem? All you can do is have a pointer to X, but not an object X inside X.

Returning to your array. You need dynamic arrays:

struct X {
   struct X* arr;
   int arr_size;
};

It gets more complicated as you need to manage the memory (malloc/free fun), but you can't avoid it.

Comments