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?

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.

Originally Posted by rags_to_riches

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.

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?

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.

Originally Posted by rags_to_riches

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?

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.

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.

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. )

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)
    ...

Oh...I see. I need the new keyword still.

Thanks!

Originally Posted by Programmer_P

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?

Originally Posted by brewbuck

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.

Originally Posted by Programmer_P

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.