FacebookTwitter
Hatrack River Forum   
my profile login | search | faq | forum home

  next oldest topic   next newest topic
» Hatrack River Forum » Active Forums » Books, Films, Food and Culture » Linear Linked List, help and also why Pointers are EVIL

   
Author Topic: Linear Linked List, help and also why Pointers are EVIL
Blayne Bradley
unregistered


 - posted            Edit/Delete Post 
code:
class List
{
public:
List( /* in */ const char dataLine[] );
~List( );
void PrintList( ) const;
void ReversePrintList( ) const;
private:
struct Node
{
char item;
Node* next;
};

Node* front;


};

List::List( /* in */ const char dataLine[] )
{


int temp = strlen(dataLine);

for ( int counter = 0; counter < temp; counter++)
{
front = new Node;
front->item = dataLine[counter];
front->next = front;


cout << front->item << endl;
}

}

basicaly I am trying to make a linear linked list with pointers. In main I pass the constructor an array with the items say a,b,c, and d.

However I am dereferencing a null value somewhere and I am not quite sure where.

http://img102.imageshack.us/my.php?image=dereferenceid9.png

heres the what error looks like.

So ya can anyone help me.

IP: Logged | Report this post to a Moderator
Blayne Bradley
unregistered


 - posted            Edit/Delete Post 
Okay, fixed it apparently i had a pointer pointing to nowhere but alas my linked list still isnt working right. for some reason each front->item is always equaling to a. and I am not sure how I am doing it wrong.
IP: Logged | Report this post to a Moderator
El JT de Spang
Member
Member # 7742

 - posted      Profile for El JT de Spang   Email El JT de Spang         Edit/Delete Post 
You've never gonna be worth much as a programmer if you run for help every time you run into an error message.

Learn to debug your own programs -- I can't stress how important a skill this is.

Posts: 5462 | Registered: Apr 2005  |  IP: Logged | Report this post to a Moderator
MrSquicky
Member
Member # 1802

 - posted      Profile for MrSquicky   Email MrSquicky         Edit/Delete Post 
When working with nodes and pointers, I recommend drawing out what you are expecting to happen so that you can identify where it goes wrong. Your problem here looks to be pretty basic and that should fix you right up.

Also, what JT said. If you ever want to get hired as a programmer, now is the time to develop some self-reliance in debugging.

Posts: 10177 | Registered: Apr 2001  |  IP: Logged | Report this post to a Moderator
Dagonee
Member
Member # 5818

 - posted      Profile for Dagonee           Edit/Delete Post 
I had little magnets with node boxes drawn on them that stuck to a white board, plus color-coded magnetic arrows. Worked great for stepping through iterations.

The magnets had dry-erasable surfaces, so I could put in values.

Make each box a node, draw arrows from the pointer field in the struct, use the colored arrows to represent pointer variables.

Posts: 26071 | Registered: Oct 2003  |  IP: Logged | Report this post to a Moderator
King of Men
Member
Member # 6684

 - posted      Profile for King of Men   Email King of Men         Edit/Delete Post 
Stepping through code in your head, and using cout statements, are both great friends for a programmer. You should note that a human brain actually makes a supremely excellent debugging interpreter for C++.
Posts: 10645 | Registered: Jul 2004  |  IP: Logged | Report this post to a Moderator
King of Men
Member
Member # 6684

 - posted      Profile for King of Men   Email King of Men         Edit/Delete Post 
And dude, did you even read your own code? Please do take a look at what you are doing with that assignment of front.
Posts: 10645 | Registered: Jul 2004  |  IP: Logged | Report this post to a Moderator
Bokonon
Member
Member # 480

 - posted      Profile for Bokonon           Edit/Delete Post 
Do you not have breakpoints in your environment? I also recommend a whiteboard/chalkboard/piece of paper. Then step through line by line your constructor, with boxes for a node object, and an arrow for the node pointer in the Node. also have a box labelled null. Try this with a dataLine with one value, and then try it with 2 values in dataLine. If you still don't see it, try with 3 values. If you _still_ don't see it, talk to your teacher('s assistant).

Also, for your own sanity, explicitly initialize your pointers...

-Bok

Posts: 7021 | Registered: Nov 1999  |  IP: Logged | Report this post to a Moderator
Chanie
Member
Member # 9544

 - posted      Profile for Chanie   Email Chanie         Edit/Delete Post 
Download gdb (or some other debugger). You'll find the problem right away.
Posts: 159 | Registered: Jun 2006  |  IP: Logged | Report this post to a Moderator
The Pixiest
Member
Member # 1863

 - posted      Profile for The Pixiest   Email The Pixiest         Edit/Delete Post 
If you are having problems with such a simple program of your own creation, you will suffer greatly when you have to debug someone elses code and you have no clue what their rational is.

Further, pointers are everything. If you can't handle them/hate them and can not learn to love them, maybe you should look for another career.

Posts: 7085 | Registered: Apr 2001  |  IP: Logged | Report this post to a Moderator
Chanie
Member
Member # 9544

 - posted      Profile for Chanie   Email Chanie         Edit/Delete Post 
Ah, as I click on your error, I see that you are using an IDE. Did you try to use the debugger? When I TA'ed an intro class I wouldn't even talk to a student unless they could tell me what happened when they tried to run it in the debugger.
Posts: 159 | Registered: Jun 2006  |  IP: Logged | Report this post to a Moderator
Ken
Member
Member # 10082

 - posted      Profile for Ken   Email Ken         Edit/Delete Post 
Master pointers and the building of simple data structures like a linked list and then higher level languages like ruby will be a real treat!

The first couple programming classes can be rough because you have no foundation but it's worth the trouble.

Posts: 20 | Registered: Jan 2007  |  IP: Logged | Report this post to a Moderator
Will B
Member
Member # 7931

 - posted      Profile for Will B   Email Will B         Edit/Delete Post 
Let's be merciful. We can't expect beginning programmers to be as adept as experts.

Blayne, you weren't ready to compile yet, because you needed to walk thru your code as others here recommended: visually, going thru the steps of your function, drawing yourself a box for each variable you make, filling in its contents with the values you get (which will be arrows pointing to other things, if they're pointers), and see what happens. When you have done that and it seems to give you the right result, then you're ready to write it as real code and compile it. If you don't know what I mean, get a prof or TA to show you -- it is a skill you will use over and over again.

Your problem here is that you have, for each Node you create, the next pointer pointing to that same Node. That is, you're creating a bunch of circular lists of length 1.

Posts: 1877 | Registered: Apr 2005  |  IP: Logged | Report this post to a Moderator
Dagonee
Member
Member # 5818

 - posted      Profile for Dagonee           Edit/Delete Post 
BTW, being able to fluidly work with various forms of indirection is a very useful mental process to have in you arsenal. The uses in programming are obvious and way beyond pointers.

But when I went to law school, it was immediately useful.

Practice doing this and being able to keep straight in your head whether you are talking about a thing, or something that refers to that thing, and you will have developed a mode of thought that will serve you well in many situations.

Posts: 26071 | Registered: Oct 2003  |  IP: Logged | Report this post to a Moderator
Blayne Bradley
unregistered


 - posted            Edit/Delete Post 
on the car ride home I figured out what the problem is for some reason its making a circular linked list by pointing to itself so each time it goes through the loop it simple replaces itself and then points to itself. Now I just need to figure out how to not make it circular.

I have couts and I have a debugger and it howed it pointing to itself for infinity but i hadnt realized at the time that I was looking at a 1 node circular linked list.


*Did not read Wills post before posting this*

IP: Logged | Report this post to a Moderator
Bokonon
Member
Member # 480

 - posted      Profile for Bokonon           Edit/Delete Post 
Don't just rely on your program. Independently verify your algorithm (especially school projects) using paper/whiteboard/your brain. Use one to validate the other. And don't make assumptions when doing it out by hand.

-Bok

Posts: 7021 | Registered: Nov 1999  |  IP: Logged | Report this post to a Moderator
Scott R
Member
Member # 567

 - posted      Profile for Scott R   Email Scott R         Edit/Delete Post 
Dude, follow your heart.

That's what I always do.

Posts: 14554 | Registered: Dec 1999  |  IP: Logged | Report this post to a Moderator
King of Men
Member
Member # 6684

 - posted      Profile for King of Men   Email King of Men         Edit/Delete Post 
quote:
for some reason its making a circular linked list by pointing to itself
Just like you told it to. Dude, it's staring you right in the face. Step through the code in your head like we've been telling you; it'll jump right out. By the way, do you have a sub for Poland or Greece tomorrow?
Posts: 10645 | Registered: Jul 2004  |  IP: Logged | Report this post to a Moderator
Blayne Bradley
unregistered


 - posted            Edit/Delete Post 
front->next = front; THIS is whats causing it, Im just tryign to figure out now how to get it not to do that, the examples online dont help.
IP: Logged | Report this post to a Moderator
Chanie
Member
Member # 9544

 - posted      Profile for Chanie   Email Chanie         Edit/Delete Post 
If you were to say it in English, what would you want the next arrow of front pointing to?
Posts: 159 | Registered: Jun 2006  |  IP: Logged | Report this post to a Moderator
MrSquicky
Member
Member # 1802

 - posted      Profile for MrSquicky   Email MrSquicky         Edit/Delete Post 
It's important to keep in mind that a linked list should generally also end (i.e. have its last node pointing to nothing).

---

Stop looking for examples on the web, take people's advice here, and figure it out on your own. This is something you are going to need to be able to visualize for yourself, and the only way to do that is to do it.

[ March 30, 2007, 04:01 PM: Message edited by: MrSquicky ]

Posts: 10177 | Registered: Apr 2001  |  IP: Logged | Report this post to a Moderator
King of Men
Member
Member # 6684

 - posted      Profile for King of Men   Email King of Men         Edit/Delete Post 
You need to think iteratively. Suppose you are making the second node of the chain; what needs to happen to the first one?
Posts: 10645 | Registered: Jul 2004  |  IP: Logged | Report this post to a Moderator
Bokonon
Member
Member # 480

 - posted      Profile for Bokonon           Edit/Delete Post 
quote:
Originally posted by MrSquicky:
It's important to keep in mind that a linked list should generally also end (i.e. have its last node pointing to nothing).

This ties in with my suggestion to explicitly initialize your struct values/pointers (for this exercise, until you understand it). If you don't, your assumptions can be wrong.

-Bok

Posts: 7021 | Registered: Nov 1999  |  IP: Logged | Report this post to a Moderator
Blayne Bradley
unregistered


 - posted            Edit/Delete Post 
code:
List::List( /* in */ const char dataLine[] )
{
Node* current;

front = new Node;
front->item = dataLine[0];


int temp = strlen(dataLine);

for ( int counter = 1; counter < temp; counter++)
{

current = front;

Node* newPtr;
newPtr = new Node;

newPtr->item = dataLine[counter];

*while ( current->next != NULL )
{
// stuff
current = current->next;

}

current->next = newPtr;


cout << newPtr->item << endl;

}

}

k with KoM guiding me and helping me understand this I have rewritten my code but it says when I run it that there is an unhandled exception at some place in memory access vilation reaing location some place in memory.

At the * line, this is with the array [ 'a', 'b', 'c', 'd' ] being passed.

IP: Logged | Report this post to a Moderator
fugu13
Member
Member # 2859

 - posted      Profile for fugu13   Email fugu13         Edit/Delete Post 
Are you intializing Node->next to NULL in the Node constructor? If not, there's no guarantee that an uninitialized pointer will have a particular value. Its just some (essentially random) memory location, which can vary depending on implementation and the state of your computer.

Also, your code still has logic problems. I believe it will work, but its doing things in an extremely circuitous fashion.

Posts: 15770 | Registered: Dec 2001  |  IP: Logged | Report this post to a Moderator
Nighthawk
Member
Member # 4176

 - posted      Profile for Nighthawk   Email Nighthawk         Edit/Delete Post 
It's confusing, and it's extremely inefficient to determine the end of the list each iteration. Best to keep track of what the last node is. I explain through code...

(Code omitted...)

[ March 31, 2007, 04:54 PM: Message edited by: Nighthawk ]

Posts: 3486 | Registered: Sep 2002  |  IP: Logged | Report this post to a Moderator
Will B
Member
Member # 7931

 - posted      Profile for Will B   Email Will B         Edit/Delete Post 
Nighthawk, I ask you to consider removing your post. Using your code for his assignment would be cheating, and I don't think that was Blayne's intent. We should make it easy for him to stay on the straight and narrow!

Blayne, how did it work out when you drew a diagram of what was happening, and walked thru the code?

The Wikipedia entry has some examples of this approach. http://en.wikipedia.org/wiki/Linked_list

Posts: 1877 | Registered: Apr 2005  |  IP: Logged | Report this post to a Moderator
Nighthawk
Member
Member # 4176

 - posted      Profile for Nighthawk   Email Nighthawk         Edit/Delete Post 
Sorry about that... I have a tendency of better describing things through code. The disadvantage of being self-taught as opposed to going through a curriculum is that sometimes it's hard explaining things using the same terms as those instructed.
Posts: 3486 | Registered: Sep 2002  |  IP: Logged | Report this post to a Moderator
Will B
Member
Member # 7931

 - posted      Profile for Will B   Email Will B         Edit/Delete Post 
No problemo.
Posts: 1877 | Registered: Apr 2005  |  IP: Logged | Report this post to a Moderator
Nighthawk
Member
Member # 4176

 - posted      Profile for Nighthawk   Email Nighthawk         Edit/Delete Post 
Let me try to explain then...

You have to keep two variables: where you started and where you are.

Knowing where you are allows you to not have to plow through the array from the beginning every time you have to add something to the end. Most linked list implementations in data structures, such as queues, maintain the concept of a "head" and a "tail". You add on to the "tail", and remove from the "head" (or vice-versa).

Also, it's a bad idea to initialize the variable with the first character in "dataLine": what if there is none and the string is zero length? For that matter, your last implementation is one off because you're using "strlen", but not taking in to consideration the character you already initialized with.

Posts: 3486 | Registered: Sep 2002  |  IP: Logged | Report this post to a Moderator
King of Men
Member
Member # 6684

 - posted      Profile for King of Men   Email King of Men         Edit/Delete Post 
You're right about the inefficiency, but I thought it valuable to learn how to iterate through a linked list to get to the end, as a thought exercise. And the non-initialised pointers were indeed what was causing the problem.

Edit: And he is indeed taking into account the character he's used, that's why the loop begins at 1. Though your point about empty strings is well taken.

Posts: 10645 | Registered: Jul 2004  |  IP: Logged | Report this post to a Moderator
   

   Close Topic   Feature Topic   Move Topic   Delete Topic next oldest topic   next newest topic
 - Printer-friendly view of this topic
Hop To:


Contact Us | Hatrack River Home Page

Copyright © 2008 Hatrack River Enterprises Inc. All rights reserved.
Reproduction in whole or in part without permission is prohibited.


Powered by Infopop Corporation
UBB.classic™ 6.7.2