「陣列」還是「鏈結串列」？影響程式效率的關鍵概念

我們透過程式讓電腦幫忙處理資料，但對電腦來說這些資料有不同的類型及擺放方式，陣列與連結串列就這些柏訪方式，如果能先了解資料的類型還有擺放方式，才能夠順利指引電腦讀取及處理資料。這些概念的理解，並不影響工程師的程式語言撰寫，卻可能是程式內容優劣的關鍵。許多人可能會以為會寫出程式就好，但真正了解兩種儲存資料格式的差異與優勢，對於未來程式的應用與效率是有幫助的。有人說：「語言只是的工具，演算法才是靈魂。」對於想要強化程式能力的人來說，了解背後的邏輯與原理，更能快速在多種解法中，找到最佳的做法。

除了陣列與連結串列，還有哪些演算法背後的概念需要知道？《白話演算法！培養程式設計的邏輯思考》透過圖像，將原本需要空泛想像的計算機運作流程，以更具體的方式傳達給讀者。讓程式初學者可以降低學習的成本；對於已有基本概念的讀者，則能補強原先較為模糊的脈絡。作者以自身的學習經驗出發，藉由輕鬆的程式流程插圖，有助於學習者以圖像學習了解演算法背後的脈絡；即使是對數學感到恐懼的讀者，也能輕鬆理解。透過書中的小練習，更能加深學習印象。以下是《白話演算法！培養程式設計的邏輯思考》的精彩內容摘錄整理：

陣列 (array) 與鏈結串列 (linked list)

有時候你需要將多個元素儲存到記憶體中。例如要開發一個管理待辦事項的程式，就得將多個待辦事項存入記憶體。那麼你該選擇陣列還是鏈結串列呢？

陣列 (array)

我們先說明將多個待辦事項存入陣列中，因為陣列的概念最容易理解。選用陣列表示所有的待辦事項都連續 ( 緊鄰著) 存入記憶體裡。

假設你想新增第四個待辦事項，但是下一個位置已經被佔用了！

這就像和兩位朋友去看電影，在電影院找到座位後，突然又有一位朋友臨時加入，但是旁邊已經沒有座位了，這時如果你們還是要坐在一起， 那就必需移動到可以容納 4 個人的新位置。如果記憶體遇到這樣的情況， 必須請電腦提供可以容納 4 個待辦事項的記憶體區塊，再將所有待辦事項移過去。

如果又有朋友要加入，但是旁邊的座位不夠，就得再次移動了，實在有點麻煩！同樣地，在陣列中新增元素也很麻煩。如果每次空間都不夠， 而且需要一直移到新的記憶體區塊時，新增元素的過程就會變得很冗長。

有個簡單的方法可解決，那就是「先佔位置」，就算只有 3 個待辦事項，但為了以防萬一，先跟電腦要 10 個空位。這麼一來你就可以將待辦事項增加到 10 項而不用移動了。雖然這個做法不錯，但還是有以下兩個缺點：

• 浪費空間：你可能用不到那些多申請的空間，但那些記憶體空間就這樣 浪費了。雖然你沒有使用，但是別人也無法使用。
• 得再次移動：你的待辦事項可能會超過 10 個，到頭來還是得移動。

所以囉！「先佔位置」雖然是個好方法，但並不是一個完美的解決方法。改用鏈結串列就能解決這個新增元素的問題。

鏈結串列 (linked list)

使用鏈結串列時，元素可以存放在記憶體中的任何一個空位。

採用鏈結串列，存放每個元素的同時，也會記錄下一個元素的存放位址。這樣就能循著位址找到串列的每一個元素了！

這有點像尋寶的概念。你到第一個位址時，上面寫著「去位址 123 可 找到下個元素」。你移動到位址 123 後，上面寫著「去位址 847 可找到下個元素」、…依此類推。所以要將新的元素新增到鏈結串列非常簡單，隨便在記憶體內找個空位並將該空位的位址存到上個元素裡就可以了。

使用鏈結串列就不用把元素搬來搬去，而且還可以避免發生以下的情況：假如你和 5 位朋友去看一部熱門的電影，你們 6 個人要找座位，但是電影院大爆滿，已經沒有 6 個連在一起的座位了。在使用陣列時也會遇到這樣的狀況，當你需要為陣列準備 10,000 個儲存槽時，但是記憶體沒有 10,000 個連在一起的空儲存槽，這樣就沒有空間可以建立陣列了！但是，鏈結串列這時候會說「我們分頭找座位看電影吧！」。只要記憶體有足夠的空間，就能建立鏈結串列。

既然鏈結串列這麼好用，那還要陣列做什麼？

陣列與鏈結串列的優缺點

我們常在網路上看到各種「十大排行榜」的網站，這些網站為了賺瀏覽量會用些取巧的伎倆。例如，不會將所有內容顯示在同一個網頁裡，而是一頁只顯示一個項目，當你按「下一頁」才顯示下一個項目。以「10 大電視劇反派角色」的網頁為例， 不會一次顯示所有排名；而是從排名第 10 名的紐曼 (Newman) 開始，你得在每個頁面按「下一頁」，最後才能看到排名第一的葛斯塔沃．弗林 (Gustavo Fring)。這些網站會這樣設計，是因為可以獲得 10 個頁面的廣告曝光機會，但是為了知道第一名是誰，必須按九次「下一頁」實在是很無聊。比較人性化的設計是將這 10 個演員放在同一個頁面，並讓瀏覽者點選演員名字時顯示相關資訊。

鏈結串列有類似的問題。假設你想讀取鏈結串列的最後一個元素時，你沒辦法直接讀取，因為你不知道它的位址。必須先從第一個元素取得第二個元素的位址，再從第二個元素取得第三個元素的位址，依此類推直到取得最後一個元素的位址。若你要逐一讀取元素，那鏈結串列非常適合，你可以讀取一個元素後，再依照位址讀取下一個元素。但如果你並沒有要依序讀取，那麼鏈結串列會是很糟糕的選擇。

陣列就不一樣了！你已經知道陣列內的所有位址了。舉例來說，陣列內有 5 個元素，而且位址是從 00 開始，那麼第 5 個元素的位址是多少？

用簡單的算術就能算出 04 這個答案。如果需要隨機讀取，那麼陣列就非常適合，因為可以瞬間讀取陣列內的任何一個元素。鏈結串列的元素並非連續排列，所以無法馬上算出第 5 個元素的記憶體位址，你必須要從第一個元素取得第二個元素的位址，再從第二個元素取得第三個元素的位址，依此類推直到取得第五個元素的位址。

了解陣列的「索引」(index)

陣列內的每個位置都有編號，這個編號 ( 位置 ) 叫做索引 (index)。編號不是從 1 開始，而是從 0 開始。例如下圖這個陣列編號 1 的內容為 20。

而 10 是在編號 0 的位置。這樣的編號方式常讓程式初學者感到困惑。從 0 開始會讓各種陣列相關的程式碼更容易撰寫，所以程式設計師們就延續了這個模式，幾乎所有程式語言都是從 0 開始編列陣列的元素位置，你很快就會習慣了。

每個元素的位置稱為索引 (index)。講白話一點就是，我們可以說20 在第 1 個位置，但專業的行話會說 20 的索引是 1。本書會用索引取代位置。

本文節錄自《白話演算法！培養程式設計的邏輯思考》，由旗標科技授權轉載。