Java和Python的数据结构及其实现：列表、数组、元组

Question

我知道Java，也最近开始学习Python。在某个时候，我意识到我需要停下来，弄清楚与数据结构相关的所有问题，特别是列表、数组和元组。请你帮我纠正一下我以下的理解，如果我有错的话：

• 根据数据结构的标准，列表最开始是不支持任何索引的。获取元素的唯一方法是通过迭代（也就是用下一个方法）。
• 在Java中，确实有一种通过索引访问元素的方法（比如get(index)方法），但即使你使用这些与索引相关的方法，实际上还是从第一个元素开始迭代（更具体地说，是从它的引用开始）。
• 在Python中，我们可以用类似于Java数组的方式访问列表元素，使用list[index]的语法，但实际上，尽管这个数据类型叫“列表”，在后台我们确实有一个引用数组，当我们引用第三个元素时，比如说，我们是直接引用数组中的第三个元素，而不是从第一个元素开始迭代（我觉得我在这里可能理解错了）。
• 元组在Python中的实现方式和列表是一样的。唯一的区别是元组是不可变的。但它仍然更接近于列表而不是数组，因为元素在内存中并不是连续存放的。
• 在Python中没有像数组那样的东西。
• 在数据结构理论中，当我们创建一个数组时，它只使用对内存第一个单元的引用，然后迭代到我们指定的索引元素。列表和数组之间的主要区别是，所有元素在内存中是连续存放的，这就是为什么在性能方面我们会有优势。

我觉得我在某些地方可能理解错了。请你帮我纠正一下好吗？谢谢！

Answer 1

大部分内容都是错误的。

• 列表抽象数据类型是一种有序的元素序列，可以包含重复的元素。实现这种数据类型的方法有很多，特别是可以用链表来实现，但大多数编程语言使用的是动态调整大小的数组。
• 即使是链表也可以支持索引。虽然实现方式不能直接跳到第n个元素，但它可以通过链接一步步到达。
• Java的List类型并没有指定具体的实现方式，而只是定义了一个接口。ArrayList是用动态数组实现的List；而LinkedList就是字面意思的链表。
• Python的列表是用动态调整大小的数组实现的，而Python的元组则是用固定大小的数组实现的。
• 实际上，Python中有两种常被称为数组的类型，不包括新手常用“数组”来指代Python列表的情况。有一种是由array模块提供的数组，还有一种是NumPy的ndarray。
• 当你索引一个数组时，实际的实现并不是从第一个元素的位置开始逐个遍历到第n个元素。它是通过在数组地址上加一个偏移量，直接跳到那个元素，而不是逐个遍历。