作为数据结构，列表、元组和数组有什么区别？

Question

这里我不是在谈论某种特定的编程语言。我想知道不同数据结构之间这些东西有什么区别。我认为列表基本上应该是可调整大小的，而数组则不是，但我不确定。

Answer 1

在不提及任何特定实现的情况下将“数组”和“列表”作为抽象数据类型进行讨论可能会有点令人困惑，因为这两者的定义不是很好。

维基百科的两个页面列表（抽象数据类型）和数组数据类型使这种歧义有些明显，其中包含诸如“列表数据结构的实现可能提供以下一些操作：”之类的不确定陈述。

在许多语言中，有一种类型叫作list和一种类型叫作array，它们有一些更好定义的含义。

这是一个非常笼统的总结。

列表：

• 列表是线性的，它是元素的有序序列；
• 您可以访问列表的第一个元素；
• 您可以将新元素添加到列表中；
• 您可以从第一个元素开始依次访问列表中的所有元素。最后一个操作可以通过“任意访问”（以 等方式访问元素l[0], l[1], l[2]）或通过称为“head”和“tail”的两个操作来完成，其中head(l)返回 的第一个元素l并tail(l)返回通过丢弃第一个元素获得的子列表。

在我看来，四个元素的列表如下所示：

-> 3 -> 7 -> 12 -> 9

数组：

• 数组使用索引提供“任意访问”（访问元素为a[something]）；
• 有时索引被限制为 0 到数组长度之间的整数；有时索引可以是任何东西；
• 您可以轻松地修改您访问的元素，但不一定要添加新元素。

在大多数语言中，允许将任何内容用作索引的数组通常称为 amap或 a dict，其中array严格指由整数索引的线性结构；但在某些语言中，例如 PHP，它仍然称为数组。

在我看来，四个元素的数组如下所示：

+--+--+--+--+
| 0| 1| 2| 3|
+--+--+--+--+
| 3| 7|12| 9|
+--+--+--+--+

元组：

• 线性、有序的元素序列；
• 通常可以包含不同类型的元素，而在大多数语言中，列表中的所有元素必须具有相同的类型；
• 通常无法添加/删除元素
• 在强类型语言中，例如 Haskell 或 OCaml，元组的类型由其长度和其中使用的类型的枚举给定，例如元组(3, 7, 12.0, "9")具有 type (int, int, float, string)，并且返回特定类型元组的函数不能突然返回返回不同类型的元组。

强类型语言中的元组有时被称为“乘积类型”，类似于数学中的笛卡尔积，与structC 中的非常接近。弱类型语言中的元组与列表非常接近。