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