java - 从头开始创建 LinkedList 类

Question

我们被分配了从头开始创建 LinkedList 的任务，但绝对没有任何读数可以指导我们完成这个导致偏头痛的任务。此外，网上的一切似乎都只是使用 Java 内置的 LinkedList 方法和东西。无论如何，链表在使用 Java 的默认东西时非常有意义，但从头开始创建它是没有任何意义的。假设我有

public class LinkedList {
  private LinkedList next;  
  private final String word;
  // constructor
  public LinkedList(String word, LinkedList next) {
    this.word = word;
    this.next = next;
  }

因此神奇地我们有一个链表。到底是怎么回事？我是如何创建这样的链表的？这是如何运作的？我应该编写一个追加方法，将给定的 String word 参数添加到 this 链表的末尾。我尝试查看内置 java 链表类的 addLast 内置方法，但这对我没有帮助，因为我真的不明白发生了什么。有人愿意帮助我:)

Answer 1

如果您实际上是在构建一个真实的系统，那么是的，如果您需要的东西在那里可用，您通常只需使用标准库中的东西。也就是说，不要认为这是一个毫无意义的练习。了解事物的工作原理很好，了解链表是了解更复杂数据结构的重要一步，其中许多数据结构在标准库中不存在。

创建链接列表的方式与 Java 集合 API 的创建方式之间存在一些差异。 Collections API 试图遵循更复杂的接口(interface)。 Collections API 链表也是一个双向链表，而您正在构建一个单链表。你正在做的更适合类作业。

使用您的 LinkedList 类，实例将始终是包含至少一个元素的列表。通过这种设置，您可以在需要空列表时使用 null。

将 next 视为“列表的其余部分”。事实上，许多类似的实现使用名称“tail”而不是“next”。

这是一个包含 3 个元素的 LinkedList 的图表:

请注意，它是一个 LinkedList 对象，指向一个单词(“Hello”)和一个包含 2 个元素的列表。 2 个元素的列表有一个单词(“Stack”)和一个包含 1 个元素的列表。 1 个元素的列表有一个单词(“溢出”)和一个空列表(null)。因此，您可以将 next 视为恰好是一个元素较短的另一个列表。

您可能想要添加另一个只接受字符串的构造函数，并设置在 null 旁边。这将用于创建一个 1 元素列表。

要追加，请检查 next 是否为 null。如果是，则创建一个新的元素列表并将 next 设置为该列表。

next = new LinkedList(word);

如果 next 不是 null，则改为追加到 next。

next.append(word);

这是递归方法，代码量最少。您可以将其转换为迭代解决方案，这在 Java^* 中会更高效，并且不会冒着列表很长的堆栈溢出的风险，但我猜测不需要那种复杂程度为你的任务。

---

^{* 一些语言有尾调用消除，这是一种优化，允许语言实现将“尾调用”(作为返回前的最后一步调用另一个函数)转换为(有效地)“goto” .这使得此类代码完全避免使用堆栈，从而使其更安全(如果不使用堆栈，则不能溢出堆栈)并且通常更高效。 Scheme 可能是具有此功能的语言中最著名的示例。}