将单向链表转换为双向链表

Question

首先，我已经搜索过了，但我似乎找不到任何可以帮助我更好地理解实现双向链表的东西。我还要说，这也是我的一项任务，我不期望有人只为我做这件事。如上所述，我有一个单链表(线性)的工作代码，它可以添加、删除、获取大小、清除、etc...and，我想在这段代码中实现双向链表实现。

据我所知，这应该是相当直接的。然而，我的书并没有对此进行太多的详细介绍，并且只提供了很少的示例。我很难想象如何实现这一点。我意识到在单链表中，前一个节点只指向下一个节点，要求您在任何时候想要删除或添加任何内容时都要遍历整个列表。在双向链表中，它应该从最接近正在处理的节点的末端开始遍历。如果我的理解不正确，请纠正我。

这是我到目前为止修改过的代码片段。

private class Node
{
    private T data;
    private Node next;
    private Node previous;



    private Node(T dataPortion)
    {
        this(dataPortion, null, null);
    }

    private Node(T dataPortion, Node nextNode, Node prevNode)
    {
        data = dataPortion;
        next = nextNode;
        previous = prevNode;

    }

我添加了"private Node previous“作为对列表中前一个节点的引用，并按照代码中的前一个格式将其设置为等于prevNode。在进入各个方法之前，在初始设置中还需要做什么吗？

在我的每个方法中，我都不确定现在需要做什么才能使用它来引用前一个节点和下一个节点，就像它现在做的那样。有没有人可以帮我解决这个问题，可能会提供一些示例代码？下面是当前的add方法以供参考。

public boolean add(T newEntry)
{
    Node newNode = new Node(newEntry);

    if (isEmpty())
        firstNode = newNode;
    else
    {
        Node lastNode = getNodeAt(numberOfEntries);
        lastNode.setNextNode(newNode);
    }

    numberOfEntries++;

    return true;
}

Edit:新增上一个Node的set和get方法。

private Node getNextNode()
    {
        return next;
    }

    private Node getPrevNode()
    {
        return previous;
    }

    private void setNextNode(Node nextNode)
    {
        next = nextNode;
    }
    private void setPrevNode(Node prevNode)
    {
        previous = prevNode;
    }

这是我应该添加的内容吗？

public boolean add(T newEntry)
{
    Node newNode = new Node(newEntry);


    if (isEmpty())
        firstNode = newNode;
    else
    {
        Node lastNode = getNodeAt(numberOfEntries);
        Node prevNode = getNodeAt(numberOfEntries -1);
        lastNode.setNextNode(newNode);
        newNode.setPrevNode(prevNode);
    }

    numberOfEntries++;

    return true;
}

Answer 1

你做的都是对的。您需要做的就是添加newNode.setPreviousNode(lastNode)

你可以看看LinkedList作为参考。它们在列表中存储了引用first和last的两个节点。使用这种方法，您可以不使用getNodeAt函数遍历add方法中的所有列表。

LinkedList中add方法的实现

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

Answer 2

public boolean add(T newEntry)
{
    Node newNode = new Node(newEntry);
    newNode.previous = this;
    newNode.next = next;
    next = newNode;
    numberOfEntries++;
    return true;
}

最重要的是，您不需要知道数据结构的其余部分在做什么。您甚至不需要知道还有其他节点。您只需告诉节点添加此节点并更新链接即可。或者通过删除对此节点的引用来删除此节点。

public void remove() {
     if (next != null) next.previous = previous;
     if (previous != null) previous.next = next;
     numberofEntries--;
}