DLLists, Arrays

https://sp18.datastructur.es/

SLList的缺点 addLast() 方法非常慢！我们无法添加到列表的中间。另外，如果我们的列表很大，那么我们必须从最前面开始，并一直循环到列表的最后，然后再添加元素。

一个Naive的解决方法 回想一下，我们将列表的大小作为SLList的实例变量进行了缓存。如果我们也缓存列表中的最后一个元素怎么办？突然之间，addLast() 又很快了。我们立即访问最后一个元素，然后添加我们的元素。但是 removeLast() 仍然很慢。在 removeLast() 中，我们必须知道second-to-last 变量是什么，因此我们可以将缓存的 last 变量指向该变量。然后，我们可以缓存 second-to-last，但是现在，如果我想删除倒数第二个元素，则需要知道倒数第二个元素在哪里。如何解决这个问题呢？

DLList 解决方案是为每个 IntNode 提供一个 prev 指针，指向上一个项目。这将创建一个双向链表或 DLList。通过此修改，从列表的前面和后面添加和删除变得很快（尽管从中间添加/删除仍然很慢）。

结合Sentinel 回想一下，我们在 SLList 中添加了一个哨兵节点。对于 DLList，我们可以有两个哨兵（一个为前哨，一个为后哨），也可以使用圆形哨兵。使用圆形标记的 DLList 具有一个哨兵。哨兵通过next指针指向列表的第一个元素并且用 prev 指针指向最后一个元素。此外，列表最后一个元素的 next 指向哨兵，列表中第一个元素的 prev 指向哨兵。对于空列表，哨兵两个方向指向自身。

泛型双向链表Generic DLList 我们如何修改 DLList，以便它可以是我们选择的任何对象的列表？回想一下我们的类定义如下：

public class DLList { ... }

将其变为：

public class DLList<T> { ... }

其中 T 是占位符对象类型。 注意尖括号语法。 另请注意，我们不必使用 T； 任何变量名都可以。 在 DLList 中，我们的项目现在为 T 类型，并且我们的方法现在将 T 类型实例作为参数。 为了准确性，我们还可以将 IntNode 类重命名为 TNode。

使用泛型双向链表 回想创建一个 DLList，我们输入：

DLList list = new DLList(10);

如果我们想创建一个支持 String 对象得 DLList，我们必须说：

DLList<String> list = new DLList<>("bone");

创建列表时，编译器将 T 的所有实例替换为 String！ 我们将在以后的课程中更详细地介绍通用类型。

数组 回想一下变量只是位盒。例如，int x; 创建了一个32位的存储盒。数组是一个特殊的对象，它由编号顺序的存储盒组成！要获得数组A的第i个项，请使用 A[i]。 数组的长度不能更改，并且数组的所有元素必须具有相同的类型（这与Python列表不同）。 这些框的索引为零，这意味着对于具有N个元素的列表，第一个元素位于 A[0]，最后一个元素位于 A[N-1]。 与常规类不同，数组没有方法！ 数组确实有一个 length 变量。

数组实例化 创建数组有三种有效的表示。 第一种方法指定数组的大小，并使用默认值填充数组：

int[] y = new int[3];

第二种和第三种方法向数组填充特定的值：

int[] x = new int[]{1, 2, 3, 4, 5};
int[] w = {1, 2, 3, 4, 5};

我们可以使用数组索引在数组中设置一个值。 例如，我们可以说 A[3] = 4;。 这将访问数组A的第四个元素，并将该框的值设置为4。

Arraycopy 为了复制数组，我们可以使用 System.arraycopy。 它有5个参数； 语法很难记住，因此我们建议使用诸如此类的各种在线参考。

二维数组 我们可以声明多维数组，对于二维数组，我们可用以下语法：

int[][] array = new int[4][];

这创建了一个包含整型数组的数组，注意我们必须手动的创建内层数组如下：

array[0] = new int[]{0, 1, 2, 3};

Java还可以使用自动创建的内部数组来创建多维数组。 为此，请使用以下语法：

int[][] array = new int[4][4];

我们也可以使用这种方式：

int[][] array = new int[][]{{1}, {1, 2}, {1, 2, 3}}

来得到具有具体数值的数组。

Arrays vs. Classes

  • 两者都用于组织一堆内存。
  • 两者都有固定数量的“盒子”。
  • 通过方括号符号访问数组。 通过点表示法访问类。
  • 数组中的元素必须全部为同一类型。 类中的元素可以是不同的类型。
  • 数组索引是在运行时计算的。 我们无法计算类成员变量名称。