LinkedList和ArrayList都是Java集合框架中的List接口的實(shí)現(xiàn)類，但它們的底層實(shí)現(xiàn)機(jī)制有所不同，導(dǎo)致它們在不同的場景下都有一些優(yōu)勢。
LinkedList的底層實(shí)現(xiàn)是基于鏈表結(jié)構(gòu)，它內(nèi)部維護(hù)了一個(gè)雙向鏈表。在LinkedList中插入、刪除元素時(shí)，它的時(shí)間復(fù)雜度是O(1)，因?yàn)橹恍枰淖兿噜徆?jié)點(diǎn)的指針，不需要像ArrayList一樣移動大量元素。但是在訪問元素時(shí)，因?yàn)樾枰獜念^開始遍歷到要訪問的元素位置，時(shí)間復(fù)雜度是O(n)，而且因?yàn)殒湵淼拇鎯C(jī)制是隨機(jī)的，所以緩存命中率較低，效率較低。
ArrayList的底層實(shí)現(xiàn)是基于數(shù)組結(jié)構(gòu)，它的元素是順序存儲的。在訪問元素時(shí)，由于它的內(nèi)存結(jié)構(gòu)是連續(xù)的，所以它的訪問速度非常快，時(shí)間復(fù)雜度是O(1)。但是在插入、刪除元素時(shí)，由于需要移動元素，時(shí)間復(fù)雜度是O(n)，因此對于頻繁的插入、刪除操作，ArrayList的效率較低。
因此，當(dāng)需要對List進(jìn)行頻繁的插入、刪除操作時(shí)，LinkedList的效率較高;當(dāng)需要對List進(jìn)行頻繁的訪問操作時(shí)，ArrayList的效率較高。
京公網(wǎng)安備 11010802030320號