Question related to linked lists

This is a discussion on Question related to linked lists within the C++ Programming forums, part of the General Programming Boards category; Hello, what does this line of code (in bold) do exactly: Code: struct node { int x; node *next; }; ...

  1. #1
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827

    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?

  2. #2
    a_capitalist_story
    Join Date
    Dec 2007
    Posts
    2,655
    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.

  3. #3
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    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.

  4. #4
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    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?

  5. #5
    a_capitalist_story
    Join Date
    Dec 2007
    Posts
    2,655
    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.

  6. #6
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    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?
    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.

  7. #7
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    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.

  8. #8
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,262
    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.

  9. #9
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Oh...I see. I need the new keyword still.

    Thanks!

  10. #10
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,272
    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?
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  11. #11
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    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.

  12. #12
    Ex scientia vera
    Join Date
    Sep 2007
    Posts
    478
    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."

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Question About Linked Lists Example
    By bengreenwood in forum C Programming
    Replies: 6
    Last Post: 08-07-2009, 12:45 PM
  2. Question regarding comparing two linked lists
    By cyberfish in forum C++ Programming
    Replies: 2
    Last Post: 08-23-2007, 05:28 AM
  3. Singly Linked Lists: Clarification Needed
    By jedispy in forum C++ Programming
    Replies: 4
    Last Post: 12-14-2006, 05:30 PM
  4. Linked Lists Question
    By panfilero in forum C Programming
    Replies: 4
    Last Post: 11-22-2005, 01:33 AM
  5. Linked Lists Question
    By SlyMaelstrom in forum C++ Programming
    Replies: 12
    Last Post: 11-12-2005, 12:03 PM

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