|
Indeed. You're more likely to run out of memory building the tree with 1B nodes than you are to run out of memory using an array with 1B elements, as the combination of nodes and the objects will be larger than an object.
The only potential exception is when memory is fragmented, and it is difficult to dynamically allocate a very large contiguous array.
A more usual reason for using a linked list and not an array is because insertions into the middle of the list are faster. It is certainly not done to save memory, or to support larger sets of objects. The more usual reason to use an array (apart from the fact it's contiguous) is that, once the elements are in the array, accessing them in random order is faster.
|