Java 排序双向链表

Question

我在这里遇到了一个问题，实现名字和姓氏的排序双向链接列表。

向每个链接添加一个字段，指示按字母顺序排列的下一个名字；现有的下一个链接用于指示按字母顺序排列的下一个姓氏。您还需要该列表的第二个根链接 - 现有的根链接指示按字母顺序排列的第一个姓氏，并且您将需要一个指示按字母顺序排列的第一个名字的根链接。请注意，对于列表中输入的每个名称，您仍然只有一个链接对象。

完成此操作后，对插入、查找和删除方法进行必要的更改，以便维护两个交错列表。还要根据需要更新运行时间估计以保持准确。

最后，添加第二个查找方法，该方法接受名字并返回包括该名字的所有全名，以及第二个显示方法，按名字的字母顺序打印姓名列表。确保您也给出了这些方法的运行时间估计。

我完全不知道如何做到这一点。我已经创建了一个带有名字和姓氏的链接列表，但这只是我所能得到的。

任何帮助都会很棒：D

谢谢。

Answer 1

1. 创建一个具有两个链接字段（nextFirstName、nextLastName）和一个名称对象字段的链接类。
2. 插入时，首先搜索位于该新对象 (LastName) 之前的 Link 对象，然后使用 nextLastName 字段将其插入到该对象之后。然后使用 nextFirstName 字段作为链接，对 FirstName 执行相同的操作。
3. ????
4. 利润！

这确实很像家庭作业:)

Answer 2

因为您已经实现了单链表，所以扩展到双向链表应该不会太困难。您已经有了后续的参考资料（见下图）。现在您还需要添加向后引用。另外，请注意下图中的蓝色线条。添加拼写属性的附加参考。因此每个节点都将具有变量：

private Node NextFirstName;
private Node PreviousFirstName;
private Node NextLastName;
private Node PreviousLastName;

Answer 3

您不需要向后引用！该任务需要类似 2 个单链表的东西，它们使用相同的对象作为条目。每个对象都有两个链接：一个链接到列表 A 中的下一项，一个链接到列表 B 中的下一项。