CODEWITHSUNDEEP
javalinked-listgarbage-collection
Faraz
Faraz

Reputation: 6285

Garbage Collection in Custom Linked List

Let's say this custom singly-linked Linked List has the following data;

1 2 3

I want to remove the first element (which happens to be 1). For this, I just move the first pointer to the next like so ->

first = first.next;

Now, nothing is pointing the node that contains '1', but it is pointing to some node (in this case, a node that contains a value '2').

Would the node that contains '1' which I delinked from the list ever be garbage collected?

This is the full implementation:

public class LinkedList<E> {
    
   private Node<E> first;
   private Node<E> last;

   public E removeFromFront() {
       if(isEmpty()) {
           System.out.println("List is empty");
           return null;
       }
       E data = first.data;
       if(first == last) {
           first = last = null;
       } else {
           first = first.next;
       }
       return data;
   }

Upvotes: 0

Views: 185

Answers (1)

rzwitserloot
rzwitserloot

Reputation: 103823

Of course.

Java has a complete garbage collector, and not some imperfect approximation thereof. No 'ARC' (Automatic reference counting, which cannot deal with loops; used by e.g. Apple's ObjC implementation and I think Swift).

The garbage collector acts as if it works like this:

  • Take all 'entry points'. This starts with all classloaders in current usage, all threads, and every method anywhere on the stack in any of those methods.
  • Then take all classes themselves (not the instances of it, just the class; this doesn't matter unless you have static fields in em) from those classloaders, and all local variables (including the 'this' reference, and all parameters) from all those methods on all stacks.

Those are not garbage.

Then, start going through all the not-garbage and fan out: Find everything it can reference directly. That's not garbage either. Keep going: fan out from the newly found not-garbage to find more not-garbage. When there's no more non-garbage to find, declare that everything else is garbage, and clean it up at some point (note that it is impossible for garbage to turn itself into not-garbage, so there's no need to do it right away).

In this case, no static field or any active code has a reference to what used to be the first node object, so that is garbage, and the things you can reach given this garbage instance are completely irrelevant. Those references aren't looked at; whatever is reachable from garbage doesn't matter at all.

NB: Actual garbage collectors work quite differently. But they act like they work as above; if they didn't, they aren't a valid implementation of the garbage collector spec. So, they bring in generational concepts, and may use refcounting for hints, but in your described scenario, first is treated as garbage, no matter which impl of the garbage collector you are using.

Upvotes: 1

Related Questions