列表 (抽象数据类型)

计算机科学中,列表(英语:list)或序列sequence),是一种抽象数据类型,一种有限的有序的集合,其中每个值可以出现多次。列表的一个实例是在计算机中用来表现出数学上有限序列的概念;列表的无限类似是。列表是容器的一个基本例子,因为它们包含其他值。在列表中的每个值(value),称为项目(item)、条目(entry)或元素(element);如果相同的值出现多次,每一次出现都认为是分立的一个项目。列表和数组区别在列表只允许顺序访问,而数组允许随机访问。

数据结构中,也使用这个名称,表示实现出列表的数据结构,尤指链表(linked list)。

所谓静态列表结构只允许对值的审查和枚举。一个可变对象或动态列表在其生存周期内允许条目被插入、替换或删除。

许多编程语言支持列表数据类型,针对列表和列表运算有特定的语法和逻辑。通常可以通过写入序列中的元素来建立列表。元素用逗号、分号或空格分开,位于一对括号(如圆括号 '()', 方括号, '[]', 花括号 '{}', 以及尖括号 '<>')内部。

运算

编辑

实现列表数据结构可以提供以下一些运算:

  • 一个生成空列表的构造函数
  • 用于测试列表是否为空的运算;
  • 向列表前端加入元素的运算;
  • 向列表末端入元素的运算;
  • 确定列表头元素的运算;
  • 用于引用除首项外所有部分的列表(这被称为列表的“尾部”。);
  • 销毁列表析构函数

特征

编辑

列表有下列属性:

  • 列表大小. 它表明列表中有多少元素。
  • 列表相等:
    • 在数学里,有时列表相等定义为: 两个列表是相等的当且仅当它们是相同的对象。
    • 在现代编程语言中, 列表相等一般定义为相应条目结构上相等,要是列表具有类型,那么与列表类型也有关联。
  • 列表会具有类型。这表明列表中的条目必须有与列表类型兼容的类型。当列表由数组实现的时候常常会具有类型。
  • 列表中每个元素有一个标号。首元素一般标号为0或1(或其他一些预定义的整数)。后面的元素的标号比前一个大1。 尾元素的标号为<首标号> + <size> − 1。
    • 可以检索特定标号(index)的元素。
    • 可以按照标号增加的顺序遍历列表。
    • 可以改变特定标号的元素的值,同时不影响其他元素。
    • 可以向特定标号插入一个元素。后面的元素标号增加1。
    • 可以在特定标号删除一个元素。后面的元素标号减少1。
  • 列表的“头”“尾”、“前”“后”
    • 列表的“头”(head),是指指向列表的第一个元素的指针或结点;因此,列表的“尾”(tail),是指遍历列表到达的最后一个元素。
    • 前向列表(forward list,如C++标准模板库的实现 )是指一个单向列表,从头部开始,每个节点有一个next指针指向紧邻的下一个节点。这与常识中的从“头”至“尾”是“向后”的理解,恰恰相反。