Nested linked lists in C

Question

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);

Based on answers by @bolov and @sps (once again, thanks to both of them), here is the minimum working example:

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

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

typedef struct MenuItem_t 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);

The difference between this corrected program and the original (non)working program, is that the children array is defined as an array of pointers to variables of the type MenuItem_t instead of the array of variables of the same type. The other difference is that a nested list (inside the structure) should also contain the keyword struct as @bolov explained.

follow any tutorial on C linked lists. And you will see how to define your node structure. — bolov
– bolov, Commented Aug 8, 2016 at 14:40
GCC (v4.9.3-1) is complaining to nested structures Can you include a quote of these 'complaints'? Whenever you post a question that involves an error/warning message, you should include it, so people don't have to guess what the problem is. — underscore_d
– underscore_d, Commented Aug 8, 2016 at 15:01
Thank you for your suggestion. I'll keep that in mind for future questions! I won't post errors now, as bolov and sps have answered my question. I'll post a complete solution in my first post once I test everything. — Marko Gulin
– Marko Gulin, Commented Aug 8, 2016 at 15:58

bolov · Accepted Answer · 2016-08-09 08:37:44Z

1

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) + padding. 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.

edited Aug 9, 2016 at 8:37

answered Aug 8, 2016 at 14:45

bolov

76.8k17 gold badges156 silver badges248 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Matthew Over a year ago

I agree with you on the dislike of that form... It's really gross

Marko Gulin Over a year ago

I fixed it in a way that I removed a typedef and added the struct keyword before all MenuItem_t. Now the GCC complains to array struct MenuItem_t children[10] with the following error: array type has incomplete element type.

bolov Over a year ago

@Marko you can't have that. Think about it: what size would MenuItem_t be?

Marko Gulin Over a year ago

What I actually want is to store an array of pointers to other (predefined number of) MenuItem_t variables. Can this be done? As for the "typedef form", I don't have that experience to like/dislike any form, I'm just using a form that programmers-that-write-header-files-for-microcontrollers use :)

sps · Accepted Answer · 2016-08-09 08:17:55Z

1

First of all, you cannot do,

typedef struct {
    SomeName_t some_var;
} SomeName_t;

You need to do,

typedef struct somename {
    struct somename some_var;
} SomeName_t;

Also, a struct cannot have a member which is an array of structure itself. However, a struct can have a member which is an array of pointer to the same structure.

struct foo {
    struct foo foo_arr[10];      /* Will give error */
    struct foo *foo_ptr_arr[10]; /* Legal */
};

However, I dont see a reason that your children member should be an array of struct anyways. Because, as can be seen in menu.c, you are doing

    parent->children[parent->size] = child;

where the type of child is MenuItem_t *. So I think you basically wanted MenuItem_t.children to be an array of MenuItem_t *, and not an array of MenuItem_t.

So making this change should resolve your issue:

menu.h

typedef struct menuitem {
    unsigned char size;
    /* MenuItem_t children[10]; */  /* Not possible */
    struct menuitem *children[10];  /* This is what you want to do */
    struct menutem *parent;
} MenuItem_t;

edited Aug 9, 2016 at 8:17

answered Aug 8, 2016 at 15:31

sps

2,7302 gold badges24 silver badges42 bronze badges

1 Comment

Marko Gulin Over a year ago

Thank you for your answer. I've edited my first post to include these solutions.

Collectives™ on Stack Overflow

Nested linked lists in C

2 Answers 2

4 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related