Java ArrayList的时间复杂度

我发现这个问题的其他条目涉及特定方法，但没有全面的。 我想validation自己对这种数据结构中最常用的方法的理解：

O（1） – 恒定时间：

isEmpty() add(x) add(x, i) set(x, i) size() get(i) remove(i) 

O（N） – 线性时间：

 indexof(x) clear() remove(x) remove(i) 

它是否正确？ 谢谢你的帮助。

Answer 1

最好的资源来自官方API ：

size，isEmpty，get，set，iterator和listIterator操作以恒定时间运行。 添加操作以分摊的常量时间运行，即添加n个元素需要O（n）时间。 所有其他操作都以线性时间运行（粗略地说）。 与LinkedList实现相比，常数因子较低。