列表 (抽象数据类型)

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

在数据结构中，也使用这个名称，表示实现出列表的数据结构，尤指链表（linked list）。

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

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

运算

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

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

特征

列表有下列属性：

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