从头开始创建 LinkedList 类 [英] Creating a LinkedList class from scratch

问题描述

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

We were given an assignment to create a LinkedList from scratch, and there are absolutely no readings given to guide us on this migrane-causing task. Also everything online seems to just use Java's built in LinkedList methods and stuff. Anyway, linked lists make perfect sense when using Java's default stuff, but creating it from scratch makes no sense whatsoever. Lets say I have

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

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

And thus magically we have a linked list. What is going on? How have I created a linked list like this? How does this work? I'm supposed to write an append method that adds a the given String word parameter to the end of this linkedlist. I tried looking at the addLast built in method for built in java linkedlist class, but it's no help to me, as I really dont understand whats going on. Anyone care to help me out :)

推荐答案

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

If you're actually building a real system, then yes, you'd typically just use the stuff in the standard library if what you need is available there. That said, don't think of this as a pointless exercise. It's good to understand how things work, and understanding linked lists is an important step towards understanding more complex data structures, many of which don't exist in the standard libraries.

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

There are some differences between the way you're creating a linked list and the way the Java collections API does it. The Collections API is trying to adhere to a more complicated interface. The Collections API linked list is also a doubly linked list, while you're building a singly linked list. What you're doing is more appropriate for a class assignment.

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

With your LinkedList class, an instance will always be a list of at least one element. With this kind of setup you'd use null for when you need an empty list.

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

Think of next as being "the rest of the list". In fact, many similar implementations use the name "tail" instead of "next".

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

Here's a diagram of a LinkedList containing 3 elements:

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

Note that it's a LinkedList object pointing to a word ("Hello") and a list of 2 elements. The list of 2 elements has a word ("Stack") and a list of 1 element. That list of 1 element has a word ("Overflow") and an empty list (null). So you can treat next as just another list that happens to be one element shorter.

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

You may want to add another constructor that just takes a String, and sets next to null. This would be for creating a 1-element list.

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

To append, you check if next is null. If it is, create a new one element list and set next to that.

next = new LinkedList(word);

如果 next 不是 null，则附加到 next.

If next isn't null, then append to next instead.

next.append(word);

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

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.

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

这篇关于从头开始创建 LinkedList 类的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！