1

I'm not sure if this question has been asked before ( searched through SOF and couldn't find an answer)

I wrote a LinkedList class and a function to reverse it.The function as follows,

    struct LinkedList::element* LinkedList::recurrsiveReverseList(element* head){
     element* tempList;
     if(head->next == NULL){
        return head;
     }else{
        tempList = recurrsiveReverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return tempList;        
    }
   }

here I am declaring a local pointer variable and making some changes to it and returning it back to the caller. In C++, when I declare a local variable inside a function the scope exists only inside the function. Now when I return the pointer from the function how does it work? I am able to understand the logic and get the result (luckily) but I am not able to completely understand the working here.

Can somebody clear my doubt?

Improve this question
6
  • As a side note, the first struct keyword in your code snippet is completely unnecessary. Commented Aug 23, 2011 at 3:36
  • 1
    Nice function. I would put if(head == NULL || head->next == NULL) { Commented Aug 23, 2011 at 3:47
  • @seth Carnegie: Yes you are right. The struct was not needed. But how does the compiler ignore it? I mean when I am returning an object/pointer to a class I don't mention the keyword 'class' in the function definition (if I do, wouldn't it throw an error? ). But how come it ignores the struct keyword? Commented Aug 23, 2011 at 3:52
  • @sje397: I think to check the head with NULL wouldn't be necessary. When I am iterating through and reach the last node I would only want to check if the next node is NULL or not to pass on the recurrsion to it. No need to check if Head is NULL. Commented Aug 23, 2011 at 3:57
  • 1
    @Ajai yes you do need to check that head is NULL and not just head->next because people could call the function with NULL in the first place and cause a segfault. Commented Aug 23, 2011 at 3:58

5 Answers 5

Reset to default
2

The scope of tempList terminates when you exit the function but tempList is a pointer to a block of memory whose scope does not terminate there because it's been undoubtedly allocated by new. Memory allocated in such a way is valid right up until the point you delete it, regardless of how many functions you go in to or out of.

By passing the pointer back to the caller, it preserves said pointer elsewhere, where you can use it.

A simple example:

static char *fn (void) {
    char *rv = new char[42];
    return rv;
}

int main (void) {
    char *x = fn();
    delete [] x;
    return 0;
}

In the code above, the scope of rv is limited to the fn function after it's declared.

The scope of x is limited to the main function after it's declared.

However the memory allocated by new comes into existence within fn and continues to exist after returning to main. The address of said memory, initially stored in rv, is transferred to x by the assignment of the fn return value to x.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

That's interesting. So you are saying that if I allocate a new object inside a function through MyClass *obj = new MyClass(), and return obj from the function, obj will still be valid all through the program until someone deletes it, just because it was assigned through new? Won't the same hold if I create it like MyClass obj inside and return as return &obj?
2

Not sure if someone else explained it this way, but the pointer itself is nothing more than a number, like... 0x12345678. That number in turn addresses a position in the memory of a computer that contains the actual value you are looking for, which is the linked list node.

So when you return that address, it's okay that the original variable was destroyed. Like copying down a street address to a different piece of paper, then throwing away the original paper. The house that is at the address you have is still there.

Improve this answer

2 Comments

Nice example. Thanks! Could have upvoted but SOF wouldn't let me until I have 15 reputations.
Thanks! And that's no problem~
1

The pointer object tempList ceases to exist when you leave the function. But that's ok; you're returning (a copy of) the value that was stored in the object, not the object itself. It's just like

int n = 42;
return n;

(Returning the address of a local variable is what gets you into trouble.)

Improve this answer

Comments

0

I assume your linked list nodes are allocated on the free store (i.e. with new).

When you create an object with new, it is created on the free store and exists until you call delete on it. You can make as many pointers to that location as you want, and it exists independent of any function calls it may have been made in. So in this function, you are just returning a pointer by value to that location on the free store. The pointer is just a number which is the address of the object, like returning an int by value.

tl;dr: You obviously know you can return local objects by value because a copy is made. In this function, it returns a copy of the pointer which points to a location on the free store which is only destroyed when delete is called with a pointer to that memory location.

As another note, you probably should not return a pointer to the new head of the list but rather take a pointer to the head of the list by reference and change the list through that, so if someone forgets to assign their old head pointer to the one returned by recurrsiveReverseList, things aren't messed up.

Improve this answer

3 Comments

Nice suggestions, but my idea was to generate a temporary reverse list and give it to the user without affecting the existing list (list stored inside the class).
@Ajai that would be pretty inefficient :) If I were you (which I'm not so) I would make efficiency the default and make people work a tiny bit more for inefficiency (something like newlist = oldlist; newlist.reverse())
Hhhhmm make sense.. The user would think that I'm reversing the current whereas in the back I'm creating a new list and giving the user a new one. Either I should separate this function from the class or should make the function record the changes to the list inside the class. Thanks for the note!
0

The scope of usage of tempList variable is limited within the method as its local, but it holds a memory address which is what is returned. The code that call its will receive this memory address, not the variable tempList.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.