从内存分配角度看ArrayList与LinkedList

Question

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

我从其他帖子中了解到,存储在LinkedList中的各个元素比ArrayList占用更多空间,因为LinkedList也需要存储节点信息,但我仍然猜测我已定义的场景LinkedList可能是更好的选择.此外,我不想进入性能方面(获取,删除等),因为已经讨论过很多内容.

Answer 1

LinkedList可能会分配更少的条目,但这些条目在天文数字上比它们的价格更高ArrayList- 足以使得即使最糟糕的情况ArrayList就内存而言也更便宜.

(仅供参考,我认为你错了; ArrayList当它满了时增长1.5倍,而不是2倍.)

例如,参见http://code.google.com/p/memory-measurer/wiki/ElementCostInDataStructures:LinkedList每个元素消耗24个字节,而ArrayList最佳情况下每个元素消耗4个字节,最差情况下每个元素消耗6个字节.(结果可能因32位与64位JVM和压缩对象指针选项而异,但在这些比较LinkedList中至少需要36个字节/元素,ArrayList最多为8个,最差为12个.)

更新:

我从其他帖子中了解到,存储在LinkedList中的各个元素比ArrayList占用更多空间,因为LinkedList也需要存储节点信息,但我仍然猜测我已定义的场景LinkedList可能是更好的选择.此外,我不想进入性能方面(获取,删除等),因为已经讨论过很多内容.

要明确的是,即使在最坏的情况下,ArrayList也要比LinkedList具有相同元素的小4倍.LinkedList获胜的唯一可能方法是通过调用ensureCapacity故意夸大的值来故意修复比较,或者ArrayList在添加之后删除许多值.

总之,这基本上是不可能使LinkedList赢得内存比较,如果你关心的空间,然后调用trimToSize()上ArrayList会立即让ArrayList再次以巨大的优势夺冠.认真. ArrayList胜.

Answer 2

ArrayList 对每个对象使用一个引用（或者当其大小是所需大小的两倍时使用两个引用）。这通常是 4 个字节。

LinkedList 仅使用其需要的节点，但每个节点可以是 24 字节。

因此，即使在最坏的情况下，ArrayList 也会比 LinkedList 小 3 倍。

对于获取ARrayList支持随机访问O(1)，但LinkedList是O(n)。对于从末尾删除，都是 O(1)，对于从中间某处删除 ArrayList 是 O(n)

除非您有数百万个条目，否则集合的大小不太重要。首先重要的是条目的大小，无论使用什么集合，条目的大小都是相同的。

Answer 3

...但我仍在猜测我已定义的场景LinkedList可能是更好的选择

你的猜测不正确.

一旦超过了阵列列表的初始容量,后备的大小将在1到2个引用之间乘以条目数.这是由于用于增长后备阵列的策略.

对于链表,每个节点至少占条目数的3倍,因为每个节点都有一个next和prev引用以及条目引用.(事实上​​,它超过3次,因为节点的对象头和填充使用了空间.根据JVM和指针大小,它可以多达6次.)

链接列表使用的空间少于数组列表的唯一情况是,如果您严重高估了数组列表的初始容量.(对于非常小的清单......)

当你考虑它时,链接列表中唯一真正的优势就是在数组列表中插入和删除元素.即便如此,这取决于你是如何做到的.