Linked list with multiple parent and child nodes

Question

I am trying to create a program that receives data from a file, after which it gives the numbering of unique data, the linked list also contains the parent and child lists.

Data structure:

____A / | BC | / \ E--> FG | | | IJK 

Nodes can have several of the following nodes (for example, A and C) and can have several previous nodes.

The text file contains such data, I get the data from the file and turn it into a linked list :

  A B E I A C E F J A C G K 

My question is: Is it possible to create a linked list with nodes with more than one next or several previous nodes, if so, what would the structure look like?

What I tried:

I created a structure containing an array of 4 integers for the parent and child.

 struct abcd{ char data; int nodeid; int parent[4]; int child[4]; struct abcd *next; } 

Thus, the parent array contains the node-id of most of the previous nodes (there can be more than one, because, for example, E (B and C point to it) → (node-id - 1).

The child array contains the node-id of the next moment 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 

Hope this is clear, please do not give me how I should implement this. Regards.

Answer 1

Yes, therefore it is called the directed graph. And there are about a thousand ways to implement it. The “correct” method depends entirely on how you use it, which you did not describe. Since you seem to limit this to linked lists or doubly linked lists, I just use only doubly linked lists.

Forward declare your data types

 typedef struct ItemInfo_s ItemInfo; typedef struct DoubleLinkedListNode_s DoubleLinkedListNode; 

Create a ListNode, as you always have:

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

Then create your ItemInfo:

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

In addition, to intelligently create a list of all created nodes:

 DoubleLinkedListNode *items; 

Now I won’t write all the related list management functions, but I’m sure you can understand it. By convention, I will write (B) as node pointing to element B (node.data = & B). I will also indicate any two nodes connected together with '=' and a '-' as an unbound (zero) node connection. I will write a chain of elements [- (1) = (2) = (3) -], and pointers to pointers to a chain of elements will always point to the first node in the chain ((1) in this example). Your schedule will look like this:

 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, these are 9 ItemInfos and 27 DoubleLinkedListNodes. I hardly think that I will ever put this into practice, but it is implemented using only two linked lists. This may make managing the list easier to make doubly linked rings (connecting the head and tail of the list together), but it's harder to show in text form. :)

Answer 2

You may have a 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 the following nodes, you can do node->next[i] instead of node->next , where 0<= i < 10 . When distributing / creating a node, reset all elements of the array to NULL so that you do not have garbage for uninitialized nodes.

So, suppose you add 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; 

In this, you can create a node that can contain no more than 10 next or previous nodes.

An array for simplicity, you can also do struct abcd **next; where you can have a dynamic number of next / previous nodes. You will need to allocate memory accordingly.

Answer 3

Linked and doubly linked lists are specific types of directed graphs that can be optimized in the head/tail , data/next/prev structure that you are familiar with. As you expand your capabilities, you lose this specificity and want to return to the general structure of the directed graph and work from there.

A directed graph is most easily described using an adjacency list:

You can implement this as a list of lists, or an array of lists, or an uneven array, or whatever. Now, on the right, I drew a doubly linked list in the form of a directed graph. Because next pointers are different from prev pointers, your adjacency list should keep these separate. So this will be a list of double lists:

 typedef struct _BPNode { // "Back-Pointing Node" void *data; struct _BPNode *nexts[]; struct _BPNode *prevs[]; } Node; typedef struct _BPGraph { // "Back-Pointing Graph" Node **allNodes; } BPGraph; 

Or something like that. Disclaimer: I have not tested this in the compiler. And just in case, here's a guide to reading some of the ads there .

Alternatively, you can create two oriented graphs, one of which runs forward and one runs backward. However, it will take more memory than this "reverse" graph. It will also run slower (more processor cache misses), will be less intuitive and more unpleasant to free memory.

Answer 4

Is it possible to create a linked list with nodes with more than one next or several previous nodes, if so, what would the structure look like?

Yes, perhaps - the question you should ask yourself is “how can I store a fairly large amount of data?”, The short answer is “you should use ADT." Recall that ADT is a mathematical model for collecting data .

You can implement it with any ADT, the choice of a specific ADT depends on the operations that you plan to use most often. In my example, I will use a dynamic array. The structure will be declared as follows (omitting specific fields for node):

 struct llnode { int item; struct llnode *children; int length; int capacity; }; 

... where the element is the ASCII code for "A", "B", "C", etc., and the children are a pointer to an array of structural llnodes. However, you can create a separate structure so that the dynamic array is less dirty, but it is completely up to you. The same idea applies to parent nodes.

Answer 5

You can try to separate the data from the data structure by executing lists of pointers to data objects:

 struct data_item { unsigned char data; unsigned char id; unsigned int count; // Whatever other data you want. }; struct list_node { struct data_item *item; struct list_node *next; } 

Now, when we come across the characters in the file, we insert them into the "repository" data structure. In this example, I will use a simple table, but you can use a list if you want to save space or a tree, if you want to save space while maintaining the speed of a quick search, etc.

 data_item data_table[UCHAR_MAX + 1] = {0}; ... unsigned char data = read_character_from_file(); struct data_item *di = data_table[data]; if (di == NULL) di = new_data_item(data); else ++di->count; 

And attach them to the current list:

 struct list_node *list; if (first_item_in_list()) list = new_list(di) else list - add_list(list, di); 

Now you can have as many lists as you want (even a list of lists, if you do not know the number of lists in advance).

Answer 6

What you are describing is Graph .

A (double) A linked list is actually just a one-dimensional list and is unacceptable for what you want.

There are two main ways to implement a schedule:

• Destination. Each node / node has a list of incoming and outgoing edges. Like the one you are describing.
• Adjacency matrix. A n times n matrix (where n is the number of nodes / vertices) with a record in [a][b] if node a has an edge to b .

Which of these uses depends on your use case. As a rule: if you have many vertices (tens of thousands), and you can limit the number of edges per vertex to a constant on average, then you should use lists. In other use cases, you should be better off with a matrix (mainly because of ease of implementation).

I assume your use case is limited to ASCII letters, so I would use the matrix here. With proper optimization (bit-rates, etc.) you can quickly view it.

Your implementation might look like this:

 char adj_matrix[0x80][0x80]; // I am assuming that you only have ASCII letters memset(adj_matrix, 0, sizeof(adj_matrix)); // initialise empty 

The insertion of elements will look like this:

 adj_matrix['A']['C'] = 1; // edge from A --> C 

To determine all incoming edges for "A", you will have to iterate over the matrix:

 for (i = 'A'; i <= 'Z'; i++) if (adj_matrix[i]['A']) // A has an incoming edge from i 

for outgoing in the opposite direction

 for (i = 'A'; i <= 'Z'; i++) if (adj_matrix['E'][i]) // E has an outgoing edge to i 

As already mentioned, you can significantly increase performance both in space and in time using bitfield and bit commands (for example, gcc __builtin_clzll , icc _bit_scan_reverse ).