java - 从内存分配的角度来看 ArrayList 与 LinkedList

Question

我需要存储大量信息，例如 java 列表中的“名称”。项目的数量可以改变(或者简而言之我无法预定义大小)。我认为，从内存分配的角度来看，LinkedList 将是比 ArrayList 更好的选择，因为对于 ArrayList，一旦达到最大大小，内存分配会自动加倍，因此总是有可能分配比 ArrayList 更多的内存需要什么。

我从这里的其他帖子中了解到，存储在 LinkedList 中的单个元素比 ArrayList 占用更多空间，因为 LinkedList 还需要存储节点信息，但我仍然猜测我定义的场景 LinkedList 可能是更好的选择。另外，我不想涉及性能方面(获取、删除等)，因为已经讨论了很多。

Answer 1

LinkedList可能会分配更少的条目，但这些条目比 ArrayList 更昂贵。 -- 足够了，即使是最坏的情况 ArrayList就内存而言更便宜。

(仅供引用，我认为你弄错了；ArrayList 满时增长 1.5 倍，而不是 2 倍。)

参见例如https://github.com/DimitrisAndreou/memory-measurer/blob/master/ElementCostInDataStructures.txt : LinkedList每个元素消耗 24 个字节，而 ArrayList在最好的情况下每个元素消耗 4 个字节，在最坏的情况下每个元素消耗 6 个字节。 (结果可能因 32 位与 64 位 JVM 和压缩对象指针选项而异，但在这些比较中，LinkedList 至少花费 36 个字节/元素，ArrayList 最多为 8，最坏为 12。)

更新:

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.

要清楚，即使在最坏的情况下，ArrayList比 LinkedList 小 4 倍具有相同的元素。制作 LinkedList 的唯一可能方法win 是通过调用 ensureCapacity 故意修复比较。故意夸大值，或从 ArrayList 中删除大量值添加后。

简而言之，制作LinkedList 基本上是不可能的。赢得内存比较，如果你关心空间，然后调用 trimToSize()在 ArrayList将立即使ArrayList再次以巨大的优势获胜。严重地。 ArrayList赢了。