《演算法圖解》之數組和鏈表的比較

數組&鏈表比較

數組

使用數組意味著所有待辦事項在內存中都是相連的（緊靠在一起的）。所以在數組中添加新元素也可能很麻煩。如果沒有了空間，就得移到內存的其他地方，因此添加新元素的速度會很慢。一種解決之道是「預留座位」：即便當前只有3個待辦事項，也請計算機提供10個位置，以防需要添加待辦事項。這樣，只要待辦事項不超過10個，就無需轉移。這是一個不錯的權變措施，但你應該明白，它存在如下兩個缺點。

你額外請求的位置可能根本用不上，這將浪費內存。你沒有使用，別人也用不了。

待辦事項超過10個後，你還得轉移。

鏈表

鏈表中的元素可存儲在內存的任何地方。鏈表的每個元素都存儲了下一個元素的地址，從而使一系列隨機的內存地址串在一起。使用鏈表時，根本就不需要移動元素。這猶如尋寶遊戲。你前往第一個地址，那裡有一張紙條寫著「下一個元素的地址為123」。因此，你前往地址123，那裡又有一張紙條，寫著「下一個元素的地址為847」，以此類推。在鏈表中添加元素很容易：只需將其放入內存，並將其地址存儲到前一個元素中。

使用鏈表時，根本就不需要移動元素。這還可避免另一個問題。假設你與五位朋友去看一部很火的電影。你們六人想坐在一起，但看電影的人較多，沒有六個在一起的座位。使用數組時有時就會遇到這樣的情況。假設你要為數組分配10 000個位置，內存中有10 000個位置，但不都靠在一起。在這種情況下，你將無法為該數組分配內存！鏈表相當於說「我們分開來坐」，因此，只要有足夠的內存空間，就能為鏈表分配內存。

鏈表的優勢在插入元素方面，那數組的優勢又是什麼呢？

在需要讀取鏈表的最後一個元素時，你不能直接讀取，因為你不知道它所處的地址，必須先訪問元素#1，從中獲取元素#2的地址，再訪問元素#2並從中獲取元素#3的地址，以此類推，直到訪問最後一個元素。需要同時讀取所有元素時，鏈表的效率很高：你讀取第一個元素，根據其中的地址再讀取第二個元素，以此類推。但如果你需要跳躍，鏈表的效率真的很低。

數組與此不同：你知道其中每個元素的地址。（因為是按順序存儲的）只需執行簡單的數學運算就知道。需要隨機地讀取元素時，數組的效率很高，因為可迅速找到數組的任何元素。在鏈表中，元素並非靠在一起的，你無法迅速計算出第五個元素的內存地址，而必須先訪問第一個元素以獲取第二個元素的地址，再訪問第二個元素以獲取第三個元素的地址，以此類推，直到訪問第五個元素。

附加：log的理解

一般對於對數log的解釋都是這樣的：如果a的x次方等於N（a>0，且a不等於1），那麼數x叫做以a為底N的對數（logarithm），記作x=logaN。其中，a叫做對數的底數，N叫做真數。

很抽象有木有！

《演算法圖解》中這樣解釋：log10100相當於問「將多少個10相乘的結果為100」。答案是兩個：10 × 10 = 100。因此，log10100 = 2

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！