Thread: 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.

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

Thanks!

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.