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

VinceNtD
  • 1
新手上路,请多包涵

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

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

回复
阅读 1.9k
1 个回答

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

宣传栏