資料結構

資料結構是一種組織資料的方式，目的是讓你真正在意的那些操作變得容易。想想你在家裡怎麼收納東西。寫在一張紙條上的購物清單，從上往下讀很方便，可要往中間插一項就糟透了。一個按字母順序擺放瓶子的香料架，讓你一把抓到奧勒岡，卻很難一直保持有序。一疊盤子讓你眨眼間從頂上取走，卻永遠沒法從底下拿。抽象地說，沒有哪一種「最好」——每一種都是為了讓某些動作變便宜而塑形的，代價是另一些動作變貴。

在計算裡也是一樣。陣列讓你瞬間取到第 i 個元素，卻在中間插入時很慢。鏈結串列把這個取捨反了過來。雜湊表讓「這東西在不在？」幾乎瞬間得到答案，卻丟掉了任何次序感。二元搜尋樹既保持有序，又仍允許快速查找。資料結構是位元組的具體佈局，再加上定義在其上的那組操作；它是演算法的搭檔，因為一個演算法的速度，往往完全取決於它所執行其上的結構。

這正是為什麼這門學科的兩半——演算法與資料結構——總是合在一起教。選對結構，常常就是「一眨眼就跑完的程式」與「慢到幾乎停擺的程式」之間的分水嶺。訣竅在於：先點名你最常做的那些操作，再選一種能讓這些操作變便宜（往往是 O(1) 或 O(log n)）、同時讓其餘操作還能忍受的結構。我們用來比較它們的推理工具，就是漸近分析。