Multi Level Data Structure (Linked list)

Question

I am looking to implement a multi level data structure which looks like as shown below.

object {
   object A {
          child {
               myChild;
          };
          child 1 {
               mychild;
          };
   };
   object B {
         child {
         };
   };
};

My approach is to implement this using a linked list as shown below.

typedef struct node_s {
    struct node_s *next;
    struct node_s *first_child;
    struct node_s *parent;
    char *text;
} node_t;

Converting above list to STAILQ (sys/queue.h linux) will be

typedef struct node_s {
    char *text;
    ....;
} node_t;

typedef struct list_s {
    STAILQ_ENTRY(list_s) link;
    node_t *first_child;
    node_t *parent;
    node_t *next;
    int level;
} list_t;

typedef STAILQ_HEAD(list_head_s, list_s) list_head_t;

Please suggest if there is any other better way of implementing this other than a linked list or using linked list?

your list_s is a tree. Which part are you asking about? first_child? — Hogan, May 27 '13 at 11:22
I want to implement entire list_s as linked list can you suggest if there is any other better way of addressing the above problem? — Bose, May 27 '13 at 11:57

score 2 · Accepted Answer · edited May 23 '17 at 11:58

The structure that you're representing is more of a tree than a linked list - it's a collection of nodes where each node may have zero or more children, and every node except the root will have exactly one parent.

The representation scheme that you are using is typically referred to as the left-child, right-sibling representation of a tree. Rather than having each node store an explicit list of its children, it stores a pointer to one of its children, and the children are then linked together through a linked list. As mentioned in the linked question and answer, this has some advantages when memory is scarce, but it increases the amount of time required to search for a particular child of a given node.

There are many other ways that you could represent this structure, and it's really up to you do determine how to do it. One option would be to store the children in some sort of associative array structure keyed by the name of the child (for example, a hash table or balanced binary search tree). This would make it much faster to find a specific child given its name, though it does increase the memory usage a bit. Another option would be to use an explicit array of all the children rather than threading a linked list through the children of each node, which requires more allocations but makes it easier to append children to a given node.

Hope this helps!

Multi Level Data Structure (Linked list)

1 Answers1