SLLists, Nested Classes, Sentinel Nodes

https://sp18.datastructur.es/

裸数据结构Naked Data Structure IntLists很难使用。为了正确使用 IntLists，即使对于简单的列表相关任务，程序员也必须理解并利用递归。

Adding Clothes 我们首先将 IntList 类转变为 IntNode 类。然后我们将删除IntNode类中的所有方法，接下来我们将创建一个名为 SLList 的新类，该类首先包含实例变量，并且该变量的类型应为 IntNode。本质上我们已经用 SLList 包装了我们的IntNode。

使用SLList 作为 SLList 的用户，要创建一个列表，我调用 SLList 的构造函数，并且希望填充列表的数字。然后，SLList 构造函数将使用该数字调用 IntNode 构造函数，并首先设置其指向刚创建的 IntNode。

改进 注意当创建一个有一个值的列表时，我们谢了 SLList list = new SLList(1);。我们不必担心像我们的IntList那样传递空值，本质上，SLList类充当列表用户和裸 IntList 之间的中间人。

Public vs Private 我们希望用户仅通过SLList方法修改列表，而不要直接修改first。我们可以通过变量访问权限设置为private来防止至其他用户这样做。编写 private IntNode first; 来防止其它类中的代码首先访问和修改(而该类中的代码仍然可以这么做)。

嵌套类Nested Classes 我们还可以将类移入类以创建嵌套类！您也可以将嵌套类声明为私有类。这样，其他类将永远无法使用此嵌套类。

静态嵌套类Static Nested Classes 如果 IntNode 类从不使用 SLList 类的任何变量或方法，我们可以通过添加 static 关键字将其变为静态。

递归帮助器方法Recursive Helper Methods 如果要在 SLList 中编写递归方法，我们将如何去做呢？毕竟，SLList 不是像 IntNode 这样的自然递归数据结构。一个常见的想法是编写一个用户可以调用的外部方法。此方法调用一个以 IntNode 作为参数的私有帮助器方法。然后，此辅助方法将执行递归，并将答案返回给外部方法。

缓存Caching 以前，我们通过返回 1+其余列表的大小来递归计算 IntList 的大小。如果列表很大，这将变得很慢，并且我们反复调用我们的 size 方法。现在我们有了一个 SLList，让我们简单地将列表的大小作为实例变量进行缓存！请注意，在没有 IntList 之前我们无法做到这一点。

空列表 使用一个 SLList，我们现在可以表示一个空列表。我们只需将 first 设置为 null 并将 size 设置为 0。即，因为first现在为null，所以任何尝试访问first属性的方法（例如first.item）都将返回NullPointerException。当然，我们可以通过编写处理这种特殊情况的代码来解决此错误。但是可能会有很多特殊情况。有更好的解决方案吗？

前哨节点Sentinel Nodes 使所有 SLList 对象（甚至是空列表）都相同。为此，给每个 SLList 一个前哨节点，一个始终存在的节点。实际元素位于前哨节点之后，并且我们所有的方法都应尊重哨兵始终是列表中第一个元素的想法。

不变式Invariants 不变式是关于保证是正确的数据结构的事实（假设您的代码中没有错误）。每当我们向数据结构中添加功能时，这便为我们提供了一个方便的清单。还向用户保证将保留他们信任的某些属性。例如，带有前哨节点的SLList至少具有以下不变量：

  • 前哨引用始终指向前哨节点。
  • 前项（如果存在）始终位于 sentinel.next.item。
  • size 变量始终是已添加的 items 总数。