列表、栈以及队列

数组是一个简单的数据结构，其中每个元素都能直接访问。比如说，内存就是像数组那样构建的。如果需要被数据元比一个字节大，那么就会有多个字节分配给这个数据元，然后这个数据元的地址就是“数据元编号 x 数据元大小”。但是如果存储的数据元的大小是变化的呢？并且如果要在保留剩下的数据元的情况下删除某一个数据元呢？在这样的情况下，数组就要给其他数据结构让路了。

数组之后，列表也许是计算机科学中最基础的数据结构了。尽管我们可以直接访问数组的每个元素，但在列表中，我们必须以特定的顺序访问它们。也就是说列表是数据按顺序排列的一个集合。最常见的实现这个数据结构的方法是链表linked list ---- 数据元们一个链接着另一个。链表有如下几种分类：

在 单链表singly linked list中，每个元素指向它的下一个元素，如下图：

... 在 双向链表 double linked list中，每个元素同时指向它的前一个和下一个元素，如下图：

...

在 循环链表circularly linked list中，列表中的最后一个元素指向第一个元素，而不是指向null，如下图：

...

链表可以允许不同大小的元素，并允许插入和删除元素。使用列表一个潜在的缺点是它在检索执行某一个元素时的性能是 - O(n)，也就是说，最坏的情况下，检索某个元素需要检索n次，n代表列表的大小。列表有时被内核算法直接使用。他们也频繁的被用于构建更强大的数据结构栈和队列。

栈Stack是使用后入先出（last in，first out，LIFO）的顺序来添加元素和移除元素的数据结构。也就是说最后一个被放入栈中的元素会被第一个移除。对于栈的插入和移除的操作又分别叫做push进栈和pop出栈。操作系统利用栈来调用函数。当函数调用的时候，参数、本地变量以及返回地址被push进栈内；当从这个函数调用返回时，在把之前的这些push进栈的再pop出来。

队列queue，正相反，它是以先进先出（first i, first out, FIFO）的方式排序数据元的数据结构，u也就是说在队列中的元素将被按照插入时的顺序挨个儿从队列中被移除。在我们的日常生活中有许多队列的例子，比方说，商店排队等候结帐的队伍以及排队等候交通信号灯的汽车。在操作系统中，队列也是非常常见的。比方说，发送给打印机的任务就会按照他们提交的顺序被打印，或是，在可执行的CPU上等待运行的任务就是按照队列组织的。

树

树tree是一种被用来表示数据层级的数据结构。在树结构中的数据值被表示成父和子的关系。在一棵general tree中，父节点有无数个孩子。在一棵binary tree中每个父节点最多只能有两个子节点，分别叫做left child左子节点和right child右子节点。在一棵binary search tree中，还要求在父节点的两个子节点中，左子节点 <= 右子节点，如下图：

...

当我们在一棵binary search tree中查找某一项时，最坏的性能是O(n)，为了改善这个情况，我们使用一种叫做blanced binary search tree的算法。因此，此时最坏的性能为O(lgN)。Linux使用blanced binary search tree（也叫red-black tree）来作为CPU调度算法的一部分。

哈希函数Hash function和映射maps

哈希函数Hash function是拿数据作为输入，然后通过对数据进行算数运算，再返回一个数值。这个数值可以被用作一个表（一般是数组）的索引，从而可以检索到数据。通过大小是n的链表检索一个数据的性能是O(n)，而通过使用哈希函数检索数据的性能是O(1)，当然这取决于实现细节。正是因为这样的性能，哈希函数被大量的适用于操作系统中。

哈希函数潜在的一个困难点是两个不同的输入可能会导致输出同一个值，也就说他们被关联到了表中相同的位置。我们可以通过把表的每一项化为链表在包含相同哈希值的数据，从而来解决这个hash collision哈系冲突。当然，如果冲突越多，那么哈希函数的效率也就越低。

一种使用哈希函数的实现的功能叫做哈希映射hash map，通过哈希函数关联或映射一对键值。一旦映射创建完毕，我们可以通过键的哈希函数从哈希映射中获得值。如下图：