CODEWITHSUNDEEP
c++algorithmdoubly-linked-list
Binay Dhawa
Binay Dhawa

Reputation: 71

Double linked list confused

I'm having some trouble in understanding this code. It's working just fine, however I don't understand some parts of it.

The given code is suppossed to add in files to a list. But the part that I'm confused is

fNext->fPrevious = &aNode

fNext = &aNode

The first part is assigning value to fNext->fPrevious

however isn't the second part writing value of fNext to &Node

In that case shouldn't the value in fNext->fPrevious and fNext be same.

Can someone please explain it to me. I've seen the examples but and I understand the concept of Double linked list but I dont't understand this code.

Also could someone elaborate this part as well

aNode.fPrevious = this. 

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

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

        fNext->fPrevious = &aNode;

    }

    fNext = &aNode;   
}

The constructor of DoubleLinkedNode goes like this.

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

Upvotes: 1

Views: 64

Answers (1)

abarnert
abarnert

Reputation: 365677

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

No they aren't. Yes, we do set fNext->fPrevious to &aNode. But after we set fNext to &aNode, fNext is not the node whose fPrevious we set, it's aNode. So fNext->fPrevious is aNode.fPrevious, which is this, not aNode.

Maybe it will help to give all these nodes names, and look at it graphically. Before you call append, you have something like this:

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

So, first you set aNode.fPrevious to this and aNode.fNext to fNext, so it's pointing back at this and forward at next:

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

Then you set fNext->fPrevious to &aNode. Since fNext is currently that next node, you're changing next's back-pointer to point at aNode:

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

Notice that at this point, both this and aNode think that next node is their fNext.

And finally, we fix that by setting fNext to &aNode:

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

And now aNode is properly inserted into the linked list, between this and next, and everyone agrees about everything.

Upvotes: 2

Related Questions