Trees: Linked lists versus arrays (efficiency)

Question

This is a task for which I have problems with the answer.

"Suppose a tree can have up to k children per node. Let v be the average number of children per node. For what value (s) v is it more efficient (in terms of space used) for storing child nodes in a linked list compared to storage in the array? Why? "

I think I can answer "why?". more or less in simple English - it will be more efficient to use a linked list, because instead of having empty empty nodes (i.e. empty indexes in the array, if your average value is less than the maximum), taking up memory, you only allocate space for node in a linked list when you really fill the value.

So, if you have an average of 6 children, when your maximum is 200, the array will create space for all 200 children of each node when creating the tree, but the linked list will allocate space for the nodes as needed. Thus, with the linked list, the used space will be approximately (?) Average; with an array, the interval used will be maximum.

... I do not see when it would be more efficient to use an array. Is this a trick question? Should I take into account the fact that the array must have a limit on the total number of nodes when it is created?

Answer 1

k (). 2 node ( ). 3 node.

n - node A:

• k
• 2 n
• 3 n

k , 2 n 3 n .

Answer 2

... , . ?

. , . ( )?

( !), . , (, , ).

Answer 3

, .
, node, ,
.

. , , ,
, 4 , , , .

Answer 4

, LinkedList, , , , TimeTableItem - - . , LinkedList node. , List, .

Answer 5

You assume that the array cannot be dynamically redistributed. If possible, the array wins because it should be no more than k elements (plus permanent overhead), and also because pointers do not need an element store.