What is the data model required for such data?

Question

Using python syntax, we have deep list like,

Example 1 - list = [1, [2, 3], 4]

Example 2 - list = [[1, [1, 1]], 1, [1, 1]]

where each subset MUST be of class list or int at runtime.

Using C language, What is the data model required to maintain such data?

Note: Dimensions are not fixed, as per the example

Answer 1

Use a forward declaration of a structure for the elements.

// declare existence of a structure type to be used for array elements.
struct some_type_S;

// The list type is a count and pointer to an array of `struct some_type_S`
// Alternative: use a variable length array for `element`
typedef struct list_S {
  size_t num_elements;
  struct some_type_S *element;
  // Alternative: use C99 and a variable length array for `element`
  // struct some_type_S element[];
} list_T;

// Now define `struct some_type_S` as
// a flag (is_int) and a union of an `int` and a pointer to a list
typedef struct some_type_S {
  _Bool is_int;
  union {
    int i;
    list_T *list;
  } u;
} some_type_T;

Happy C coding.

Answer 2

The data structure you want appears to be a tree shape. Where each leaf is either an int, or it is a list of variable size. There is no current implementation of this I know of, so you would have to implement your own tree structure. You could implement this using a dynamic array like

struct Tree{
    struct Tree* list;
    //if leafOrBranch is true, consider this a branch and branchsize is the size of list, if it is false, consider this a leaf and branchsize is the content
    int branchSize;
    bool leafOrBranch;
}

This has the downside of needing the reallocate the memory in list when increasing the size of it, so an implementation could be done using a linked list or binary treee or something to speed it up.

Answer 3

To have such a structure in C you have much work to do (or link code of others). And SO is no code-writing service. However, I'll give you some pointers how to do that:

1. C does not support dynamic length arrays (lists) out of the box. (So-called variable length arrays are no help in your situation.) But you will find implementations for that in the web. (Usually list are linked lists of fixed-size buffers.)

2. C neither supports dynamic typing nor generic typing. To write generic code as such an array implementation has to have, usually the array does not store the payload itself, but a pointer to it. The pointer can be typed void*, what basically means "pointer to something". Therefore you can store a pointer to an integer number or to another list into it.

3. Or. You want to store integer numbers and lists of integer numbers side-by-side in the same list. This is unusual for C. Esp. C programs does not have meta information about its objects. There is no way to ask a void *, what type it is pointing to. Therefore you need a structure that stores, whether it holds a number or a list and then a component to hold a number (unused if it is a list) and a pointer to a list (unused if it is a number.) (You can optimize this a bit with castings or unions, but this is the first approach.)

So, putting all things together:

You need code, that manages a list. You will find that in the web.

You define your own structure holding a number or a pointer to another list and the type of data it stores.

Allocation of every list has to be done by yourself.

A long way to go. We will see you soon with additional Qs. ;-)

Answer 4

Alternatively, if you prefer a linked structure:

// A cell is a basic variant type whose value can be either
//  * An integer, or
//  * A pair of cells
struct cell_t;
struct pair_t;

// Enum of cell type, currently INT or PAIR
typedef enum { INT, PAIR } cell_type;

// Definition of type cell and pair, which are pointers to the respective structs
typedef struct cell_t* cell;
typedef struct pair_t* pair;

// Definition of pair_t: two pointers to cell (first and second)
// For a list structure, the type of second should always be PAIR.
struct pair_t {
    cell first;
    cell second;
};

// Definition of cell_t: type + union value
struct cell_t {
    cell_type type;
    union {
        int  i;
        pair p;
    } value;
};

// Constructors
//////////////////////////////////////////////////////////////////////////////////
// Returns an integer cell
cell Int(int i);
// Returns a pair cell
cell Pair(cell a, cell b);
// Returns a empty pair, type: PAIR, value.p==NULL
cell Nil();

To understand how this can represent the "deep" lists, have a read of this Wikipedia entry list.

Now we can create the example lists:

// Empty list
cell empty = Nil();

// [2, 3]
cell sublist23 = Pair(Int(2),
                    Pair(Int(3), empty));

cell sublist11 = Pair(Int(1), Pair(Int(1), empty));
cell sublist1_11 = Pair(Int(1), sublist11);

// [1, [2, 3], 4]
cell list1 = Pair(Int(1), 
                  Pair(sublist23, 
                       Pair(Int(4), empty)));
cell list2 = Pair(sublist1_11, sublist1_11);