特定android示例上的LinkedList vs ArrayList[重复]

Question

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

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

目标硬件是Android操作系统。我应该以返回数组列表或链接列表的方式对类进行编码吗？在以下情况下，哪种情况更好：

>

myList始终包含100个元素

myList始终包含10个元素

也许我看到了一个没有问题的问题。你认为在这种情况下我不应该关心性能，因为问题大小（对于1和2）都很小吗？

我知道过早优化是万恶之源这句话，这就是为什么我在改变我的植入之前犹豫不决（至于现在，我的A对象返回一个ArrayList）。




Answer 1

简而言之，如果你经常添加/删除/更新元素，尤其是对于第一个/最后一个元素，你应该选择LinkedList，因为它包含一个指向第一个和最后一个节点的指针

例如，从链表中删除元素的成本O（1），而对数组（数组列表）这样做的成本O（n）。

但是，正如bigoh post所说，这并不总是一条规则：

对于大量数据，大哦符号可以给出非常好的性能想法，但是唯一确定的真正方法是在大数据集上进行实际尝试。大哦符号可能没有考虑到性能问题，例如，随着虚拟内存使用的增加，对分页的影响。虽然基准测试更好，但在设计过程中不可行，所以大哦复杂性分析是选择。

这篇文章验证了以上内容，其中LinkedList也被证明很慢。

参考
http://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.htmlhttp://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html