作業系統組織資料的方法（詳解版）

下面討論作業系統實現的一個核心問題：系統如何組織資料。本節簡要討論多個基本資料結構，它們在作業系統中用得很多。

列表、堆疊及佇列

陣列是個簡單的資料結構，它的元素可被直接存取。例如，記憶體就是一個陣列。如果所存的資料項大於一位元組，那麼可用多個位元組來儲存資料項，並可按項碼 x 項大小（item number X item size）來定址。不過，如何儲存可變大小的項？再者，如何刪除一項而不影響其他項的相對位置？對於這些情況，陣列不如其他資料結構。

在電腦科學中，除了陣列，列表可能是最為重要的資料結構。不過，陣列的項可以直接存取，而列表的項需要按特定次序來存取。即列表（list）將一組資料表示成序列。實現這種結構的最常用方法是連結串列（linked list），項與項是連結起來的。連結串列包括多個型別：

• 單向連結串列（singly linked list）的每項指向它的後繼，如圖 1 所示：

---