Originally Posted by
Subsonics
What is the purpose of the parent, child members? If there is no special head struct, surely something like struct node *list; will be enough.
That will give you only one list, and a singly-linked list at that.
Consider the situation when we wish to describe the following structure:
Code:
Alice ─ Cecilia ─ David ─ Felicity
│ │
Bob Erwin
The root, is obviously Alice: the pointer that we use to manage the entire structure is Alice. If we choose to use NULL to terminate each list, then
Code:
Alice: .parent = NULL, .child = Cecilia, .prev = NULL, .next = Bob
Bob: .parent = NULL, .child = Cecilia, .prev = Alice, .next = NULL
Cecilia: .parent = Alice, .child = David, .prev = NULL, .next = NULL
David: .parent = Cecilia, .child = Felicity, .prev = NULL, .next = Erwin
Erwin: .parent = Cecilia, .child = Felicity, .prev = David, .next = NULL
Felicity: .parent = David, .child = NULL, .prev = NULL, .next = NULL
If you added Esther under Erwin, then
Code:
Erwin: .parent = Cecilia, .child = Felicity, .prev = David, .next = Erwin
Esther: .parent = Cecilia, .child = Felicity, .prev = Erwin, .next = NULL
As you can see, inserting something between Cecilia and David would mean you need to also reparent Erwin (and Esther, if added under Erwin). On the other hand, you can easily "move" in either direction, when given just one node.
Often, the .child pointer is left NULL for all but the first child. In that case, to go "down", you use ->parent->child->child if ->child==NULL.
___________________________
I suspect you (Subsonics) refer to another method, where one uses two different structures to describe nodes (without data) and leaves (with data). Doubly-linking, as per the OP's request, that would be for example:
Code:
struct leaf {
struct list *prev;
struct list *next;
/* Data fields */
};
struct node {
struct node *prev;
struct node *next;
struct leaf *list;
};
In this case, we'd have one list of nodes, and the data lists hanging off those:
Code:
node0: .prev = NULL, .next = node1, .list = Alice
node1: .prev = node0, .next = node2, .list = Cecilia
node2: .prev = node1, .next = node3, .list = David
node3: .prev = node2, .next = NULL, .list = Felicity
Alice: .prev = NULL, .next = Bob
Bob: .prev = Alice, .next = NULL
Cecilia: .prev = NULL, .next = NULL
David: .prev = NULL, .next = Erwin
Erwin: .prev = David, .next = NULL
Felicity: .prev = NULL, .next = NULL
The pointer needed to refer to the entire structure would point to node0.
This is closer to the concept of list of lists rather than 2D arrays. The thing to note is that if given a data node, there is no way to navigate vertically; one must have both the vertical node, and the horizontal leaf, to be able to navigate as one would in an array.
You can also form either or both lists into rings, where first .prev points to the last item, and last .next points to the first item. Or instead of NULL, have them point to the leaf itself.
Data structures formed from more than one dimension of linked lists are a bit hard to fathom in the abstract sense. If the Original Poster (Isnalla) could state an example use case -- say, directories and files, or something real-worldly --, I could perhaps show better examples. There are a lot of variations and combinations of the above two structures that are applicable in different situations; there simply is no one structure that would fit all cases best.
So, Isnalla, give us a real-world use case, and we'll discuss further.
. Im currently on my 2nd year of my BS computer science course.
