C Board  

Go Back   C Board > General Programming Boards > C++ Programming

Reply
 
LinkBack Thread Tools Display Modes
Old 11-02-2009, 12:02 PM   #1
Registered User
 
Join Date: May 2009
Posts: 83
Question related to linked lists

Hello, what does this line of code (in bold) do exactly:


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

int main()
{
  node *root;       // This won't change, or we would lose the list in memory
  node *conductor;  // This will point to each node as it traverses the list

  root = new node;  // Sets it to actually point to something
Does it create a new node structure at that point, and point at it with "root"? Or is it only saying to point at any new node structure in the future, which is explicitly created?
And I'm assuming, since its the "new" keyword, that this new object/structure/or-whatever-you-want-to-call-it is created in the "heap" section of memory, correct? Why, then, is there no need for the delete keyword to delete the "root" variable?
Programmer_P is offline   Reply With Quote
Old 11-02-2009, 12:40 PM   #2
and the Hat of Ass
 
Join Date: Dec 2007
Posts: 731
It allocates memory for a new node struct and sets root to point to that newly-allocated node.

It is created on the heap, and you SHOULD delete the root when complete. If you "new" something, consider yourself responsible for "delete"-ing it as well.
rags_to_riches is offline   Reply With Quote
Old 11-02-2009, 12:49 PM   #3
Registered User
 
Join Date: May 2009
Posts: 83
Quote:
Originally Posted by rags_to_riches View Post
It allocates memory for a new node struct and sets root to point to that newly-allocated node.

It is created on the heap, and you SHOULD delete the root when complete. If you "new" something, consider yourself responsible for "delete"-ing it as well.
Ok, then....well, it looks like the author of this tutorial (of this site) must have forgot to then, in his example, because he does not delete his root.

Thanks for the reply.
Programmer_P is offline   Reply With Quote
Old 11-02-2009, 12:57 PM   #4
Registered User
 
Join Date: May 2009
Posts: 83
So, does this code look good then?

Programming_Exercises.h:

Code:
struct node {

    string store; //for storing something in the list
    node* next;
    int one;
    int two;
    int three;
    int random;

};
Programming_Exercises.cpp:

Code:
#include <iostream>
#include <string.h>
#include "Programming_Exercises.h"

using namespace std;


int main() {

  node* root; //This will be the unchanging first node
  node* conductor; //This will point to each node as it traverses the list

  root = new node;
  //Assisn values:
  root->next = 0; //otherwise it wont work well
  root->store = "This program tests a linked list.\n\nYes, it tests a linked list.";
  root->one = 1;
  root->two = 2;
  root->three = 3;
  root->random = 4;

  conductor = root; //The conductor points at the first node

  if (conductor != 0 ) {
      while (conductor->next !=0) {
        cout<< conductor->store;
        cout<< conductor->one <<", " << two << ", " << three << ", " << random <<endl;
        conductor->random = 5;
        cout<< conductor->random;
        conductor = conductor->next;
      }
      cout<< conductor->store;
  }
  conductor->next = new node; //creates a node at the end of the list
  conductor = conductor->next; //Points to that node
  conductor->next = 0; //Prevents it from going further
  conductor->store = "Conductor just accessed the list, changed the contents of the string...\n\nTest completed \"
                    "successfully. Thank you for trying this program";
  cout<< conductor->store;
  delete[] root;

  return 0;

}
I would have used delete on the conductor->next too, since it also uses new, but I didn't think I needed to, since it is a member variable of the node struct, and the object of that node struct (root) was deleted. Is that fine, or do I need to explicitly delete conductor->next too?
Programmer_P is offline   Reply With Quote
Old 11-02-2009, 02:03 PM   #5
and the Hat of Ass
 
Join Date: Dec 2007
Posts: 731
If you new it, you should delete it. The memory allocated by new is returned to the operating system upon exit of the program, so strictly speaking the author is not incorrect in the provided, simple example. However, it is GOOD FORM AND PRACTICE to clean up after yourself!

You must use the array delete operator -- delete [] -- only on arrays, not on pointers to non-array objects. root is a node object, and therefore should not be deleted as if it were an array, it should be deleted with delete root. Any nodes under root ARE NOT DELETED simply by deleting root. To properly clean up you must traverse the list node by node and delete each one.

Your while loop will not be entered, as you've not added anything to the list.
rags_to_riches is offline   Reply With Quote
Old 11-02-2009, 02:17 PM   #6
Registered User
 
Join Date: May 2009
Posts: 83
Quote:
Originally Posted by rags_to_riches View Post
If you new it, you should delete it. The memory allocated by new is returned to the operating system upon exit of the program, so strictly speaking the author is not incorrect in the provided, simple example. However, it is GOOD FORM AND PRACTICE to clean up after yourself!
My understanding of new is the memory allocated by new is NOT returned to the operating system on exit of the program...hence the need to explicitly delete each new object with delete. Is this not the case?
Quote:
You must use the array delete operator -- delete [] -- only on arrays, not on pointers to non-array objects. root is a node object, and therefore should not be deleted as if it were an array, it should be deleted with delete root. Any nodes under root ARE NOT DELETED simply by deleting root. To properly clean up you must traverse the list node by node and delete each one.
Ok, thank you. That answers my question concerning if next would be deleted automatically, because I deleted root.
Quote:
Your while loop will not be entered, as you've not added anything to the list.
Right. I figured that, but I wasn't sure at first how to add something to the list. I now see I will probably need to create a new instance of the "node" struct, thereby adding a new node to the list. Of course, obviously, I would need to point next at that new node (and take the next = 0 stuff out). At least, that's the way I understand it..

Thanks for the replies.
Programmer_P is offline   Reply With Quote
Old 11-02-2009, 03:06 PM   #7
Registered User
 
Join Date: May 2009
Posts: 83
Ok, this is ridiculous...
Each new (NOT the keyword new) node I try to create has to be pointed at something, so I don't leave any hanging pointers, or initialized to a NULL (0) value, but the problem is the while loop will NEVER be entered no matter what, because the condition (conductor->next != 0) will never be met, because its always going to have a NULL value...

For example, I have pointers *x and *y: I point *x AT *y...so what does y get pointed at? Nothing! And so I say y = 0. Only problem is I said (figuratively), "You can only enter this while loop while *x does NOT equal 0". And so, unfortunately, even though x = y, y = 0, and so x = 0.

So how do I solve the problem? Use some other condition?

I guess I don't understand why the author of that tutorial put that condition in there in the first place.

(To translate: I attempted to create a new node (naming it secondNode, by convention), and assign it 0 -- so, node* secondNode = 0; I then did:
root->next = secondNode;

Now, the problem...

if (conductor != 0) {
while (conductor->next != 0) {
//Do stuff
}


Since conductor->next (keep in mind "next" is a node pointer in the node struct) is pointing at secondNode (another pointer, which has been initialized to 0), the condition is not met, and so it can't enter the while loop. )

Last edited by Programmer_P; 11-02-2009 at 03:17 PM.
Programmer_P is offline   Reply With Quote
Old 11-02-2009, 03:15 PM   #8
Registered User
 
Join Date: Sep 2004
Location: California
Posts: 2,845
Quote:
Originally Posted by Programmer_P
because the condition (conductor->next != 0) will never be met, because its always going to have a NULL value...
That's not true if your list has more than one node...

Code:
// Create a linked list that is 3 nodes in length
node* conductor = new node;
node* second = new node;
node* third = new node;

conductor->next = second;
second->next = third;
third->next = NULL;

while(conductor->next != NULL)
    ...
__________________
bit∙hub [bit-huhb] n. A source and destination for information.
bithub is offline   Reply With Quote
Old 11-02-2009, 03:21 PM   #9
Registered User
 
Join Date: May 2009
Posts: 83
Oh...I see. I need the new keyword still.

Thanks!
Programmer_P is offline   Reply With Quote
Old 11-02-2009, 04:00 PM   #10
Senior software engineer
 
brewbuck's Avatar
 
Join Date: Mar 2007
Location: Portland, OR
Posts: 5,381
Quote:
Originally Posted by Programmer_P View Post
My understanding of new is the memory allocated by new is NOT returned to the operating system on exit of the program...hence the need to explicitly delete each new object with delete. Is this not the case?
Considering that just about every program out there has a few memory leaks in it, how could your computer ever stay up for more than a few minutes if the OS did NOT clean up the mess?
__________________
"Congratulations on your purchase. To begin using your quantum computer, set the power switch to both off and on simultaneously." -- raftpeople@slashdot
brewbuck is offline   Reply With Quote
Old 11-02-2009, 04:12 PM   #11
Registered User
 
Join Date: May 2009
Posts: 83
Quote:
Originally Posted by brewbuck View Post
Considering that just about every program out there has a few memory leaks in it, how could your computer ever stay up for more than a few minutes if the OS did NOT clean up the mess?
Very true. I didn't think of that.
But, then again...I'm sure its best to follow the "delete every new object" rule.
Some OSes are probably coded worse than others though...I'm sure Windows, for example, probably does a poorer job of cleaning up than any other OS.
Programmer_P is offline   Reply With Quote
Old 11-03-2009, 08:27 PM   #12
Ex scientia vera
 
Join Date: Sep 2007
Posts: 426
Quote:
Originally Posted by Programmer_P View Post
Very true. I didn't think of that.
But, then again...I'm sure its best to follow the "delete every new object" rule.
Some OSes are probably coded worse than others though...I'm sure Windows, for example, probably does a poorer job of cleaning up than any other OS.
Of course it's good practice. If you do it right, you will be cleaning up after yourself as soon as you are finished using the memory. Sure, the memory is returned to the system at some point, but why should your program be using more resources than it has to?

Without having any proof or benchmarks or anything similar, I have to say that particularly vista is unbelievably slow at cleaning up memory upon the execution of a big program. I see this even on new installations.
__________________
"What's up, Doc?"
"'Up' is a relative concept. It has no intrinsic value."
IceDane is offline   Reply With Quote
Reply

Thread Tools
Display Modes

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Question About Linked Lists Example bengreenwood C Programming 6 08-07-2009 11:45 AM
Question regarding comparing two linked lists cyberfish C++ Programming 2 08-23-2007 04:28 AM
Singly Linked Lists: Clarification Needed jedispy C++ Programming 4 12-14-2006 05:30 PM
Linked Lists Question panfilero C Programming 4 11-22-2005 01:33 AM
Linked Lists Question SlyMaelstrom C++ Programming 12 11-12-2005 12:03 PM


All times are GMT -6. The time now is 01:35 PM.


Powered by vBulletin® Version 3.8.1
Copyright ©2000 - 2009, Jelsoft Enterprises Ltd.
Search Engine Optimization by vBSEO 3.3.0 RC2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22