c++ - 双链表混淆

Question

我在理解这段代码时遇到了一些困难。它工作得很好，但我不明白它的某些部分。

给定的代码应该将文件添加到列表中。 但我感到困惑的部分是

fNext->fPrevious = &aNode

fNext = &aNode

第一部分是给fNext->fPrevious赋值

但是第二部分不是将 fNext 的值写入 &Node

在那种情况下，fNext->fPrevious 和 fNext 中的值不应该相同。

谁能给我解释一下。我看过示例，但我理解双链表的概念，但我不理解这段代码。

也有人可以详细说明这部分

aNode.fPrevious = 这个。

 void DoublyLinkedNode<DataType>::append(Node& aNode)
{
    aNode.fPrevious = this;

    if (fNext != &NIL)
    {
        aNode.fNext = fNext;

        fNext->fPrevious = &aNode;

    }

    fNext = &aNode;   
}

DoubleLinkedNode 的构造函数是这样的。

template<class DataType>
DoublyLinkedNode<DataType>::DoublyLinkedNode(const DataType& aValue)
{
    fValue = aValue;
    fPrevious = &NIL;
    fNext = &NIL;
}

Answer 1

what I am currently confused about is the difference in between fNext->fPrevious and fNext. Both are pointing towards the same thing.

不，他们不是。是的，我们将 fNext->fPrevious 设置为 &aNode。但是当我们将fNext设置为&aNode后，fNext并不是我们设置的fPrevious的节点，而是一个节点。所以fNext->fPrevious是aNode.fPrevious，也就是this，不是aNode。

也许给所有这些节点命名并以图形方式查看它会有所帮助。在你调用 append 之前，你有这样的东西:

prev      this          next                   aNode
...   <-- fPrevious <-- fPrevious      NIL <-- fPrevious
fNext --> fNext     --> ...                    fNext     --> NIL

因此，首先将 aNode.fPrevious 设置为 this 并将 aNode.fNext 设置为 fNext，因此它是指向 this 并指向 next:

prev      this          next                   aNode
...   <-- fPrevious <-- fPrevious     this <-- fPrevious
fNext --> fNext     --> ...                    fNext     --> next

然后将fNext->fPrevious设置为&aNode。由于 fNext 当前是 next 节点，您正在更改 next 的后向指针以指向 aNode :

prev      this          aNode         next
...   <-- fPrevious <-- fPrevious <-- fPrevious
fNext --> fNext \       fNext     --> ...
                 -------------------/

请注意，此时 this 和 aNode 都认为 next 节点是它们的 fNext。

最后，我们通过将 fNext 设置为 &aNode 来解决这个问题:

prev      this          aNode         next
...   <-- fPrevious <-- fPrevious <-- fPrevious
fNext --> fNext     --> fNext     --> ...

现在 aNode 被正确地插入到链表中，在 this 和 next 之间，并且每个人都同意所有事情。