程序员学数据结构

第3章　列表：线性数据集

上一章介绍了数组数据结构，它是本书后续研究的一系列数据结构的基础。虽然数组在处理静态数据集时性能较好，但代码示例说明了数组在很多应用情景下并不是那么灵活和高效——以至于从数据集中增加或删除元素的简单操作都会非常复杂且耗费资源。

从某种程度上看，列表是一种改良的数组。列表可定义为有限的、由称为元素的对象或数值构成的有序序列。空列表即没有任何元素的列表。列表的长度为该数据集中所有元素的总个数。列表中的第一项称为表头（head），最后一项称为表尾（tail）。在长度为1的列表中，其头和尾为同一个对象。

数组是一种具体的数据结构，而列表是数据结构的一种抽象概念，许多编程语言都对这种抽象概念提供了具体实现。本章的后续部分将会使用一个Java示例来更详细地说明这种区别。

顺序表（ordered list）不应与排序表（sorted list）相混淆，这是因为列表可以是已排序的，也可以是未排序的。顺序表指的是列表中的每个元素位置都经过了定义。已排序表中的对象之间都有一定关系，而未排序表中的对象之间没有明确的关系。例如，当我妻子在列购物清单时，她会根据超市里的布局来认真组织需要购买的商品。她在购物清单上列明了多种不同的商品，并根据这些货物在超市中的相对位置进行组合，这些货物之间的关系即空间关系（spatial relationship）。这便是一个已排序表。另一方面，我发现家里有些东西没有了，便找了张纸，随便列了一个购物清单。虽然我的购物清单上也有很多种类的货物，但这些项目并没有以任何特定方式加以组织，因此它们相互之间没有明确的关系。我的这张购物清单便是未排序表。 ...