ArrayList vs LinkedList from memory allocation perspective
arraylist, collections, java, linked-list, list
Solution
`LinkedList` might allocate fewer entries, but those entries are astronomically more expensive than they'd be for `ArrayList` -- enough that even the worst-case `ArrayList` is cheaper as far as memory is concerned.
(FYI, I think you've got it wrong; `ArrayList` grows by 1.5x when it's full, not 2x.)
See e.g. https://github.com/DimitrisAndreou/memory-measurer/blob/master/ElementCostInDataStructures.txt : `LinkedList` consumes 24 bytes per element, while `ArrayList` consumes in the best case 4 bytes per element, and in the worst case 6 bytes per element. (Results may vary depending on 32-bit versus 64-bit JVMs, and compressed object pointer options, but in those comparisons `LinkedList` costs at least 36 bytes/element, and `ArrayList` is at best 8 and at worst 12.)
UPDATE:
I understand from other posts here that individual elements stored in a LinkedList takes more space than an ArrayList as LinkedList also needs to store the node information, but I am still guessing for the scenario I have defined LinkedList might be a better option. Also, I do not want to get into the performance aspect (fetching, deleting etc) , as much has already been discussed on it.
To be clear, even in the worst case, `ArrayList` is 4x smaller than a `LinkedList` with the same elements. The only possible way to make `LinkedList` win is to deliberately fix the comparison by calling `ensureCapacity` with a deliberately inflated value, or to remove lots of values from the `ArrayList` after they've been added.
In short, it's basically impossible to make `LinkedList` win the memory comparison, and if you care about space, then calling `trimToSize()` on the `ArrayList` will instantly make `ArrayList` win again by a huge margin. Seriously. `ArrayList` wins.
Problem
I need to store a large amount of information, say for example 'names' in a java List. The number of items can change (or in short I cannot predefine the size). I am of the opinion that from a memory allocation perspective LinkedList would be a better option than ArrayList, as for an ArrayList once the max size is reached, automatically the memory allocation doubles and hence there would always be a chance of more memory being allocated than what is needed. I understand from other posts here that individual elements stored in a LinkedList takes more space than an ArrayList as LinkedList also needs to store the node information, but I am still guessing for the scenario I have defined LinkedList might be a better option. Also, I do not want to get into the performance aspect (fetching, deleting etc) , as much has already been discussed on it.