ALists, Resizing, vs. SLists

https://sp18.datastructur.es/

列表与数组 我们的 DLList 有一个缺点。获得第i个项目很慢；我们必须从头到尾扫描列表中的每个项目，直到到达第 i 个项目为止。但是，对于名为 A 的数组，我们可以使用方括号表示法 A[i] 快速访问第i个项目。因此，我们的目标是实现带有数组的列表。

AList AList 将具有与 DLList 相同的API，这意味着它将具有与 DLList 相同的方法(addLast(), getLast(), removeLast(), and get(int i))。 AList也将具有一个跟踪其大小的大小变量。

AList不变式 AList有一些不变式。

  • addLast：我们要添加的下一个项目将进入 size 位置。
  • getLast：我们要返回的项目位置为 size-1。
  • size：列表中的项目数应为 size。

实现AList 每个 AList 都有一个int[] 叫做 item。

  • 对于addLast，我们将项目放置在 items[size]中。
  • 对于getLast，我们只返回 items[size-1]。
  • 对于removeLast，我们只是减小 size（我们不需要更改 items）。因此，如果调用 addLast，则由于 size 减小了，因此只会覆盖旧值。但是，最好将对象删除后将其清空，因为这样可以节省内存。注意这些方法与不变量有多紧密的联系。

抽象 本课程的一个关键思想是可以将实现细节隐藏在用户面前。例如，用户可能想使用列表，但是作为实现者，我们可以为他们提供列表的任何实现，只要该列表符合其规范即可。用户不应该了解我们列表的内部工作原理。

调整数组大小Array Resizing 当数组满时，我们可以调整数组大小。但是，我们了解到数组大小无法更改。相反，解决方案是创建一个更大的新数组，然后将我们的旧数组值复制到新数组中。现在，我们拥有所有旧值，但是我们有更多空间来添加项目。

调整速度Resizing Speed 在讲座视频中，每次达到数组大小限制时，我们便开始将数组调整大小再增加一个额外框。事实证明这非常慢，因为将数组复制到新数组意味着我们必须对每个项目执行复制操作。最糟糕的部分是，由于我们仅调整了一个额外的框的大小，因此，如果我们选择添加另一项，则每次添加到数组时都必须再次执行此操作。

提高Resizing性能 而不是添加一个额外的框，我们可以创建一个新数组，其大小为 size * FACTOR项，其中 FACTOR 可以是任何数字，例如2。我们将在本课程的稍后部分讨论为什么这样做很快。

减小数组大小 如果我们拥有一百万个长度的数组，但是我们删除了990,000个元素，该怎么办？好吧，类似地，例如，如果我们达到250,000个元素，则可以通过创建一半大小的数组来缩小数组的大小。同样，我们将在本课程的后面部分对此进行更严格的讨论。

另外：分解代码 有时，我们编写大型方法来完成多项任务。更好的方法是将我们的大型方法分解为许多较小的方法。这样的好处之一是我们可以分部分地测试我们的代码。

泛型AList 上一次，我们讨论了如何制作泛型 DLList。 我们可以为 AList 做类似的事情。 但是我们发现我们在创建数组时出错了。 我们的问题是Java中不允许使用通用数组。 相反，我们将更改以下行：

items = new Item[100];

改为：

items = (Item[]) new Object[100];

这叫做 cast，我们将在以后学习。