CODEWITHSUNDEEP
c++c++11linked-list
TosinAl
TosinAl

Reputation: 166

Confusion on Linked Lists

I read this code written in the programming principles and practice using c++ book.

struct Link {
string value;
Link* prev;
Link* succ;
Link(const string& v, Link* p = nullptr, Link* s = nullptr)
: value{v}, prev{p}, succ{s} { }
};

I like his approach to teaching starting from an empty shell and working his way up(By his/he i mean the author of the book). So on his first attempt at building a list(of Norse gods ), he did this: 

Link* norse_gods = new Link{"Thor",nullptr,nullptr};
norse_gods = new Link{"Odin",nullptr,norse_gods};
norse_gods–>succ–>prev = norse_gods;
norse_gods = new Link{"Freia",nullptr,norse_gods};
norse_gods–>succ–>prev = norse_gods;

The confusion I have is on the fact that he had to explicitly state this:

norse_gods–>succ–>prev = norse_gods;

as seen on the third and fifth lines.

I was thinking adding items without explicitly stating that line of code in between each addition will also work. i.e:

Link* norse_gods = new Link{"Thor",nullptr,nullptr};
norse_gods = new Link{"Odin",nullptr,norse_gods};
norse_gods = new Link{"Freia",nullptr,norse_gods};

Is my state of thinking wrong? And why does that line( norse_gods–>succ–>prev = norse_gods;) have to be explicitly added to the code

Upvotes: 3

Views: 203

Answers (1)

Garrett Gutierrez
Garrett Gutierrez

Reputation: 767

Let us say that A <--> B says A->succ == B and B->prev == A. After line 1 you have:

norse_gods == Thor

After line 2 you have:

norse_gods == Odin ---> Thor

The problem here is that Odin->succ == Thor but Thor->prev == nullptr. Because every element in the list has a pointer to its previous and successor element this is a doubly-linked list intended to be traversed in both directions, but right now it can only be traversed in one (left to right). This is corrected by making Thor->prev == Odin. Since Odin->succ == Thor and norse_gods == Odin we can access and change Thor->prev that way in the line norse_gods->succ->prev = norse_gods;. After that you have:

norse_gods == Odin <--> Thor

Upvotes: 6

Related Questions