从头开始创建链接列表类

append data-structures java linked-list

2022-09-01 01:48:10

我们被赋予了从头开始创建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;
  }

因此，神奇的是，我们有一个链接列表。这是怎么回事？我如何创建这样的链表？这是如何工作的？我应该写一个追加方法，将给定的参数添加到linklist的末尾。我尝试查看java链接列表类中内置的addLast内置方法，但它对我没有帮助，因为我真的不明白发生了什么。任何人都关心帮助我:)String wordthis

答案 1

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

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

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

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

下面是包含 3 个元素的图示：LinkedList

linked list diagram

请注意，它是一个指向单词（“Hello”）的对象和 2 个元素的列表。2 个元素的列表有一个单词（“堆栈”）和一个包含 1 个元素的列表。该包含 1 个元素的列表有一个单词（“Overflow”）和一个空列表（）。因此，您可以将其视为另一个恰好是一个元素较短的列表。LinkedListnullnext

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

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

next = new LinkedList(word);

如果 next 不是，则追加到。nullnext

next.append(word);

这是递归方法，它是最少的代码量。你可以把它变成一个迭代解决方案，在Java^*中会更有效率，并且不会冒着堆栈溢出很长的列表的风险，但我猜你的任务不需要这种复杂程度。

^{*某些语言具有尾部调用消除功能，这是一种优化，允许语言实现将“尾部调用”（在返回之前的最后一步调用另一个函数）转换为（有效地）“goto”。这使得这样的代码完全避免使用堆栈，这使得它更安全（如果你不使用堆栈，你就不能溢出堆栈），并且通常更有效。Scheme可能是具有此功能的语言中最广为人知的示例。}

答案 2

你编码的不是LinkedList，至少不是我认识的。对于此作业，您需要创建两个类：

LinkNode
LinkedList

A 包含的数据有一个成员字段，以及对中下一个成员字段的引用。是的，它是一种自我参照的数据结构。A 有一个特殊引用，用于引用列表中的第一项。LinkNodeLinkNodeLinkNodeLinkedListLinkedListLinkNode

在中添加项目时，将遍历所有项目，直到到达最后一个项目。接下来应为空。然后在此处构造一个新的，设置其值，并将其添加到 .LinkedListLinkNode'sLinkNode'sLinkNodeLinkedList

public class LinkNode { 

    String data;
    LinkNode next;

    public LinkNode(String item) { 

       data = item;

    }

}

public class LinkedList { 

    LinkNode head;

    public LinkedList(String item) { 

       head = new LinkNode(item);

    }

    public void add(String item) { 

       //pseudo code: while next isn't null, walk the list
       //once you reach the end, create a new LinkNode and add the item to it.  Then
       //set the last LinkNode's next to this new LinkNode

    }


}