1. 章节引言：线性表¶

如果你的程序需要存储少量东西—例如数字、工资记录或职位描述—最简单也最有效的做法也许就是把它们放进一个列表。 只有当你必须组织和查找大量东西时，才需要像 查找树 这样更复杂的数据结构。 许多应用不需要任何形式的查找，也不要求对所存储的对象施加某种排序。 有些应用要求按严格的时间顺序执行操作， 即按对象到达的顺序处理它们，或者也许按到达顺序的逆序处理它们。 对于所有这些情形，简单的列表结构都是合适的。

本章既描述线性表的表示，也描述两种重要的类线性表结构，称为 栈 和 队列 。 除了介绍这些基本数据结构外，本章的其他目标还有：

1. 给出示例，展示以 ADT 形式呈现的逻辑表示与作为数据结构的物理实现之间的分离。

2. 说明渐近分析在你可能已经熟悉的简单操作语境中的应用。 这样，你就可以开始理解渐近分析是如何工作的，而不必面对分析更复杂算法和数据结构时出现的种种复杂情况。

我们首先定义 ADT for lists 。 线性表 ADT 的两种实现—即 array-based list 和 linked list—将被详细讨论， 并比较它们各自的优缺点。 本章最后给出 stacks 和 queues 的实现。