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

Question

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

- Kaiyaha

Answer 1

谈论抽象数据类型“数组”和“列表”而不涉及任何特定实现可能有点令人困惑，因为这两者并没有很好地定义。

两个维基百科页面List (abstract data type) 和 Array data type表明了这种模棱两可的情况，其中包含不确定的陈述，例如“列表数据结构的实现可能提供以下一些操作：”。

在许多语言中，存在一个称为list的类型和一个称为array的类型，并且它们具有一些更好定义的含义。

以下是非常通用的摘要。 列表：

• 列表是线性的，它是一个有序的元素序列；
• 您可以访问列表的第一个元素；
• 您可以向列表添加新元素；
• 您可以按顺序访问列表中的所有元素，从第一个元素开始。最后一个操作是使用“任意访问”（将元素访问为l[0]、l[1]、l[2]等），或者使用称为“头”和“尾”的两个操作完成的，其中head(l)返回l的第一个元素，而tail(l)返回丢弃第一个元素后获得的子列表。

在我的想象中，一个由四个元素组成的列表如下：

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

数组：

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

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

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

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

元组：

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

在强类型语言中，元组有时被称为“积类型”，类比于数学中的笛卡尔积，并且与C语言中的struct非常接近。在弱类型语言中，元组非常接近于列表。

- Stef

---

谢谢，听起来合理！那元组呢？维基百科上说它也是一个有序的元素序列。 - undefined

我为元组添加了一个小节。 - undefined

在Python中，例如列表是异构的。 - undefined

是的，在强类型语言中，列表的长度可以变化，但必须包含相同类型的元素；而元组则用于保存已知数量的不同类型的元素。在这种情况下，一个元组（int，float，string）和三个变量int，float和string之间没有太大区别，只是方便地将这三个子变量放在一个“元组”变量中。在弱类型语言中，列表可以存储不同类型的元素，而元组与列表并没有太大区别。 - undefined

Answer 2

是的，你说得对。

数组可以创建固定大小的，并且如果数组已满，则无法添加项目。

列表是动态数组，可以根据需要添加项目。在某些语言中，例如C＃，List内部使用数组。当添加新项并且数组已满时，将创建一个大小加倍的新数组。

您可以查看C#中List<T>的实现

- StepUp

---

我的意思是元组作为数据结构在结构理论中（某种程度上），而不是特定语言中的元组。维基将列表和元组看作是相同的（都是有序序列）。 - undefined

@Kaiyaha，你能给我提供元组和链接作为数据结构的链接吗？ - undefined

https://en.wikipedia.org/wiki/List_(abstract_data_type) https://en.wikipedia.org/wiki/Tuple - undefined

在某些编程语言的某些实现中，列表中使用了底层数组。这是真实的，但并不普遍适用。 - undefined

@StepUp 例如，Haskell和OCaml都使用单链表；Java允许用户明确选择ArrayList和LinkedList之间的差异；甚至C++的std::list通常被实现为双向链表。 - undefined