hosteons中文网

下面讨论操作系统实现的一个核心问题：系统如何组织数据。本节简要讨论多个基本数据结构，它们在操作系统中用得很多。

列表、堆栈及队列

数组是个简单的数据结构，它的元素可被直接访问。例如，内存就是一个数组。如果所存的数据项大于一字节，那么可用多个字节来保存数据项，并可按项码 x 项大小（item number X item size）来寻址。不过，如何保存可变大小的项？再者，如何删除一项而不影响其他项的相对位置？对于这些情况，数组不如其他数据结构。

在计算机科学中，除了数组，列表可能是最为重要的数据结构。不过，数组的项可以直接访问，而列表的项需要按特定次序来访问。即列表（list）将一组数据表示成序列。实现这种结构的最常用方法是链表（linked list），项与项是链接起来的。链表包括多个类型：

• 单向链表（singly linked list）的每项指向它的后继，如图 1 所示：

图 1 单向链表