Why isn't LinkedList.Clear() O(1)

Question

I was assuming LinkedList.Clear() was O(1) on a project I'm working on, as I used a LinkedList to drain a BlockingQueue in my consumer that needs high throughput, clearing and reusing the LinkedList afterwards.

Turns out that assumption was wrong, as the (OpenJDK) code does this:

    Entry<E> e = header.next;     while (e != header) {         Entry<E> next = e.next;         e.next = e.previous = null;         e.element = null;         e = next;     } 

This was a bit surprising, are there any good reason LinkedList.Clear couldn't simply "forget" its header.next and header.previous member ?

Answer 1

The source code in the version I'm looking at (build 1.7.0-ea-b84) in Eclipse have this comment above them:

// Clearing all of the links between nodes is "unnecessary", but: // - helps a generational GC if the discarded nodes inhabit //   more than one generation // - is sure to free memory even if there is a reachable Iterator 

That makes it reasonably clear why they're doing it, although I agree it's slightly alarming that it turns an O(1) operation into O(n).

Answer 2

while I'm not very impressed with the reason of GC optimization - it clearly backfires in your case -

clearing and reusing the LinkedList

that does not sound right. why not just create a brand new LinkedList object?