Linked List Confusion I need some expert help Please

[Y2J]

I am working through this book on C++ programming, the author is
speaking of using linked lists. He gave and example which I found
confusing to say the least. So I rewrote the example in a way that I
could better understand the concept, he was trying to convey to me.

I ran my own example and it crashed and burn "what a surprise!" : (. I
ran the authors example out of the book and quess what, it crashed
also, : 0. I ran them both on my laptop that uses the blood shed C++
IDE and they both crashed, I ran them both on my desktop in MS Visual
Studio 6.0 and they both crashed.

So I kept trying to look over the code carefully and see what the hell
is going on here, but I lack the experience to understand the error
messages that are being returned to me. I need to understand this
concept as I know it is important to understand it before I can move
on.

Here is the code I re wrote:

#include <iostream>
using namespace std;

struct node
{
int data;

node *nextNode;
node *previousNode;
};

class linkedList
{
private:
node baseNode;

node *currentNode;
public:
void pushMethod(int item);

int popMethod();

};

void linkedList:ushMethod(int item)
{
node *temporaryNodeToBePushedOn = currentNode;

currentNode->nextNode = new node;

currentNode = currentNode->nextNode;

currentNode->previousNode = temporaryNodeToBePushedOn;
}

int linkedList:opMethod()
{
int temporaryNodeToBePoppedOff;

temporaryNodeToBePoppedOff = currentNode->data;

if(currentNode->previousNode == NULL)
{
return temporaryNodeToBePoppedOff;
}

currentNode = currentNode->previousNode;

delete currentNode->nextNode;

return temporaryNodeToBePoppedOff;
}

int main()
{
linkedList myLinkedList;

int data;

cout << "Enter your data, and enter -1 to exit \n";

while (data != -1)
{
cout << "Enter your next number: ";
cin >> data;

myLinkedList.pushMethod(data);
}

return 0;
} // End of double linked list example : )

*** Can anyone take the time to explain what is wrong here? ***
In the begining of the program I see this:

struct node
{
int data;

node *nextNode;
node *previousNode;
};

What doesn't make sense to me is that how can a structure be declared
with in a structure if the structure is first being declared. This
little piece of code appears as if the structure is being declared and
then two types of the same structure are being declared within it at
the same time. I thought that the structure is declared and then as a
data type and then it is used as a data type in declaring other things
such as pointers and variables. Anyways I must be retarded or
something. But the author gives like a five sentence explanation about
this then moves onto something completely different all together.

Peace, Jaret

 

[Victor Bazarov]

I am working through this book on C++ programming, the author is

Which book, BTW?

speaking of using linked lists. He gave and example which I found
confusing to say the least. So I rewrote the example in a way that I
could better understand the concept, he was trying to convey to me.

I ran my own example and it crashed and burn "what a surprise!" : (. I
ran the authors example out of the book and quess what, it crashed
also, : 0. I ran them both on my laptop that uses the blood shed C++
IDE and they both crashed, I ran them both on my desktop in MS Visual
Studio 6.0 and they both crashed.

So I kept trying to look over the code carefully and see what the hell
is going on here, but I lack the experience to understand the error
messages that are being returned to me. I need to understand this
concept as I know it is important to understand it before I can move
on.

Here is the code I re wrote:

#include <iostream>
using namespace std;

struct node
{
int data;

node *nextNode;
node *previousNode;
};

class linkedList
{
private:
node baseNode;

What's that for? You don't seem to make any use of it.

node *currentNode;
public:

Your 'currentNode' is left uninitialised upon creation of
the linkedList. You probably should add a constructor here
which will initialise 'currentNode' to null.

void pushMethod(int item);

int popMethod();

};

void linkedList:ushMethod(int item)

You don't seem to make any use of 'item'...

{
node *temporaryNodeToBePushedOn = currentNode;

currentNode->nextNode = new node;

currentNode = currentNode->nextNode;

currentNode->previousNode = temporaryNodeToBePushedOn;
}

int linkedList:opMethod()
{
int temporaryNodeToBePoppedOff;

temporaryNodeToBePoppedOff = currentNode->data;

Don't assign. Initialise. However, your 'data' member of
your 'currentNode' is never set to anything. Reading it may
be dangerous.

if(currentNode->previousNode == NULL)
{
return temporaryNodeToBePoppedOff;
}

currentNode = currentNode->previousNode;

delete currentNode->nextNode;

return temporaryNodeToBePoppedOff;
}

int main()
{
linkedList myLinkedList;

int data;

You never initialise your 'data' object here. Your 'while' will
not reliably work. If you need to always go into the body of the
'while' below, you must initialise 'data' to something that is
not -1. 0 would do nicely.

cout << "Enter your data, and enter -1 to exit \n";

while (data != -1)
{
cout << "Enter your next number: ";
cin >> data;

myLinkedList.pushMethod(data);

Again, in 'pushMethod' you don't use the argument. Whatever you
enter here is not going to be used.

}

return 0;
} // End of double linked list example : )

*** Can anyone take the time to explain what is wrong here? ***
In the begining of the program I see this:

struct node
{
int data;

node *nextNode;
node *previousNode;
};

What doesn't make sense to me is that how can a structure be declared
with in a structure if the structure is first being declared.

There is no "structure with in a structure". Both 'nextNode' and
'previousNode' members are _pointers_. That's allowed. All pointers
to objects have the same size and it's independent from the contents
of the class to which they point.

This
little piece of code appears as if the structure is being declared and
then two types of the same structure are being declared within it at
the same time.

No. Look again. Do you see '*' there?

I thought that the structure is declared and then as a
data type and then it is used as a data type in declaring other things
such as pointers and variables. Anyways I must be retarded or
something. But the author gives like a five sentence explanation about
this then moves onto something completely different all together.

You need to get a better grasp at pointers to understand linked lists
and dynamic memory allocation. Please go back to the part where they
are described.

The program you posted here is riddled with logical errors, and there
is no sense in pointing them out if you don't understand such things
like pointers. Please don't take this personally. You're not as you
say, retarded. You just haven't studied enough. Perhaps a different
book is in order...

V

 

[Y2J]

Which book, BTW?


What's that for? You don't seem to make any use of it.


Your 'currentNode' is left uninitialised upon creation of
the linkedList. You probably should add a constructor here
which will initialise 'currentNode' to null.


You don't seem to make any use of 'item'...


Don't assign. Initialise. However, your 'data' member of
your 'currentNode' is never set to anything. Reading it may
be dangerous.


You never initialise your 'data' object here. Your 'while' will
not reliably work. If you need to always go into the body of the
'while' below, you must initialise 'data' to something that is
not -1. 0 would do nicely.


Again, in 'pushMethod' you don't use the argument. Whatever you
enter here is not going to be used.


There is no "structure with in a structure". Both 'nextNode' and
'previousNode' members are _pointers_. That's allowed. All pointers
to objects have the same size and it's independent from the contents
of the class to which they point.


No. Look again. Do you see '*' there?


You need to get a better grasp at pointers to understand linked lists
and dynamic memory allocation. Please go back to the part where they
are described.

The program you posted here is riddled with logical errors, and there
is no sense in pointing them out if you don't understand such things
like pointers. Please don't take this personally. You're not as you
say, retarded. You just haven't studied enough. Perhaps a different
book is in order...

V

The title of the book is: C++ Programming Fundamentals by Chuck Easttom
ISBN:1584502371

I don't understant cap 'a' thing, as I have not posted many questions
here:
This is the authors code example:
//Step 1: Place the following code into your favorite text editor and
save it as linkedlist.h.
//#include "linkedlist.h"
#include <iostream>
using namespace std;
struct node
{
int data; // data can be of any type at all.
node *nextnode;
node *prevnode;
};
class linkedlist
{
private:
node base; // This is the base node
// from which other nodes will
// spring.
node *curnode;// A pointer to the current node.
public:
void push(int item);
int pop();
};
void linkedlist:ush(int item)
{
// This function basically creates a new node and
// places it at the top of the linked list. The node
// currently at the top is moved down.
node *temp=curnode; // Temporary node
curnode->nextnode=new node;// Create new node
curnode=curnode->nextnode; // Assign current to
// new top node
curnode->data=item; // Assign the data
curnode->prevnode=temp;// Set previous
// pointer
}
int linkedlist:op()
{
// This function pulls the data off the current
// node,then
// moves the node preceding the current node into the
// front
// of the linked list.
int temp;
temp=curnode->data;
// if the previous node is somehow already gone, then
// skip
// the rest.
if (curnode->prevnode == NULL)
return temp;
curnode=curnode->prevnode;
// delete the node we just popped off
delete curnode->nextnode;
return temp;
}

//Step 2: Write the following code into your favorite text editor and
save it as 13_02.cpp.


int main()
{
linkedlist mylist;
int data;
cout << "Enter your data, and enter -1 to exit \n";
while(data != -1)
{
cout << "Enter your next number \n";
cin>> data;
mylist.push(data);
}
return 0;
}// end main

I included the header file into my main source file so I could better
follow what was going on. Thanks for your reply
Peace, Jaret

 

[Victor Bazarov]

I am working through this book on C++ programming, the author is

Which book, BTW?
[..previous analysis of the program snipped..]

The title of the book is: C++ Programming Fundamentals by Chuck
Easttom ISBN:1584502371

I don't understant cap 'a' thing, as I have not posted many questions
here:

The capital A thing is for you if you want to contact me by e-mail,
my return address is mangled.

This is the authors code example:

OK, let's take a look...

//Step 1: Place the following code into your favorite text editor and
save it as linkedlist.h.
//#include "linkedlist.h"
#include <iostream>
using namespace std;
struct node
{
int data; // data can be of any type at all.
node *nextnode;
node *prevnode;
};
class linkedlist
{
private:
node base; // This is the base node
// from which other nodes will
// spring.
node *curnode;// A pointer to the current node.
public:

Again, this class does not initialise 'curnode' upon its construction.
That's what causes the crash. It should probably do

linkedlist() : curnode(&base) {}

As soon as you add this, the program does not crash any more. Try it.

void push(int item);
int pop();
};
void linkedlist:ush(int item)
{
// This function basically creates a new node and
// places it at the top of the linked list. The node
// currently at the top is moved down.
node *temp=curnode; // Temporary node
curnode->nextnode=new node;// Create new node
curnode=curnode->nextnode; // Assign current to
// new top node
curnode->data=item; // Assign the data
curnode->prevnode=temp;// Set previous
// pointer
}
int linkedlist:op()
{
// This function pulls the data off the current
// node,then
// moves the node preceding the current node into the
// front
// of the linked list.
int temp;
temp=curnode->data;
// if the previous node is somehow already gone, then
// skip
// the rest.
if (curnode->prevnode == NULL)
return temp;
curnode=curnode->prevnode;
// delete the node we just popped off
delete curnode->nextnode;
return temp;
}

//Step 2: Write the following code into your favorite text editor and
save it as 13_02.cpp.


int main()
{
linkedlist mylist;
int data;

^^^^^^^^^^^^
Again, this is uninitialised object. You need to replace it with

int data = 0;

cout << "Enter your data, and enter -1 to exit \n";
while(data != -1)
{
cout << "Enter your next number \n";
cin>> data;
mylist.push(data);
}
return 0;
}// end main

I included the header file into my main source file so I could better
follow what was going on. Thanks for your reply

You're welcome. I still think you should chuck this book and get
yourself a copy of "Accelerated C++", for example, or any other
beginner's book on C++ that has decent reviews on www.accu.org.
There is "Thinking in C++" by Bruce Eckel (IIRC), freely available
on the 'Net.

V

 

[Y2J]

Y2J wrote:
I am working through this book on C++ programming, the author is

Which book, BTW?
[..previous analysis of the program snipped..]

The title of the book is: C++ Programming Fundamentals by Chuck
Easttom ISBN:1584502371

I don't understant cap 'a' thing, as I have not posted many questions
here:

The capital A thing is for you if you want to contact me by e-mail,
my return address is mangled.

This is the authors code example:

OK, let's take a look...

//Step 1: Place the following code into your favorite text editor and
save it as linkedlist.h.
//#include "linkedlist.h"
#include <iostream>
using namespace std;
struct node
{
int data; // data can be of any type at all.
node *nextnode;
node *prevnode;
};
class linkedlist
{
private:
node base; // This is the base node
// from which other nodes will
// spring.
node *curnode;// A pointer to the current node.
public:

Again, this class does not initialise 'curnode' upon its construction.
That's what causes the crash. It should probably do

linkedlist() : curnode(&base) {}

As soon as you add this, the program does not crash any more. Try it.

void push(int item);
int pop();
};
void linkedlist:ush(int item)
{
// This function basically creates a new node and
// places it at the top of the linked list. The node
// currently at the top is moved down.
node *temp=curnode; // Temporary node
curnode->nextnode=new node;// Create new node
curnode=curnode->nextnode; // Assign current to
// new top node
curnode->data=item; // Assign the data
curnode->prevnode=temp;// Set previous
// pointer
}
int linkedlist:op()
{
// This function pulls the data off the current
// node,then
// moves the node preceding the current node into the
// front
// of the linked list.
int temp;
temp=curnode->data;
// if the previous node is somehow already gone, then
// skip
// the rest.
if (curnode->prevnode == NULL)
return temp;
curnode=curnode->prevnode;
// delete the node we just popped off
delete curnode->nextnode;
return temp;
}

//Step 2: Write the following code into your favorite text editor and
save it as 13_02.cpp.


int main()
{
linkedlist mylist;
int data;

^^^^^^^^^^^^
Again, this is uninitialised object. You need to replace it with

int data = 0;

cout << "Enter your data, and enter -1 to exit \n";
while(data != -1)
{
cout << "Enter your next number \n";
cin>> data;
mylist.push(data);
}
return 0;
}// end main

I included the header file into my main source file so I could better
follow what was going on. Thanks for your reply

You're welcome. I still think you should chuck this book and get
yourself a copy of "Accelerated C++", for example, or any other
beginner's book on C++ that has decent reviews on www.accu.org.
There is "Thinking in C++" by Bruce Eckel (IIRC), freely available
on the 'Net.

Thanks it worked just like you said t would: is this the book you where
talking about?
Accelerated C++
Practical Programming by Example
by Andrew Koenig and Barbara E. Moo
Addison-Wesley, 2000
ISBN 0-201-70353-X
Pages 336
Second Printing

Because I actually have that book, and was considering reading it next.
I just wanted to finish the book I was on in order to disipline myself
to finish what I started. I only got halfway through the Dietel book on
C++ and was really disappointed with it. There allot of books out there
and they all claim to be able to teach you how to program C++, and
maybe that is true; but they don't all claim to teach you how to
understand C++ which I have found in most csases is disappointing.

I thought I did understand pointers to some degree, but the author just
took off from something simple to understand and got into something I
just could'nt seem to grasp.
When you "pointed" out that the pointer was not initialized I
remembered the author in the book saying always to point the pointer to
something or else you could crash your system and not to point it
beyond the counds of an array or esle you would get yourself in
trouble.

What books have you read that you found helpfull in learning C++? Yeah
I guess I still suck at understanding the concept of pointers,
especially if I can't even notice that they are not initilized in the
code properly. Thank you for your swift response and input.

Peace, Jaret

 

[Victor Bazarov]

[..]

Thanks it worked just like you said t would: is this the book you
where talking about?
Accelerated C++
Practical Programming by Example
by Andrew Koenig and Barbara E. Moo
Addison-Wesley, 2000
ISBN 0-201-70353-X
Pages 336
Second Printing

Yes. And also do visit www.accu.org, book review section. Time well
spent, if you ask me.

Because I actually have that book, and was considering reading it
next. I just wanted to finish the book I was on in order to disipline
myself to finish what I started. I only got halfway through the
Dietel book on C++ and was really disappointed with it. There allot
of books out there and they all claim to be able to teach you how to
program C++, and maybe that is true; but they don't all claim to
teach you how to understand C++ which I have found in most csases is
disappointing.

I don't know how good the Deitel book is (and not sure which one you
refer to, I think there are several), but look at www.accu.org, and
you will probably find it reviewed.

I thought I did understand pointers to some degree, but the author
just took off from something simple to understand and got into
something I just could'nt seem to grasp.

Pointers can be intimidating, no doubt. Often it's better to put them
aside for a while. Linked lists and other data structures are not
trivial either, and of course they make use of pointers all over, and
you gotta understand pointers relatively well to grasp data structures
better. One will help the other. Maybe a decent book (like Robert
Sedgewick's "Algorithms in C++") could help...

When you "pointed" out that the pointer was not initialized I
remembered the author in the book saying always to point the pointer
to something or else you could crash your system and not to point it
beyond the counds of an array or esle you would get yourself in
trouble.

I remember from my early days on Usenet I've debated the rule for
beginners to initialise everything; and while I don't remember the
exact argument or what we ended up with, if you ask me now, I would
probably recommend it. IOW, whatever it is, a pointer, an int,
a double, a class object, a reference, a pointer to function, don't
let it go uninitialised. Ever.

What books have you read that you found helpfull in learning C++?

I started with Stroustrup, 1st edition, translated into Russian (very
likely pirated), but it was a long time ago, and it was essentially
the only book available. I then moved onto "The Annotated Reference
Manual" by Ellis and Stroustrup, which I don't recommend as a learning
material. Next was "Advanced C++" by James Coplien. All those books
are now rather old, except "The C++ Programming Language" by Bjarne
Stroustrup because it's undergone several editions, and many more
printings. I have the Special Edition, and only recommend it to those
who are serious about C++.

Nowadays there are many [relatively] new books, and "Acc'ted C++" by
Koenig and Moo is one of the best, or so I hear. I don't own a copy
myself, probably don't have a need for it at this point. I heard
good things about "Thinking in C++" as well. Just look in the archives
of this newsgroup (http://groups.google.com/group/comp.lang.c++) for
any book recommendations.

Some find Stroustrup's "The C++ Programming Language" a bit dry or
possibly difficult to study the language by, but it's mostly because
it's so jam-packed with information.

Yeah I guess I still suck at understanding the concept of pointers,
[..]

Nah, you just need a bit more time with it. Eventually it becomes
your "second nature", don't worry about it. The more you apply them
the simpler they appear. What sometimes helps is to understand how
they are represented in memory, what they mean, how the hardware
works. It's not necessary, but it's useful if you want to be any
good at programming. Check out "Inside the C++ Object Model" by
Lippman.

V