双向链表实现

Question

我已经看了这里关于双向链表的大多数帖子，但仍然不清楚下面的内容。

我正在用Java练习Goodrich和Tamassia这本书。关于双向链表，如果我错了，请纠正我，它与单链表的不同之处在于，节点可以插入到任何地方，而不仅仅是在头部之后或尾部之后，使用next和prev节点，而在单链表中，在列表中的任何地方插入都是不可能的？

如果要在双向链表中插入节点，则默认参数应该是要插入的节点之后的节点或要插入的节点之前的节点？但如果是这样，那么我不知道如何在之前或之后传递节点。我们是否应该显示到目前为止已插入的所有节点，并要求用户选择要插入某个新节点之前或之后的节点？我的疑问是如何传递这个默认节点。因为我假设这也需要这些节点的next和prev节点。

例如，Head<->A<->B<->C<->D<->E<->tail

如果Z是在D之后插入的新节点，那么节点D应该如何传递？我对此感到困惑，尽管它对大多数人来说似乎很简单。

但是我会解释的。

谢谢，Sanjay

Answer 1

它与单链表的不同之处在于，使用next和prev节点，节点可以插入到任何地方，而不仅仅是在头部或尾部之后，而在单链表中，这种插入列表中的任何地方都是不可能的。

这是错误的。你可以在单链表的中间插入节点。唯一的区别是双向链表更容易导航，因为您可以从任何给定的节点向前和向后遍历它。

如果要在双向链表中插入节点，则默认参数应该是要插入的节点之后的节点或要插入的节点之前的节点？

这完全取决于您使用列表的目的。链表并不是真正好的通用数据结构，因为它们的随机访问性能很差。因此，它们通常只用于遍历列表并在执行时插入或删除节点的算法。

但如果是这样的话，我就不知道如何在之前或之后传递节点了。，

。我们是否应该显示到目前为止已插入的所有节点，并要求用户选择要插入某个新节点之前或之后的节点？

您正在以错误的方式处理此问题，试图围绕特定的数据结构编写应用程序。通常，您从应用程序的最终用户需求开始，然后决定哪种数据结构最适合满足这些需求。用户永远不需要了解程序的低级内部结构，比如链表。

Answer 2

假设Node类如下所示：

public class Node {
    public Node next = null;
    public Node previous = null;
    public Object value;
}

然后，您可以定义：

public void insertBefore(Node node, Node insert)
{
    Node previousNode = node.previous;

    insert.next = node;
    insert.previous = previousNode;

    if(previousNode != null)
        previousNode.next = insert;

    node.previous = insert;
}

和

public void insertAfter(Node node, Node insert)
{
    Node nextNode = node.next;

    insert.previous = node;
    insert.next = nextNode;

    if(nextNode!= null)
        nextNode.previous = insert;

    node.next = insert;
}

希望这能有所帮助

Answer 3

1. 您也可以在单个链表中插入。A->B变为A->C->B，您所要做的就是更改A的下一个节点引用，并将C的下一个节点设置为B。
2. 默认情况下，在所选节点之后插入会更有意义。
3. 您将D的下一个节点设置为Z，E的上一个节点设置为Z，Z的下一个节点设置为E，Z的上一个节点设置为D。

我希望我没弄错你的问题，它们有点令人困惑。