java - Java ArrayList插入操作的时间复杂度

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 5 年前。

Improve this question

我知道Java中的ArrayList实际上是用数组实现的。因此，向数组中插入一个元素似乎很昂贵，因为我们需要移动索引大于插入位置的所有元素。最坏的情况，即在数组的开头插入，时间复杂度可能是 O(n)？

我正在编写一个性能敏感的程序，并且经常使用插入操作。我不确定这是否会成为瓶颈，如果是的话，我必须找到一些更好的数据结构来做到这一点。

Answer 1

以下是一些基准测试结果(AL 代表ArrayList，LL 代表LinkedList，“edit”表示插入和删除):

Benchmark            (SIZE)  Mode  Samples      Score  Score error  Units

AL_accessFirst        10000  avgt        5      2.945        0.159  ns/op
AL_accessLast         10000  avgt        5      2.964        0.255  ns/op
AL_accessMiddle       10000  avgt        5      2.932        0.114  ns/op
AL_editFirst          10000  avgt        5   1898.086      100.413  ns/op
AL_editLast           10000  avgt        5     20.434        2.096  ns/op
AL_editMiddle         10000  avgt        5    893.348       31.074  ns/op
LL_accessFirst        10000  avgt        5      2.901        0.150  ns/op
LL_accessLast         10000  avgt        5      3.001        0.312  ns/op
LL_accessMiddle       10000  avgt        5   8645.194      358.769  ns/op
LL_editFirst          10000  avgt        5      8.261        0.373  ns/op
LL_editLast           10000  avgt        5     10.703        2.873  ns/op
LL_editMiddleIndx     10000  avgt        5  17075.179      730.738  ns/op
LL_editMiddleIter     10000  avgt        5   8273.984      345.155  ns/op

结果来自这里:https://stuartmarks.wordpress.com/2015/12/18/some-java-list-benchmarks/