ArrayList是基于数组的,删除的时候,获取位置是O(1),删除补位是O(n)。
LinkedList是基于链表的,删除的时候,获取位置是O(n),删除是O(1)。
插入的操作同理。
这么看并没有什么区别啊,《Java数据结构与算法》里说用Iterator就可以解决LinkedList删除操作的inefficient问题。
为什么LinkedList更高效?Iterator为什么比顺序遍历链表要节省时间?
ArrayList是基于数组的,删除的时候,获取位置是O(1),删除补位是O(n)。
LinkedList是基于链表的,删除的时候,获取位置是O(n),删除是O(1)。
插入的操作同理。
这么看并没有什么区别啊,《Java数据结构与算法》里说用Iterator就可以解决LinkedList删除操作的inefficient问题。
为什么LinkedList更高效?Iterator为什么比顺序遍历链表要节省时间?
4 回答1.5k 阅读✓ 已解决
4 回答1.3k 阅读✓ 已解决
1 回答2.6k 阅读✓ 已解决
3 回答1.9k 阅读
2 回答778 阅读✓ 已解决
1 回答2.3k 阅读
2 回答1.7k 阅读
首先要明确一点:ArrayList用for循环遍历比iterator迭代器遍历快,LinkedList用iterator迭代器遍历比for循环遍历快。
至于
Iterator为什么比顺序遍历链表要节省时间
,我的理解是,由于arrayList基于数组,下标明确,使用for循环的时候,get(i)效率很高;而linkedList基于链表,get(i)复杂度是O(n),加上循环的次数就是O(n^2),但是用iterator.next()则不需要下标,只需要算上循环的复杂度就可以了