How are n-ary trees implemented when you don't know how many children a parent might have?

c, filesystems, tree

Solution

You can simply use a linked list of children.

Pardon my ASCII graphics:

+------+
|parent|
+------+
   |
   |
   \    +-----------+     +----------+       +----------+
    --->|first child|---->|next child|--...->|last child|-->NULL
        +-----------+     +----------+       +----------+

This makes it slighly tricker to walk the children, since to get the n:th child you need to visit the n-1 preceding children, but I think it's a viable approach that is used.

Problem

This is something I've been struggling with theoretically, but haven't found any good answers online. I've written programs with binary trees before, which were easy: each node had two links. But now I'm planning out a filesystem based on trees for a project, and I'm not sure how to proceed. Here's the trouble: I want a tree that has pointers to files for leaves and subdirectories for internal nodes (I think this is how Unix does it?). But if a user wants to create a new file or directory, then the number of links in the parent node must be increased. How can I account for this when I design my struct? I'm not sure what my options are besides hardcoding, say, 10 links and restricting directory members to that. Any pointers? (Hah, get it?) If not, does anybody know of any good resources where I could learn more about this? Like I said, so far my internet searches have been fruitless.

Original source