接下来我们新建一个 DLList。这个链表相对于之前的 SLList 多了一些特点和改进：

1. 支持双向递归
2. 支持泛型

改进七：倒过来

给 IntNode 改成三个域，一个存整数，还有两个分布存向前和向后的指针：

public class IntNode {
    public IntNode prev;
    public int item;
    public IntNode next;
}

这样就可以实现双向循环了。在中文社区里面这种链表叫 双向链表

改进八：双哨兵

还记得在 SLList 中的哨兵吗？这是在链表的开头加上了一个“无用”的 IntNode，来防止空链表造成的特殊化处理。现在 DLList 改成了双向链表，当链表为空的时候（也就是只有一个哨兵节点），进行 removeLast 操作会导致 prev 指针指向空节点。解决方法也很简单：在链表尾部也加上一个哨兵，这样形成了双哨兵，向前向后遍历都不会遇到空链表带来的问题了。

改进九：泛型

想一想，从 SLList 到 DLList，我们的元素从 String 变成了 int。假如说我们加下来要存放 Dog，Cat 等其他种类，那不是又要对这个类进行重载？那太麻烦了。为了减小代码的重复，泛型就很又用了。它可以根据需要，改变类中元素的类型，你需要做的，只是在尖括号中写下类型的名字。

public class DLList<BleepBlorp> {
    private IntNode sentinel;
    private int size;

    public class IntNode {
        public IntNode prev;
        public BleepBlorp item;
        public IntNode next;
        ...
    }
    ...
}

Array

数组和链表的区别

接下来让我讲一下数组。数组和链表有很大的区别：

1. 数组只需要一个 box，每个元素在内存中是连续的；链表需要很多 box，在内存中不一定是连续的。
2. 数组的元素必须是一样的；链表不一定是一样的。
3. 数组通过 [] 来访问元素；链表通过 . 来访问元素。

数组的创建和使用

int[] z = null;
int[] x, y;

// 定义并初始化
x = new int[]{1, 2, 3, 4, 5};
y = x;
x = new int[]{-1, 2, 5, 4, 99};
y = new int[3];
z = new int[0];
int xL = x.length;

String[] s = new String[6];
s[4] = "ketchup";
s[x[3] - x[1]] = "muffins";

int[] b = {9, 10, 11};
System.arraycopy(b, 0, x, 3, 2);

x 就相当于一个引用，指向了数组的首个元素的地址，我们通过 x[i] 访问，实际上是在首地址的基础上加上 i 个元素的大小，来访问第 i 个元素的值。同时由于是一个引用，因此 y = x 实际上复制的是一个引用而不是完整的数组，如果要复制完整的数组，需要用 arraycopy 这个方法。这个方法有点类似于 python 中的切片。

二维数组

二维数组的本质是，创建了一个存放引用的数组。pascalsTriangle = new int[4][]; 实际创建了一个引用 pascalsTriangle ，指向一个大小为 4 的数组，数组里存放的都是 null；然后接下来的语句就是给给 null 重新赋值，指向新其他的整数数组。

int[][] pascalsTriangle;
pascalsTriangle = new int[4][];
int[] rowZero = pascalsTriangle[0];

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