Skip to content

Computing › CS 基礎 › 線性資料結構

線性資料結構 (Linear Data Structures) ​

線性資料結構的元素沿單一路徑排列,每個元素只與前後相鄰。它們的差別在於允許在哪裡新增、移除、存取;這些限制不是缺點,而是定義了結構的行為,讓某些流程變得自然。非線性的樹、堆積、雜湊表、圖見 非線性資料結構。

比較 ​

結構存取規則索引存取頭部插入 / 刪除尾部插入 / 刪除Python
陣列 / 動態陣列 (array)連續記憶體,依索引O(1)O(n)(後面全部搬移)O(1) 攤銷list、NumPy ndarray
鏈結串列 (linked list)從頭沿指標逐一走O(n)O(1)O(1)(有尾指標時)少直接用
堆疊 (stack)只在頂端進出,LIFO——O(1)list 的 append / pop
佇列 (queue)尾端進、前端出,FIFO—O(1) 出O(1) 進collections.deque
雙端佇列 (deque)兩端都可進出O(n)O(1)O(1)collections.deque

用 list.pop(0) 當佇列是常見的效能陷阱:每次都要把後面所有元素往前搬,O(n)。改用 deque.popleft()。

鏈結串列 (Linked List) ​

元素不放在連續記憶體,而是每個節點存自己的資料與指向下一個節點的參考。

python
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None          # 雙向鏈結串列再加 self.prev

head = Node("a"); head.next = Node("b"); head.next.next = Node("c")
node = head
while node:                       # 走訪:只能從頭沿指標前進
    print(node.data)
    node = node.next
類型指標取捨
單向 (singly)只指向下一個簡單、省記憶體
雙向 (doubly)前後都指可往回走、刪除已知節點 O(1);多一個指標的開銷
適合不適合
在已知節點附近頻繁插入 / 刪除(不必搬動後面的元素)需要依索引隨機存取第 i 個
實作堆疊、佇列、LRU 快取需要快取友善的連續掃描(陣列快很多)
上一頁 / 下一頁、播放清單—

堆疊 (Stack):LIFO ​

後進先出 (Last-In, First-Out):最後放進去的最先拿出來。

操作意義Python list
push放到頂端s.append(x)
pop從頂端取出s.pop()
peek看頂端不移除s[-1]
python
def balanced(text):                       # 括號是否成對:典型的堆疊問題
    pairs, stack = {")": "(", "]": "[", "}": "{"}, []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

balanced("f(a[i], {b})")    # True
balanced("(]")              # False

用途:函式呼叫堆疊 (call stack,遞迴太深會 stack overflow / Python RecursionError)、復原 (undo)、運算式解析、括號比對、DFS。

佇列 (Queue):FIFO ​

先進先出 (First-In, First-Out):最早放進去的最先移除。

python
from collections import deque

q = deque()
q.append("task_a")          # enqueue:尾端加入
q.append("task_b")
q.popleft()                 # dequeue:前端取出 → 'task_a'
q[0]                        # peek → 'task_b'

recent = deque(maxlen=3)    # 固定長度:滿了自動丟掉最舊的(滑動視窗)
用途例子
依到達順序處理工作工作排程、Slurm 等批次系統的等待佇列
生產者 / 消費者多執行緒用 queue.Queue(thread-safe);多程序用 multiprocessing.Queue
逐層擴展BFS
緩衝串流資料、訊息佇列 (Kafka、RabbitMQ)

先問資料怎麼流動(最新的先處理?依到達順序?要隨機存取?),再選結構;Python list 很方便,但不是所有情境的最佳選擇。