一、鏈表讀取慢刪除卻很快的原因

鏈表是一種線性數(shù)據(jù)結(jié)構(gòu)，它將數(shù)據(jù)元素存儲(chǔ)在稱為節(jié)點(diǎn)的獨(dú)立對(duì)象中，并通過指針將這些節(jié)點(diǎn)連接在一起。鏈表在讀取和刪除操作上的性能特點(diǎn)與其內(nèi)部結(jié)構(gòu)有關(guān)。

鏈表讀取慢的主要原因在于其訪問方式。鏈表中的元素不是連續(xù)存儲(chǔ)的，而是通過指針鏈接在一起的。這意味著要訪問鏈表中的某個(gè)元素，需要從頭節(jié)點(diǎn)開始，依次遍歷鏈表直到找到目標(biāo)元素。因此，鏈表的訪問時(shí)間復(fù)雜度是O(n)，其中n表示鏈表的長(zhǎng)度。這種訪問方式相對(duì)較慢，尤其是當(dāng)鏈表很長(zhǎng)時(shí)。

此外，鏈表的非連續(xù)存儲(chǔ)方式還導(dǎo)致了較低的緩存利用率。計(jì)算機(jī)內(nèi)存中的緩存對(duì)連續(xù)存儲(chǔ)的數(shù)據(jù)訪問具有更高的性能。而鏈表的節(jié)點(diǎn)可能分散在內(nèi)存的不同位置，因此在訪問鏈表時(shí)，緩存性能較差，進(jìn)一步影響了讀取速度。

鏈表刪除操作的速度相對(duì)較快，主要原因在于其結(jié)構(gòu)和刪除過程。一旦我們找到了要?jiǎng)h除的節(jié)點(diǎn)，刪除操作就變得非常簡(jiǎn)單。我們只需要調(diào)整相鄰節(jié)點(diǎn)之間的指針指向，即可從鏈表中移除目標(biāo)節(jié)點(diǎn)。在已知待刪除節(jié)點(diǎn)的情況下，鏈表的刪除操作時(shí)間復(fù)雜度為O(1)。

如果我們不知道要?jiǎng)h除的節(jié)點(diǎn)的位置，我們?nèi)匀恍枰獜念^節(jié)點(diǎn)開始遍歷鏈表以找到目標(biāo)節(jié)點(diǎn)。在這種情況下，鏈表的刪除操作時(shí)間復(fù)雜度為O(n)。然而，在很多實(shí)際應(yīng)用場(chǎng)景中，我們常常在刪除操作前已經(jīng)定位到了目標(biāo)節(jié)點(diǎn)，因此鏈表的刪除操作通常被認(rèn)為是快速的。