ArrayList和LinkedList有什么區(qū)別?

ArrayList和LinkedList都實(shí)現(xiàn)了List接口,他們有以下的不同點(diǎn)：

·ArrayList是基于索引的數(shù)據(jù)接口，它的底層是數(shù)組。它可以以0（1)時(shí)間復(fù)雜度對元素進(jìn)行隨機(jī)訪問。與此對應(yīng)，LinkedList是以元素列表的形式存儲(chǔ)它的數(shù)據(jù)。

每一個(gè)元素都和它的前一個(gè)和后一個(gè)元素鏈接在一起，在這種情況下，查找某個(gè)元素的時(shí)間復(fù)雜度是0（n）。

·相對于ArrayList,LinkedList的插入,添加,刪除操作速度更快，因?yàn)楫?dāng)元素被添加到集合任意位置的時(shí)候，不需要像數(shù)組那樣重新計(jì)算大小或者是更新索引。

·LinkedList比ArrayList更占內(nèi)存，因?yàn)長inkedList為每一個(gè)節(jié)點(diǎn)存儲(chǔ)了兩個(gè)引用，一個(gè)指向前一個(gè)元素，一個(gè)指向下一個(gè)元素。