4
\$\begingroup\$

So I'm implementing a linked list in Java, and so far it looks like this:

public class List <T> {

    private class Node {
        T value;
        Node next;
    }

    private Node node_at(int n) {
        Node seeker = front;
        for (int i = 0; i < n; i++) {
            seeker = seeker.next;
        }
        return seeker;
    }

    Node front;
    int length;

    public int length() {
        return length;
    }

    public void insert(int index, T o) {
        if (index == 0) {
            Node n = new Node();
            n.value = o;
            n.next = node_at(0);
            front = n;
        } else {
            Node n1 = node_at(index-1);
            Node n2 = new Node();
            n2.next = n1.next;
            n1.next = n2;
            n2.value = o;
        }
        length++;
    }
    public void append(T o) {
        Node n = node_at(length);
        n.value = o;
        n.next = new Node();
        length++;
    }
    public void append(List<T> l) {
        node_at(length-1).next = l.front; // specific area of interest
        length += l.length;
    }

    public T at(int n) {
        Node seeker = node_at(n);
        return seeker.value;
    }

    List() {
        length = 0;
        front = new Node();
    }
}

The line that I marked specific area of interest is effectively cutting off a node (the last node in the receiver), leaving it homeless. Is that node going to get garbage collected?

\$\endgroup\$
2
\$\begingroup\$

Yes, in theory. That depends on when the garbage collector decides to run. (There are lots of great explanations about how finicky it is on Stack Overflow.) But it will become eligible for garbage collection and is gone for all intents and purposes. Data becomes eligible for garbage collection when no references to it exist, and, assuming node_at(length-1).next is the only reference to it, the Node then qualifies once you change that reference.

\$\endgroup\$
  • \$\begingroup\$ What would happen if I had 100 or so items in my list, and then I did front = new Node();? Would it take a long time for the GC to find all the objects and destroy them since the last element wouldn't become eligible for destruction until every other element before it was destroyed? And if so is there a better way for me to delete the contents of my list? \$\endgroup\$ – Michael Dorst Sep 26 '13 at 23:57
  • \$\begingroup\$ @anthropomorphic The GC in general is pretty smart. My guess would be that it would immediately "know" that all 100 of those Nodes were "dead", but I don't know for sure. It also wouldn't bother even attempting to reclaim the memory until the memory was needed, or if the JVM was just hanging out, not doing much, with spare clock cycles. Haha \$\endgroup\$ – asteri Sep 27 '13 at 0:00
  • \$\begingroup\$ @anthropomorphic Actually, here's a SO question about exactly that. \$\endgroup\$ – asteri Sep 27 '13 at 0:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.