从头开始创建 LinkedList 类

我们的任务是从头开始创建一个 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 linkedlist 类的 addLast 内置方法，但这对我没有帮助，因为我真的不明白发生了什么。任何人都愿意帮助我:)

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

创建链接列表的方式与 Java 集合 API 的方式之间存在一些差异。 Collections API 试图遵循更复杂的接口。当您构建单链表时，Collections API 链表也是双向链表。你正在做的事情更适合课堂作业。

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

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

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

请注意，这是一个LinkedList指向一个单词（“Hello”）的对象和一个包含 2 个元素的列表。 2 个元素的列表有一个单词（“Stack”）和 1 个元素的列表。该 1 个元素的列表有一个单词（“溢出”）和一个空列表（null）。所以你可以治疗next就像另一个列表，恰好短了一个元素。

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

要附加，您检查是否next is null。如果是，则创建一个新的单元素列表并设置next对此。

next = new LinkedList(word);

如果下一个不是null，然后附加到next反而。

next.append(word);

This is the recursive approach, which is the least amount of code. You can turn that into an iterative solution which would be more efficient in Java^*, and wouldn't risk a stack overflow with very long lists, but I'm guessing that level of complexity isn't needed for your assignment.

^{* Some languages have tail call elimination, which is an optimization that lets the language implementation convert "tail calls" (a call to another function as the very last step before returning) into (effectively) a "goto". This makes such code completely avoid using the stack, which makes it safer (you can't overflow the stack if you don't use the stack) and typically more efficient. Scheme is probably the most well known example of a language with this feature.}