資料結構與演算法輕鬆學

02排隊的藝術，直線的智慧

你有沒有在連假時去排過那種超有名的拉麵店？長長的人龍，一個接著一個，非常有秩序。或者，你有沒有坐過火車？第一節車廂、第二節車廂……一直到最後一節，每一節車廂都有編號，你可以很輕易地說出：「我在第五節車廂。」這些我們生活中常見的「排隊」場景，其實就是程式世界裡最基本、也最重要的兩種資料結構：「陣列（Array）」和「連結串列（Linked List）」。 我們先來聊聊「陣列」，它就像是火車車廂。有什麼特色呢？首先，每一節車廂都是「連續」的，你走過第一節，就一定會到第二節，中間不會突然跳到別的地方。再來，每一節車廂都有「編號」，也就是所謂的「索引」。當列車長廣播說：「請第五節車廂的旅客準備下車」，你可以馬上知道是哪一節，完全不用從頭開始找。這就是陣列最大的優點：「讀取速度快」。在程式裡，如果你把一堆資料放進陣列，電腦的記憶體就像是火車鐵軌，會幫你安排一塊「連續」的空間。只要你告訴電腦：「我要拿第100個資料」，它會立刻透過數學計算（地址 = 起始地址 + 索引 資料大小），「咻」一下就跳到那個位置，把資料拿給你。這速度，簡直比高鐵還快，我們在複雜度分析上會說它的讀取時間是O(1)，意思就是「瞬間完成」。 聽起來很棒對吧？但火車車廂有什麼缺點？你想想看，如果在尖峰時刻，第三節和第四節車廂之間，突然想再加掛一節新的「親子車廂」，辦得到嗎？超難！你得先把後面的所有車廂都移開，騰出空間，再把新的車廂加進去，然後再把後面的車廂一個個接回來。這工程也太浩大了！同樣地，如果你想把第二節車廂拿掉，也是一樣麻煩，你得把後面的車廂全部往前移一格來補上空位。 這就是陣列最大的缺點：「新增和刪除資料很慢」。因為它要求所有東西都必須是連續的，所以任何「插隊」或「離隊」的行為，都會引發一連串的「大風吹」，非常沒有效率。就像是你在Excel表格裡，要在中間插入一列，整張表格下半部的資料都得往下移，資料一多，電腦就會轉圈圈給你看。所以，陣列適合用在那些「資料不太會變動，但需要經常快速讀取」的場景。例如，存放一整年365天的日曆資料，或是儲存一張圖片的像素資料，這些都很適合用陣列。 那如果我們的資料需要很頻繁地變動呢？像是排隊買珍珠奶茶，隨時有人會放棄不排了，也可能會有朋友來插隊。這時候，「連結串列」就登場了。 你可以把連結串列想像成去玩「大地遊戲」或「尋寶遊戲」。你拿到第一張線索卡（第一個資料），上面寫著：「寶藏的一部分在這裡，下一個線索在公園的溜滑梯下。」於是你跑到溜滑梯，又拿到一張線索卡，上面寫著：「下一個線索在便利商店的櫃檯。」就這樣一個接一個，直到你找到最後一個寶藏為止。 在連結串列裡，每個資料都像是一張線索卡，它包含兩個東西：一個是「資料本身」（寶藏的一部分），另一個是「指向下一個線索卡的指標」（下一個線索在哪裡）。這些線索卡（資料）在記憶體裡，並不需要像火車車廂一樣連續放好，它可以散落在各地，東一個西一個，反正只要靠著「指標」這個線索，就能把所有資料串起來。 這樣做有什麼好處？好處可大了！如果今天有人想插隊怎麼辦？簡單！假設你想插在A和B之間，你只要把A手上的線索卡，改成指向你，然後把你自己的線索卡，指向B。這樣就搞定了！原本A->B的隊伍，就變成了A->你->B。完全不需要移動後面所有的人。同樣地，如果有人想離隊，也只要把前一個人手上的線索，指向後一個人，跳過中間想離開的人，他就成功離隊了。 這就是連結串列最大的優點：「新增和刪除資料超快」。它的時間複雜度也是O(1)，瞬間完成。但是，它的缺點是什麼？你想想看，如果尋寶遊戲的主辦單位突然問你：「請問第五個線索在哪裡？」你該怎麼辦？你沒辦法立刻回答，你只能從第一張線索卡開始，一個一個往下找，直到你數到第五個為止。這就是連結串列的致命傷：「讀取特定位置的資料很慢」。它的時間複雜度是O(n)，n代表資料的總數，意思就是最壞的情況下，你可能要找遍整個隊伍才找得到。 所以，陣列和連結串列，就像是硬幣的兩面，各有優缺點，沒有誰絕對比較好，端看你的「應用場景」。這也是作者在書中不斷強調的觀念：一個好的工程師，不是去背誦哪個資料結構比較厲害，而是要去「理解」它們各自的特性，然後像個醫生一樣，針對不同的「病症」（需求），開出最適合的「藥方」（資料結構）。這就像是你去台北，如果只是要去隔壁巷口的7-11，你應該會走路去（簡單快速）；但如果你要去高雄，你就會選擇搭高鐵（雖然票價貴但長途效率最高）。為不同的問題，選擇對的工具，這才是資料結構與演算法的精髓所在。

使用 LeapAhead 應用程式繼續閱讀

完整摘要正在應用程式中等您

繼續閱讀