CODEWITHSUNDEEP
javabig-o
Leri
Leri

Reputation: 263

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

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 ?

Upvotes: 26

Views: 1527

Answers (3)

irreputable
irreputable

Reputation: 45433

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?

Upvotes: 3

Marcus Fr&#246;din
Marcus Fr&#246;din

Reputation: 12882

Since I can't seem to be able to comment on answers (?): The pointers between next and previous doesn't matter. Since none of the internal entries will be accessible from any GC root, the whole structure will be collected. Had java used a refcounting collector, we'd be stuck with the cycle problem.

The correct answers is what John Skeet notes.

Upvotes: 0

Jon Skeet
Jon Skeet

Reputation: 1500225

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).

Upvotes: 33

Related Questions