2

I'm writing a function to reverse a linked list and at the end my data structure looks like this:

OriginalPointer -> [Obj 1] <- [Obj 2] <- [Obj 3] <- [Obj 4] <- ReversedList

The OriginalPointer is what I passed into the function, and the ReverseList is the pointer I'm returning. In java, once I've returned my ReverseList pointer, does the OriginalPointer get cleaned up by the garbage collection or is that pointer always going to be there? Just curious.

traveh
  • 2,700
  • 3
  • 27
  • 44
yli12313
  • 21
  • 2
  • 1
    There are no "pointers" as you may be familiar with them from C and C++ in Java. Java has *references* which are passed by value to methods. In your example, you have 4 objects, none of which would be garbage collected. Can you provide the code of your method? – Thorn G May 12 '15 at 21:17
  • If nothing is pointing to it it will get collected. Btw: Because you are actually changing the list you could return nothing and just let original pointer point to the last object. – maraca May 12 '15 at 21:17
  • @Tom G thanks for reminding me. It's been a while since I've done Java, having been doing C recently. Under the hood though, I think Java references are pointers. – yli12313 May 12 '15 at 21:30
  • @maraca, that's exactly what I was thinking too... if it's a reference and nothing is pointing to it, then it will get collected. Thanks. – yli12313 May 12 '15 at 21:31
  • Is 'OriginalPointer' a reference to 'Obj 1'? If so, it's not relevant to the garbage collection - the garbage collection does not collect references. It collects objects. If you are asking whether 'Obj 1' will be collected, then the answer is no as long as 'OriginalPointer' or 'Obj 2' are reachable. – traveh May 12 '15 at 22:06
  • Your "original pointer" is I guess a reference of Type `Node` (List Element) given to your reverse function. It therefore lives on the stackframe of your reverse function and the caller. As soon as those code blocks are left, the reference is also unwinded (i.e. not visited by the GC mark phase anymore). (with Inlining and Byte Code Slots it is a bit more complicated than that, but its usually enough to know). – eckes May 12 '15 at 22:18

4 Answers4

0

All objects on java are stored on a heap and those objects are linked together. So when you are reversing your linked lists, all you are doing is changing the reference of the object, one object points to. So lets assume, the heap has 4 objects obj1,obj2, obj3, obj4. All objects contain a nextNode attribute, which tells them the next node. Once you reverse the list, all you are doing is changing this nextNode attribute value for that object. So by default your previous link will be deleted and I don't think anything needs to be up for GC.

Pratik
  • 1,122
  • 8
  • 26
0

GC only collects objects when there are no references to them anywhere in the program. As long as you hold a reference to one of the nodes, either in another node or in a temp, it won't be collected. The 'Original Pointer' you pass in I'm assuming is the list reference variable, and it will still point to the beginning (now end) of your list, unless you change it. Local variables like those are only destroyed when the method they are in is completed and returned from.

GreySage
  • 1,153
  • 19
  • 39
0

Here's your example, in Java syntax:

Node yourList = /* [Obj 1] <- [Obj 2] <- [Obj 3] <- [Obj 4] */;
yourList = reverse(yourList);

You start with four objects in the heap (the four nodes of your list), and one variable on the stack, yourList. This variable holds a reference to Obj 1's location in the heap. When reverse() is called it is handed the reference to Obj 1 and iterates through each object, reversing the list. Finally it returns a reference to Obj 4. The yourList variable is then updated to reference Obj 4. Since Obj 4 in turn references the other objects, none of them will be garbage collected.

All that happens to yourList is its value is updated. It previously stored the location (address) of Obj 1, now it stores the location of Obj 4. The previous value isn't garbage collected, it's overwritten. So after reverse() returns we end up with the same four objects on the heap, and the same one variable on the stack.

dimo414
  • 47,227
  • 18
  • 148
  • 244
0

Java is always pass by value, which means that when you will call doReverce(List<obj> objList) , you will send a value of your pointer as a parameter. Any change you make to your objList will have impact to your original list, unless you clone your list.

GC removes any object from the ram once it is not reachable within your code.

By the end of doReverse, it will remove any reference created there. In this case, it will remove the secondary reference inside the method, but since you have a reference from your main, your list object will still be in the ram. Once you have no references in your object, GC will collect (remove) it. The code I am refering is below. Keep in mind that you don't need to return a pointer of your object, since you already have it.

main()
{
    List<obj> objList = new objList<>;
    doReverse(objList);
}
//By the end of your main GC will collect objList
Community
  • 1
  • 1
Menelaos Kotsollaris
  • 5,776
  • 9
  • 54
  • 68