clear() impl in Java's LinkedList

Question

I fear this is a really stupid question, but here goes:

Why does the clear method in Java's default LinkedList implementation bother to walk the list and unhook all the nodes? Why not just unhook the header and leave the rest of the list connected -- the GC will get it anyway, no?

Here's the method:

/**
 * Removes all of the elements from this list.
 */
public void clear() {
    Entry<E> e = header.next;
    while (e != header) {
        Entry<E> next = e.next;
        e.next = e.previous = null;
        e.element = null;
        e = next;
    }
    header.next = header.previous = header;
    size = 0;
modCount++;
}

Why walk it? Why not just skip to header.next = header.previous = header;?

Best I can figure is it helps the GC...? This link http://java.sun.com/docs/books/performance/1st_edition/html/JPAppGC.fm.html#997442 sort of suggests that.

TIA...

Answer 1

Their method ensures that even if other code still holds references to particular nodes, the other nodes will be GC'ed.

Otherwise, even a single external reference to one of the nodes would prevent the entire chain from being collected.

Also, other operations in the list might be going on simultaneously (e.g. views through subList() or Collections.unmodifiableList(), iterators), and this ensures that those things perceive the list as "empty" immediately.

Answer 2

IIRC, this was a change made in JDK6 to assist performance of certain (generational) GC algorithms. Often, the List itself and older nodes will be in an older generation than some of the other nodes. The younger generations will get collected more frequently, with the result that young nodes get copied about before it is discovered that all the nodes are garbage.

So it's a minor performance optimisation. Memory performance optimisation is a little odd in that often it's not the code which is causing the problem that is taking the additional time to execute.

Answer 3

I was just speculating on this very issue on my game development blog. Thanks for the answer. I'd argue that node exposure was a questionable design allowance. It's also sketchy that alternate views on the list (iterators and such) would rely on node unlinking to fail-fast. Instead of relying on this side-effect behavior, sub-views on the list should be checking the modification count. In any case, I see why they're stuck with it now.

Answer 4

The source code of java.util.LinkedList at http://developer.classpath.org/doc/java/util/LinkedList-source.html suggests that you can simply set the first and last elements to null.

Of course if you tend to be over protective, you can loop through the whole thing. I personally think that this may be a very expensive task if your list hold several thousands elements.