Ruby数组是什么数据结构？

Question

我正在学习计算机科学课程中的数组和链表。我的教授说，数组不能在末尾添加或删除元素，因此我们使用链表。

我知道Python、Ruby和JavaScript中的数组实现允许我随意修改数组的长度。这些语言是否真的实现了链表或其他数据结构，并将其称为数组？

底层发生了什么？如果它不是真正的数组，为什么他们还要这样称呼它？

- chopper draw lion4

---

你可以查看所有这些数组实现的代码。你也应该注意像“任意修改数组长度”这样的语句--仅仅因为你可以使一个数组更长，并不意味着在这样做时你没有产生内存拷贝的开销。 - Dave Newton

在像Ruby和Python这样的高级语言中，实际上没有使用链表的必要，因为没有比内置数组类型更有效的实现方式。您的教授主要将数组/链表比较应用于C语言。 - Martijn

Answer 1

如果固定大小的数组已满，则无法向其末尾添加元素，但移除元素是可以的。这就是栈工作的原理。

在内部，Ruby数组被分配为固定大小的C-style数组，并在添加元素时自动调整大小。为了优化，它们通常会被重新调整到比所需空间稍大一点，以避免在每次添加时重新分配。

链表是一种不同的数据结构，允许更灵活的插入和删除，但遍历速度较慢，并且不允许轻松随机访问，这些对于数组结构非常重要。

- tadman

---

很好。我知道JS和Python也是C的衍生物。它们是否也使用C风格的数组？ - chopper draw lion4

它们不是C的派生物，但标准的Ruby、Python和JavaScript V8核心是用C编写的。它们只是惯例，在内部使用C风格的数组，但每个语言在如何使用这些数组方面有不同的方法。 - tadman

Answer 2

快速浏览Ruby数组实现的源代码，它是一个C数组，只是一个内存块。但正如您在代码中看到的，它还提供了通过更新此内存块或重新分配来添加和删除的函数，使您可以方便地修改Ruby数组，就像它是动态的一样。请参考：https://github.com/ruby/ruby/blob/master/array.c

- Chong Yu