Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Toadhead

Linked Lists (C++ Programming)

This topic is 5217 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've readed more posts about this and still doesn't understand it. Here's a code I found:
void add_node_at_end ()
  {  node *temp, *temp2;   // Temporary pointers


     // Reserve space for new node and fill it with data

     temp = new node;
     cout << "Please enter the name of the person: ";
     cin >> temp->name;
     cout << "Please enter the age of the person : ";
     cin >> temp->age;
     cout << "Please enter the height of the person : ";
     cin >> temp->height;
     temp->nxt = NULL;

     // Set up link to this node

     if (start_ptr == NULL)
         start_ptr = temp;
     else
       { temp2 = start_ptr;
         // We know this is not NULL - list not empty!

         while (temp2->nxt != NULL)
           {  temp2 = temp2->nxt;
              // Move to next link in chain

           }
         temp2->nxt = temp;
       }
  }

The "nxt" of the new node were temp points to will be set to NULL by "temp->nxt = NULL;" But.. were in this code will it pointed to the next node? Here:
 
while (temp2->nxt != NULL)
           {  temp2 = temp2->nxt;
              // Move to next link in chain

           }
         temp2->nxt = temp;
While temp2's "nxt" pointer is NOT NULL, it will move forward in the linked list until it reach a node with a next "nxt" pointer, pointed to NULL (end of the list). But how does "temp2 = temp2->nxt;" work, were have I declared that temp2->nxt will move the temp2 pointer one forward????? [edited by - Toadhead on May 8, 2004 9:11:36 AM]

Share this post


Link to post
Share on other sites
Advertisement
You use the loop to advance through the list, so when you end temp2 points at the last node. We know it''s the last node because it''s nxt pointer is NULL, meaning there are no more nodes after it.

So now we have to add the new node we made before to the end of the list, that is, after the temp2 one. To do so, we make temp2 to point to the new node as its next one, we only have to change the nxt of temp2, so instead of pointing to NULL, it will point to the new node temp, thus is, linking it.

Share this post


Link to post
Share on other sites
yes, I know HOW "temp2 = temp2->nxt;" works.. but I want to know WHY it works! Were did we say that nxt points to the next node???

[edited by - Toadhead on May 8, 2004 10:34:10 AM]

Share this post


Link to post
Share on other sites
-_-'

It's actually on the next line. temp2->next = temp.



Imagine 2 situations. In the first, only 1 node is in the list. So start_ptr is to the only node in the list. Now we know start_ptr->nxt == NULL, because there's only 1 node.
So the travelling (while-loop) stops (and never ran, because temp2->next == NULL, since temp2 points to start_ptr).
And we point temp2/start_ptr->nxt = temp. (temp is already set up so we only have to point!)



Now we want to add another node, but this time, start_ptr has a nxt. That was the node we added in situation one. So it is now like this:
start_ptr->nxt->(we want to add here)

It's obvious that the while-loop, will go once, because it went 0 times last time. If we unroll the loop:
temp2 = start_ptr; // we start..
temp2 = temp2->nxt; // Stop

So temp2 is:
start_ptr->nxt ->(we want to add here)

So all we do now is: temp2->nxt = temp (new node)

--
You're Welcome,
Rick Wong

- sitting in his chair doing the most time-consuming thing..

[edited by - Pipo DeClown on May 8, 2004 10:53:39 AM]

[edited by - Pipo DeClown on May 8, 2004 10:53:57 AM]

Share this post


Link to post
Share on other sites
thanks for your explainment.. I still don''t get it perfectly..but it will come later. I understand most things now and when I will re-read this code like 1000 times I think I should know how it works

Share this post


Link to post
Share on other sites
actaully i have to read about 1000 times to understand your question as well.please make it clear next time.

as far as the link list goes,temp->next does not move one node forwards.temp = temp->next does!imagine,you have a message to deliver to several people,and you only know the first one who needs the message,and everyone of them only know the next one who needs the message.thats pretty much like a linked list.in your problem,try envision all of sudden your boss tells you there is one guy need the message and you better update the list.what you gonna do?obviously,if you dont know anyone who need the message yet,which means no one is in the list,then the first person need the message is gonna be that new guy.otherwise,you gonna go to the first person and mark down the next person he knows,and go to the next person.keep doing this until someone knows nobody need the message.then tell him "look,this is the new guy need the message,remember him" so now the new guy is in the list.

i hope i didnt make you more confused,i just think making it as a real life example gonna help you understand it quickly.at least this applies to me.

Share this post


Link to post
Share on other sites
Just remember pointers really POINT to memory. And C++ plays with that, so you have total freedom. Love it..

--
You''re Welcome,
Rick Wong

- sitting in his chair doing the most time-consuming thing..

Share this post


Link to post
Share on other sites
wel.. I don't love it since I get stupid errors.. >

Whats wrong with this code, when I run the program I get an error from windows and I need to close the program:


#include <iostream>
using namespace std;

struct node
{
int x;
node *next;
};

void add();
void output1();

node *start = NULL;








int main()
{
int x;

loop1:

cout<<"1.) Add a node to list"<<endl<<"2.) Output complete list"<<endl<<"3.) Quit program"<<endl<<endl;
cin>>x;

switch (x)
{
case 1:
add();
goto loop1;
break;
case 2:
output1();
goto loop1;
break;
case 3:
return 0;
break;
default:
cout<<"Wrong input"<<endl;
goto loop1;
break;
}


return 0;
}











void add()
{
int y;
node *temp, *current;

temp = new node;
cout<<endl<<"What is y?"<<endl;
cin>>y;
cout<<endl<<endl;
temp->x = y;
temp->next = NULL;

if (start=NULL)
start = temp;

else
{
current = start;

while (current != NULL)
{
current = current->next;
}
current = temp;
}

}




void output1()
{

node *temp2;
temp2 = start;

if (start == NULL)
cout<<endl<<"No node's in the list!"<<endl<<endl;

else
{
while (temp2 != NULL)
{
cout<<temp2->x<<endl;
temp2 = temp2->next;
}
}

Please help me and tell me what I'm doing wrong.
thanks!

[edited by - Toadhead on May 9, 2004 9:09:39 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Pipo DeClown
You wrote = instead of == in some of the if-statements.

--
You''re Welcome,
Rick Wong

- sitting in his chair doing the most time-consuming thing..



yeah.. I know, but I already changed that.
It''s still not working!
(I edited the code so please look again )

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!