Linked list with multiple parent and child nodes

Question

I am trying to design a program that takes in data from a file, after which it gives numbering to unique data, linked list also contains parent and child lists.

Data structure:

                   ____A
                  /    |     
                 B     C    
                 |  /    \  
                 E-->  F   G
                 |     |   |
                 I     J   K

The nodes can have more than one next nodes (e.g. A and C), and can have more than one previous nodes.

The text file contains the data like this, i'll get the data from file and turn them into linked list:

                    A
                    B
                    E
                    I

                    A
                    C
                    E
                    F
                    J

                    A
                    C
                    G
                    K

My Question: Is it possible to create linked list with nodes with more than one next or more than one previous nodes, if so how would the struct look like?

What i have tried:

I made a struct which contains an array of 4 integers for parent and child.

struct abcd{
 char data;
 int nodeid;

 int parent[4];
 int child[4];

 struct abcd *next;

}

So the parent array holds node-id of most previous node (can be more than one since e.g. E (B & C are pointing to it) --> (node-id - 1).

Child array holds node-id of instant next node (node-id +1).

There are no duplicate nodes for A or any other.

OUTPUT:

1 :  A <-- 
2 :  B <-- 1
3    E <-- 2,5
4 :  I <-- 3
5 :  C <-- 1
6 :  F <-- 3
7 :  J <-- 6
8 :  G <-- 5
9 :  K <-- 8

Hopefully its clear, please let me no how i should go about implementing it. Regards.

Answer 1

Yes, so this is called a directed graph. And there are about a thousand ways you could implement it. The "right" way depends entirely on how you will use it, which you haven't described. Since you did seem to limit this to linked lists or doubly linked lists I'll just use nothing but doubly linked lists.

Forward declare your data types

typedef struct ItemInfo_s ItemInfo;
typedef struct DoubleLinkedListNode_s DoubleLinkedListNode;

Create a ListNode like you always do:

struct DoubleLinkedListNode_s {
    DoubleLinkedListNode *next;
    DoubleLinkedListNode *prev;
    ItemInfo *data;
};

Then create your ItemInfo:

struct ItemInfo_s {
    DoubleLinkedListNode *children;
    DoubleLinkedListNode *parents;
    ...  /* other item data */
};

Also, for sanity's sake create a list of all created nodes:

DoubleLinkedListNode *items;

Now, I'm not going to write all of the linked list management functions, but I'm sure you can figure it out. By convention I'll write (B) as a node pointing to item B (node.data = &B). I'll also indicate any two nodes linked together with an '=', and a '-' as an unlinked (null valued) node linkage. I'll write a chain of elements [ -(1)=(2)=(3)- ] and by convention pointers into a chain of items will always point to the first node in the chain (the (1) in this example). Your given graph looks like this in memory:

items = [ -(A)=(B)=(C)=(E)=(F)=(G)=(I)=(J)=(K)- ]

A.children = [ -(B)=(C)- ]
A.parents = []

B.children = [ -(E)- ]
B.parents = [ -(A)- ]

C.children = [ -(E)=(G)- ]
C.parents = [ -(A)- ]

E.children = [ -(I)=(F)- ]
E.parents = [ -(B)=(C)- ]

F.children = [ -(J)- ]
F.parents = [ -(E)- ]

G.children = [ -(K)- ]
G.parents = [ -(C)- ]

I.children = []
I.parents = [ -(E)- ]

J.children = []
J.parents = [ -(F)- ]

K.children = []
K.parents = [ -(G)- ]

In total that is 9 ItemInfos and 27 DoubleLinkedListNodes. I can think of almost no reason I would ever implement this in practice, but it's implemented only using double linked lists. It might make the list management easier to do doubly linked rings (connecting the head and tail of the list together) but that's harder to show in text form. :)

Answer 2

You can have structure like this:

struct abcd{
 char data;
 struct abcd *next[10];  //array of next nodes
 struct abcd *prev[10];  //array of previous nodes
}

When accessing next nodes you can do node->next[i] instead of node->next, where 0<= i < 10. When allocating/creating node reset all array elements to NULL so that you don't have garbage for uninitialized nodes.

So lets suppose you added node for 'A', then you can add nodes for 'B' and 'C' as

int idx;
//find index for free element.
for(idx = 0; nodeA->next[idx] && idx < 10; idx++)
   ;
if(idx == 10)
   //dont have free space
nodeA->next[idx] = nodeB;
nodeB->prev[0] = nodeA;

//similarly add for C, you may have to check for appropriate idx!
nodeA->next[idx++]] = nodeC;
nodeC->prev[0] = nodeA;

With this basically you can create node which can have at most 10 next or previous nodes.

Array is for simplicity, you can also do struct abcd **next; where you can have dynamic number of next/prev nodes. You will have to allocate the memory appropriately though.