双链表混淆

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的节点，而是aNode。所以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 并指向 [=31] =]:

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之间，大家一致同意。

双链表混淆

Double linked list confused

c++

algorithm

doubly-linked-list