Why can't the Nodes be linked together?

Question

EDIT: Is it possible to NOT use new? (do not dynamically allocating memory)

I think it is push that is wrong, but I don't know where, how, and why. here is the code:

struct Node {
    string fileName;
    Node *link;
};
int size(Node *&flist) {
    int count = 0;
    Node *tempPtr = flist;
    while (tempPtr != 0) {
     count += 1;
     tempPtr->link = (tempPtr->link)->link;
    }
    return count;
}
Node* push(Node *&flist, string name) {
    Node temp;
    Node *tempPtr = &temp;
    temp.fileName = name;
    temp.link = flist;
    cout << tempPtr->fileName << endl;
    cout << (tempPtr->link)->fileName << endl;
    return tempPtr;
}
int main( int argc, char *argv[] ) {
        Node aNode;
    Node *flist = &aNode;
    flist->fileName = "a";
    flist->link = NULL;
    push(flist, "b");
    int s = size(flist);
    cout << "size: " << s << endl;
}

the output is

b
a
size: 0

Thank you.

Answer 1

Well, your size() function is a little overkill. You might try

int size(Node *flist) {
    int count = 0;

    Node *tempPtr = flist;
    while (tempPtr) {
        count += 1;
        tempPtr=tempPtr->link;
    }

    return count;
}

I've removed an extraneous exit condition from the while statement that prevented calculation of the length of lists that have only one element.

The reason it's returning 0 in your version is that your while statement:

while ((tempPtr != 0) &&(tempPtr ->link != 0)) {
        count += 1;
        tempPtr->link = (tempPtr->link)->link;
    }

never executes since your one node has a .link value of null (0). Try the modified version I provided above.

Oh, in the future, you might want to tag these sorts of posts as "homework." You'll get better responses.

Answer 2

In your size() function you are modifying the list in the loop. You don't want to modify tempPtr->link but rather just change tempPtr as you iterate. Changing tempPtr won't modify anything permanently. You should also avoid passing flist by reference here as there's no need to modify it. So:

int size(Node *flist) {
    int count = 0;
    Node *tempPtr = flist;
    while (tempPtr != 0) {
        count += 1;
        tempPtr = tempPtr->link;
    }
    return count;
}

As for push(), the biggest problem is that you're allocating the new node as a local variable which means it'll be on the stack and will get destroyed when the function returns. To create a node that is more permanent you need to allocate it on the heap using the new operator. And again the '&' for flist is unnecessary:

Node* push(Node *flist, string name) {
    Node *tempPtr = new Node;
    tempPtr->fileName = name;
    tempPtr->link = flist;
    cout << tempPtr->fileName << endl;
    cout << tempPtr->link->fileName << endl;
    return tempPtr;
}

Note that the counterpart to new is delete. Since the new nodes are allocated on the heap they will not be destroyed automatically so you will need to manually delete them when you are done with the list. Your goal is to have one delete for every new, so if you new 5 nodes your code should delete 5 nodes when it cleans up. If you don't do this your program will run fine but it will have a small memory leak.

(Actually, when it exits all allocated memory is automatically freed. But it's a bad habit to allocate memory and never free it, in general, so you should pretend this automatic cleanup doesn't happen.)

Answer 3

You need to use new. Otherwise the variable temp is destroyed at the end of the push function. Later, if you try to access what that pointer pointed to, it will be GONE.