為什么ArrayList的插入刪除要比LinkedList的效率低？

ArrayList是基于數(shù)組的，刪除的時(shí)候，獲取位置是O(1)，刪除補(bǔ)位是O(n)。
LinkedList是基于鏈表的，刪除的時(shí)候，獲取位置是O(n)，刪除是O(1)。
插入的操作同理。
這么看并沒(méi)有什么區(qū)別啊，《Java數(shù)據(jù)結(jié)構(gòu)與算法》里說(shuō)用Iterator就可以解決LinkedList刪除操作的inefficient問(wèn)題。

為什么LinkedList更高效？Iterator為什么比順序遍歷鏈表要節(jié)省時(shí)間？

回答

編輯回答

悶騷型

首先要明確一點(diǎn)：ArrayList用for循環(huán)遍歷比iterator迭代器遍歷快，LinkedList用iterator迭代器遍歷比f(wàn)or循環(huán)遍歷快。
至于Iterator為什么比順序遍歷鏈表要節(jié)省時(shí)間，我的理解是，由于arrayList基于數(shù)組，下標(biāo)明確，使用for循環(huán)的時(shí)候，get(i)效率很高；
而linkedList基于鏈表，get(i)復(fù)雜度是O(n)，加上循環(huán)的次數(shù)就是O(n^2)，但是用iterator.next()則不需要下標(biāo)，只需要算上循環(huán)的復(fù)雜度就可以了

2017年9月11日 05:33