LinkedList和ArrayList在特定的Android示例中的比较

Question

24 浏览2023年5月23日

匿名的 2023年1月22日

0 Comments

这个问题已经有了答案：

在Java中什么时候应该使用LinkedList而不是ArrayList？

我从我的 A 类返回一个列表。我想把列表的第一个元素删除并将其作为最后一个元素添加到同一个列表中。我是这样做的。

myList.add(myList.get(0));
myList.remove(0);

目标硬件是 Android 操作系统。我应该以哪种方式编写我的 A 类以返回一个 ArrayList 还是一个 LinkedList？哪一个对以下情况更好：

也许我在无谓地担心。您认为我在这种情况下不应该关注性能，因为问题规模对于1和2来说都很小吗？

我知道有一句话是这样说的，“过早的优化是万恶之源”。这就是为什么我在改变我的实现之前犹豫不决的原因（目前，我的 A 对象返回一个 ArrayList）。

admin 更改状态以发布 2023年5月23日

0

匿名的 · Answer 1 · 2023-01-22T20:57:58+00:00

简短回答：如果您经常添加/删除/更新元素，尤其是首尾元素，应该选择 LinkedList，因为它包含对第一个和最后一个节点的指针。

详细回答：对于添加操作，LinkedList 的性能为 O(1)，而 ArrayList 的性能在最坏情况下为 O(n)。
LinkedList 更快。它只需引用节点，然后第一个节点消失：

此外，ArrayList 适用于写入一次，多次读取或追加，但在从前面或中间添加/删除方面不太适用。

enter image description here

例如，从链表中删除一个元素的成本是O(1)，而从数组（数组列表）中删除一个元素的成本是O(n)。

但是，这并不总是适用的规则，如bigoh发布的文章所述:

大O符号可以为大量数据提供非常好的性能提示，但确定性能的唯一真实方法是在大数据集上进行实际尝试。可能存在未被大O符号考虑到的性能问题，例如随着虚拟内存使用量的增加，对分页的影响。尽管基准测试更好，但在设计过程中它们是不可行的，因此选择使用大O复杂性分析。

这得到了这篇文章的验证，其中LinkedList也被证明很慢。