I'm having trouble understanding the linked list demo program which I
will include below.
The problem I'm having is following what's actually happening in main
& the Insert()function when pHead-> calls the Insert function on the
first new Node.  If I can get an understanding of what happens on the
first and second pass using the input values of (1, and 9) I will be
able to grasp the essense of this program. Specifically***((I don't
understand how the three local variables NextCatsAge, NewAge, and
ThisNodeAge get their values. And especially NextCatsAge and
ThisNodeAge on the first and second pass))***.  All help and
suggestions, are  greatly appreciated....
Program follows:
 
// Linked list simple implementation

#include <iostream.h>

// object to add to list
class CAT
{
public:
CAT() { itsAge = 1;}
CAT(int age):itsAge(age){}
~CAT(){};
int GetAge() const { return itsAge; }
private:
int itsAge;
};

// manages list, orders by cat's age!
class Node
{
public:
Node (CAT*);
~Node();
void SetNext(Node * node) { itsNext = node; }
Node * GetNext() const { return itsNext; }
CAT * GetCat() const { return itsCat; }
void Insert(Node *);
void Display();
private:
CAT *itsCat;
Node * itsNext;
};


Node::Node(CAT* pCat):
itsCat(pCat),
itsNext(0)
{}

Node::~Node()
{
cout << "Deleting node...\n";
delete itsCat;
itsCat = 0;
delete itsNext;
itsNext = 0;
}

// ************************************
// Insert: Orders cats based on their ages
// Algorithim: If you are last in line, add the cat
// Otherwise, if the new cat is older than you
// and also younger than next in line, insert it
// after this one. Otherwise call insert on the
// next in line
// ************************************
void Node::Insert(Node* newNode)
{
if (!itsNext)
itsNext = newNode;
else
{
int NextCatsAge = itsNext->GetCat()->GetAge();
int NewAge = newNode->GetCat()->GetAge();
int ThisNodeAge = itsCat->GetAge();

if ( NewAge > ThisNodeAge && NewAge < NextCatsAge )
{
newNode->SetNext(itsNext);
itsNext = newNode;
}
else
itsNext->Insert(newNode);
}
}

void Node::Display()
{
if (itsCat->GetAge() > 0)
cout << "My cat is " << itsCat->GetAge() << " years old\n";
if (itsNext)
itsNext->Display();
}

void main()
{

Node *pNode = 0;
CAT * pCat = new CAT(0);
int age;

Node *pHead = new Node(pCat);

while (1)
{
cout << "New Cat's age? (0 to quit): ";
cin >> age;
if (!age)
break;
pCat = new CAT(age);
pNode = new Node(pCat);
pHead->Insert(pNode);
}
pHead->Display();
delete pHead;
cout << "Exiting...\n\n";
}

Hello!

The best way to understand how a program like this works is to
actually walk through the program step by step and watch how the data
changes.  I'm going to talk about each line of the program as it
executes, and we'll see exactly what is happening in your demo
program.  We'll start at main():

(1) Node *pNode = 0;
--------------------
pNode (a pointer to a Node) is declared and set to 0 as a safety.  0
is used throughout this program to signal a pointer to nothing.  When
a piece of a linked list points to nothing, that usually signals the
end of the list.

(2) CAT * pCat = new CAT(0);
----------------------------
An initial CAT is created with an 'age' of zero.  pCat (a temporary
variable) points to it.

(3) int age;
------------
age is declared as a local temporary value for user input.

(4) Node *pHead = new Node(pCat);
---------------------------------
A new Node is created, using pCat as it's CAT.  The pointer to the new
node is saved in pHead.  pHead's variable 'itsCat' now points to the
new CAT, and 'itsNext' is set to 0 (list terminator).  Our linked list
looks like this:

	pHead -> Node[CAT(0)] -> 0 (list end)

This line #4 is important, since it sets up the head of the list.  We
know from the constructor of Node that the private variable 'itsNext'
is set to 0, so it is pointing at nothing.  This new Node stands alone
and points to nothing else.  It's a linked list with 1 element in it. 
Display skips CATs that have an age of zero, so we know this node is
used only as a placeholder for the head of the list.

while(1) {
----------
Now we're beginning the main loop, so let's see what happens on the
first pass of the main program loop with your first cat's age, which
is 1.

(5) pCat = new CAT(age);
------------------------
A new CAT is created and it's private variable 'itsAge' is set to 1.

(6) pNode = new Node(pCat);
---------------------------
A new Node is created and the following private variables set:
      itsCat is set to pCat;
      itsNext is set to 0 (list terminator);

The next line is where the fun starts.  

(7) pHead->Insert(pNode);
-------------------------
Note that we are calling the Insert() method of *the Node pointed to
by pHead*, not by pNode!  This is what the '->' operator does in C++. 
It saying this:

   "I know I'm only a pointer to an object, so call the method of the
object I am
    pointing to."

'->' can used on any public method or public data of an object, but in
this program it's used only to call public methods.

We are going to connect our new Node (pNode) into the list, but we do
it by telling the head of the list about pNode.  The Node that pHead
points to was created back in line (4).

Let's follow what happens in Insert.  We begin the function with
newNode pointing to the Node created in step (6).  That Node has a CAT
with it's 'itsAge' set to 1.

if (!itsNext)
-------------
Here's the big decision point for Insert.  Does our Node have a Node
linked to it, or are we at the end?  If 'itsNext' is set to 0, then
we're at the end.  If it's some other value greater than 0, the
programmer is assuming 'itsNext' is pointing to another Node.

So let's see what pHead's Node has for a value on the first pass. 
Look at step (4).  It's 0.  In C (and C++), the ! math operator
inverts a value.  Anything non-zero becomes 0, and anything zero
becomes non-zero.  Since 'itsNext' is 0, !itsNext is non-zero, and
this if statement evaluates to 'true'.

So on the first pass, we are true, so we execute the next line:

(8) itsNext = newNode;
----------------------
Therefore pHead's Node changes it's 'itsNext' from 0 to the pointer to
Node[CAT(1)].  Our list now looks like this:
           
	pHead --> Node[CAT(0)] --> Node[CAT(1)] --> 0

Remember that pHead is only a POINTER to a Node, not a Node itself. 
I'm using --> to draw a graph, please don't confuse this with C++'s
'->' operator.

Look at the structure of the if/else.  Nothing else happens on this
call of Insert()!  We've completed the first pass of the program! 
NextCatsAge, NewAge, and ThisNodeAge are never created or set to
anything.  This is probably why you got partially confused.

Now let's get to the rest of your question.  Here's the second pass. 
We repeat lines 5 and 6 again, setting up a new CAT with age=9 and
setting up a Node that points to that CAT.  We again call
pHead->Insert().

THIS TIME, pHead.itsNext is not 0!  So the first 'if' statement is
false.  We jump to the 'else' and see this:
        
        int NextCatsAge = itsNext->GetCat()->GetAge();

Again we see the '->' operator being used, so we will be calling
methods in objects that we are pointing to.

The 'int' at the start means we're declaring the integer local
variable 'NextCatsAge' every time we are called.  It will go away when
the function ends.  The value of the variable is set by calling

        itsNext->GetCat()->GetAge();

We know that 'itsNext' points to another Node, and we know it's the
next one in the list.  We know that it's not 0, so we go ahead and
call itsNext->GetCat().  GetCat() is a method in the Node object that
returns a pointer to it's CAT.  So essentially we are asking about the
CAT in the *next* Node, not our own!  We get that pointer, then call
the GetAge method of that CAT by using GetAge().  So let's recap:

        int NextCatsAge = itsNext->GetCat()->GetAge();

1) We are making a new local variable
2) We call the GetCat() method of the Node pointed to by 'itsNext',
and we get back a pointer to a CAT.
3) We call the GetAge() method of that CAT, which returns an int.
4) NextCatsAge is set to that int.

So on the second pass, NextCatsAge is set to '1'.

We now do the same thing for NewAge, this time we call

        int NewAge = newNode->GetCat()->GetAge().

We are asking for the age in the Node that was passed to Insert. 
Remember that we created this new Node with a CAT of age 9.  That
pointer was passed to Insert as newNode.  So in the end NewAge will be
set to '9'.

The last variable is going to find out the age of the cat the current
Node.  Remember that we called

        pHead->Insert(...

So when Insert() runs, it's in the scope of the Node that pHead points
to.  Remember back on line (4) that pHead points to a Node with a CAT
of 0!  ThisNodeAge will be set to '0' when the statement is finished.

This is the classic algorithm for what's called an "insertion sort". 
We walk through the list while comparing our current position, the
next position, and the new data we are trying to insert.  When we find
the right spot, our new item gets placeed in the middle and the links
are updated.  The current position's item will be less than the new
item, and the new item will be less than the next position's item.

Let's see how our list looks so far:

       pHead --> CAT(0) --> CAT(1) --> 0 (end)

My guess is that we're not going to fit a CAT of (9) in between 0 and
1.  Let's look at the next line:

if (NewAge > ThisNodeAge && NewAge < NextCatsAge)
-------------------------------------------------
Substitute the numbers and what do you see?

if (9 > 0 && 9 < 1)

The second comparison (9 < 1) is false.  Inserting 9 between 0 and 1
will not be a good insertion.  This whole statement evaluates to
false, but look what happens on the 'else'!

else
   itsNext->Insert(newNode);
----------------------------
We call Insert all over again, but we pass it newNode!  This time
instead of pointing to the first node CAT(0), we will be calling
Insert from the Node of CAT(1).   A function that calls itself like
this is known as a recursive function.

When Insert restarts and gets to this same point, another compare
would normally happen.  However we come across the special case check
at the start of Insert:

if (!itsNext)
   itsNext = newNode;
---------------------
Remember this?  If we're at the end of the list, just insert the new
Node (and CAT) at the end of the list.  Sadly this time we won't have
a chance to compare cat's ages again.  But now that you understand how
the variables are set, you can walk through Insert() step by step and
watch how new Nodes are placed in the correct order of the list. 
Node[CAT(9)] is now connected to the end of Node[CAT(1)].  At the end
of this statement our list now looks like:

       pHead --> CAT(0) --> CAT(1) --> CAT(9) --> 0 (end)

And all the little cats are happily in their line.

Now let's go one step further and see what happens if that comparison
statement evaluates to true:

       if (NewAge > ThisNodeAge && NewAge < NextCatsAge)

Let's say we had a CAT of age 5.  We would call Insert over and over
until we pointed to the Node of CAT(1).  We compare (5 > 1 && 5 < 9),
get a 'true', and then the following code then happens:

       newNode->SetNext(itsNext);
       itsNext = newNode;

The first statement is taking 'itsNext' (CAT 1's pointer to CAT 9) and
storing it in the 'itsNext' variable of CAT 5.  We are then setting
the 'itsNext' of CAT 1 to the newNode, which is CAT 5.  We would be
sticking CAT 5 right in between CAT 1 and CAT 9 in the linked list. 
Think of it like unhooking a train and connecting a new car in the
middle.

Whew!  That should be it!  It sure takes longer to walk through code
while you're typing in english!  But hopefuly you have a better grasp
of the code now.  When it comes to walking through code like this I
like to just take a pencil and a clean pad of paper and start to write
down the values that all the variables are set to, step by step.  Use
your eraser, change values, cross things out, and get a feel for what
your code is actually doing to the data.  Drawing pictures or graphs
doesn't hurt either, *especially* when it comes to linked list code.

I hope this explanation was clear enough.  If not, please request a
clarification and I will be more than happy to try and explain things
to the best of my ability as soon as I can.

Good luck!
koz-ga

---

Request for Answer Clarification by nebulae-ga on 17 Nov 2002 10:47 PST

Thank you very much, that was a fine job.  I now understand how it
works.
However I do have a couple of what I hope are yes and no, final
questions.
AKA stupid questions....

(1) When itsNext is changed from 0 to 1 by the newNode. Does it stay
at a value of 1, even when the node constructor is used to create
another node on the next pass? If so; is it because itsNext is a
pointer and it continues to point to a value/object until changed?

(2) The last question  is on pHead->insert(....
"so when Insert() runs, it's in the scope of the Node that pHead
points to."
Does this means that the pointer itsCat is actually pointing to the
cat in pheads node, or is this the standard procedure for this
algorithm to assign itsCat to whomever calls the insert() function?

---

Clarification of Answer by koz-ga on 18 Nov 2002 08:38 PST

Hey, there are no stupid questions.  Understanding pointers and how
they work with objects in C++ can be very tricky!

1) Yes, the 'itsNext' pointer for that newNode on the first pass stays
at 1 (a pointer to the Node that has a CAT of age 1).  To understand
why, you have to remember how objects work in C++.  Every time you
create a new Node with "new Node(pCat)", you are creating a hunk of
memory that contains all the public and private variables you declared
in the object declaration.  EVERY Node that you create has it's own
copy of an 'itsNext' variable, as well as all the other variables
declared in the object.

To help you visualize this, look at http://www.koziarz.com/google.jpg.
 Every box is an object (either Node or CAT).  The lines and arrows
represent pointers to other Nodes or CATs.  pHead is a pointer, for
example, and can only point to something.  Nodes have internal
variables and methods, those are listed inside each object.

In the first screen, you see how the list looks after the head node
was created (the CAT of age 0), and we entered 1 for the age of the
first cat.  A new CAT object was created, then a new Node was created
and the itsCat variable pointed to that new CAT.  pNode points to this
new Node, but it is not linked yet.

Now look at the second screen.  The Insert() method has found the
correct place to link in the new CAT, so it sets 'itsNext' in this
Node to point to the Node with the CAT of age 1.

Now look at the third screen.  We have created a new CAT of age 9 and
created a new Node to point to that CAT.  The Node constructor has set
up a whole new chunk of memory and initialized all the variables to
the values we choose in the constructor method.  The 'itsNext' back at
CAT #0 still points to CAT #1, that will not change until set by
somebody else.

2) You are kind of correct, check the diagram again.  When the program
calls pHead->Insert(), it is running the Insert procedure inside that
first block, the first Node in our list.  That is the Node that pHead
is pointing to, so that is the Insert() method we will call.  Imagine
that every Node we create has it's own Insert() method living inside
of it.  When we call Insert() and it uses variables like itsCat and
itsNext, it only knows about the itsCat and itsNext variables that are
inside the same box (object) as it's own box.  It does not know about
any other variable inside of any other boxes (or objects).  This is
what we mean by "scope".  Methods can only see what's in their little
world, nothing outside.  This is why CAT has something called
GetAge(), it's used to fetch the 'itsAge' variable and pass it back to
the caller.

I hope this helps a little more.  Like I said, drawing pictures can
help immensely when understanding objects and pointers.  I'm sorry I
couldn't include the diagrams in-line, but this should work well
enough.

Good luck, let me know if you're still confused.

It is quite evident that this Koz is a consummate  C++ programmer. Also one that
cares about the person on the receiving end of his answers.

I admire that koz-ga having good patience to explain so much. 
For me, it may cause me more one hour of typing and I will be crazy. 

By the way, there is a small error in this coding
of insert sort.
That is, the line in the insert function

 if ( NewAge > ThisNodeAge && NewAge < NextCatsAge ) 
 should be
 if ( NewAge > ThisNodeAge && NewAge <= NextCatsAge ) 
for otherwise if the user keys in cat having duplicates, then the 
duplicating age will go to the last (as the largest) and so not
correct.

 This program is written recursively, and created a symbolic head with
 cat age zero. Therefoer,  it is very hard for the beginners to
understand.
 
 Recurvie function can make the program short but it is hard to debug
and not  so constructive as the basic iterative way.

 In my opinion, try initialize pHead as NULL and use while loop to do
insert

 and display. Any students can try.

 Also, my point is the algorithm of insert sort is very simple. But,
this
 program causes easy stuff becoming complicated unnecessarily.
 
 Kenny

Yeah, kennyh, you make a good point.  Doing an insertion sort by
recursive means isn't exactly a beginner-level exercise.  One can also
argue that it's inefficient compared to a simple while-loop,
especially when it comes to terms of processor stack overhead and C++
function calling time.  (I'm used to doing embedded systems, we don't
have much memory for anything!)

I also noticed the missing equals condition as well, I figured it was
best not to say anything.  I'm also a fan of doing all my local
variable allocation up-front in a function, and using NULL as a
pointer terminator and not 0 (that leads to some nasty bugs).  I think
that's what confused nebulae, C programmers like to cram everything as
tightly as possible (e.g. math inside of 'for' statements, abuse of
the ? and : operators everywhere), and in most cases it doesn't result
in code that's any more efficient after compilation, it just results
in source that's harder to understand and debug.

There's no reason why the demo author could have written part of
Insert like this:

int NextCatsAge = 0;
Node *pNextNode = 0;
CAT *pNextCat = 0;

if (itsNext != 0) {       // here's a case where NULL would be better!
  pNextNode = itsNext;              // copy pointer to next node
  pNextCat = pNextNode->GetCat();   // get pointer to next node's CAT
  NextCatsAge = pNextCat->GetAge(); // get the age of that next CAT
}

It may make some of the advanced C coders here rip their hair out, but
it would have saved nebulae countless hours of time.