B4 抽象資料型別（HL）
B4 抽象資料型別（Abstract Data Types, ADT）是整個 IB Computer Science 唯一完全屬於 HL 的單元。ADT 只定義「資料能做哪些操作」，不規定「內部怎麼實作」；本單元學習如何用程式實作鏈結串列、堆疊、佇列、二元搜尋樹、集合與雜湊表，並比較它們的效率。
HL 專屬單元
B4 整個單元只出現在 HL 考卷，SL 學生可略過。SL 學生在 B2.2 資料結構 已學過堆疊與佇列的基本概念。
本單元頁面
| 頁面 | 內容 |
|---|---|
| 線性 ADT：鏈結串列、堆疊與佇列 | 單向與雙向鏈結串列、用陣列或鏈結串列實作堆疊與佇列、環狀佇列 |
| 樹、集合與雜湊表 | 二元搜尋樹與走訪、集合運算、雜湊函式與碰撞處理 |
什麼是抽象資料型別？
ADT 是 抽象化 的應用：使用者只需要知道介面（interface），例如堆疊有 push、pop、peek、is_empty；至於底層用陣列還是鏈結串列實作，可以隨時更換而不影響使用者的程式。
| ADT | 主要操作 | 常見實作 |
|---|---|---|
| 串列（list） | 插入、刪除、搜尋、走訪 | 陣列、鏈結串列 |
| 堆疊（stack） | push、pop、peek | 陣列、鏈結串列 |
| 佇列（queue） | enqueue、dequeue | 環狀陣列、鏈結串列 |
| 二元搜尋樹（BST） | 插入、搜尋、刪除、走訪 | 節點與指標 |
| 集合（set） | 加入、移除、成員判斷、聯集、交集 | 雜湊表、BST |
| 雜湊表（hash table） | 依鍵存取、插入、刪除 | 陣列 + 雜湊函式 |
推薦影音
資料結構總覽
簡述：Crash Course 用動畫說明陣列、鏈結串列、堆疊、佇列、樹與圖在記憶體中的樣子，適合作為 B4 的整體入門。
單元總複習
總複習：選擇資料結構
為下列需求選擇最適合的 ADT 並說明理由：(a) 依學號快速查詢學生資料；(b) 印表機依送出順序列印；(c) 維持一份隨時可依字母順序列出的單字清單，並經常插入新字。
參考答案
(a) 雜湊表，依鍵查詢平均 O(1)；(b) 佇列，先進先出；(c) 二元搜尋樹，插入平均 O(log n)，中序走訪即可依字母順序列出。