为什么ArrayList的插入删除要比LinkedList的效率低？

Question

ArrayList是基于数组的，删除的时候，获取位置是O(1)，删除补位是O(n)。
LinkedList是基于链表的，删除的时候，获取位置是O(n)，删除是O(1)。
插入的操作同理。
这么看并没有什么区别啊，《Java数据结构与算法》里说用Iterator就可以解决LinkedList删除操作的inefficient问题。

为什么LinkedList更高效？Iterator为什么比顺序遍历链表要节省时间？

Answer 1

首先要明确一点：ArrayList用for循环遍历比iterator迭代器遍历快，LinkedList用iterator迭代器遍历比for循环遍历快。至于Iterator为什么比顺序遍历链表要节省时间，我的理解是，由于arrayList基于数组，下标明确，使用for循环的时候，get(i)效率很高；而linkedList基于链表，get(i)复杂度是O(n)，加上循环的次数就是O(n^2)，但是用iterator.next()则不需要下标，只需要算上循环的复杂度就可以了