3.22.有序列表抽象数据结构

我们现在将考虑一种称为有序列表的列表类型。例如，如果上面所示的整数列表是有序列表（升序），则它可以写为17,26,31,54,77和93。由于 17 是最小项，它占据第一位置。同样，由于 93 是最大的，它占据最后的位置。

有序列表的结构是项的集合，其中每个项保存基于项的一些潜在特性的相对位置。排序通常是升序或降序，并且我们假设列表项具有已经定义的有意义的比较运算。许多有序列表操作与无序列表的操作相同。

• OrderedList() 创建一个新的空列表。它不需要参数，并返回一个空列表。

• add(item) 向列表中添加一个新项。它需要 item 作为参数，并不返回任何内容。假定该 item 不在列表中。

• remove(item) 从列表中删除该项。它需要 item 作为参数并修改列表。假设项存在于列表中。

• search(item) 搜索列表中的项目。它需要 item 作为参数，并返回一个布尔值。

• isEmpty() 检查列表是否为空。它不需要参数，并返回布尔值。

• size（）返回列表中的项数。它不需要参数，并返回一个整数。

• index(item) 返回项在列表中的位置。它需要 item 作为参数并返回索引。假定该项在列表中。

• pop() 删除并返回列表中的最后一个项。假设该列表至少有一个项。

• pop(pos) 删除并返回位置 pos 处的项。它需要 pos 作为参数并返回项。假定该项在列表中。