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 ?

http://www.docjar.com/html/api/java/util/LinkedList.java.html Harmony has it O(1) — Bozho, Mar 01 '11 at 22:14
Good explanation you can find here: http://stackoverflow.com/questions/575995/clear-impl-in-javas-linkedlist. Answered by Jason — lukastymo, Mar 01 '11 at 22:49

score 32 · Accepted Answer · answered Mar 01 '11 at 22:15

32

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

answered Mar 01 '11 at 22:15

Jon Skeet

1,421,763
867
9,128
9,194

The only solution I see to that problem would be to extend the class with a custom clear method. Not that hard to get right (you can peek at the original implementation after all and just remove the iteration), but still not something I'd like to do. Bad API design imho. – Voo Mar 05 '11 at 03:42

score 3 · Answer 2 · answered Mar 01 '11 at 23:03

3

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?

answered Mar 01 '11 at 23:03

irreputable

44,725
9
65
93

An existing reference to one of the Entry nodes partially through the old list will continue to see the old list, and will continue to be able iterate through it. (This is related to the second part of the comment, and has nothing to do with GC.) – Oddthinking Mar 02 '11 at 02:11
You're right that creating a new LinkedList here would just get rid of the entire problem. In the end I actually switched to an ArrayList, whlle clear() there is O(N) , we still measured it to perform better, for our specific case, garbage collecting our linked list produced abour 150-200Mb/sec garbage alone just from the internal linked list nodes (Normally we wouldn't care about stuff like that, but for this particular app we have to) – Leri Mar 02 '11 at 19:02
indeed for this one that seems true. I was just defending at least part of the reasoning provided by the comment. – Oddthinking Mar 03 '11 at 13:08
there are many reasons to keep the same LinkedList and use clear() (otherwise why would clear be introduced?), one of the reasons is for using "final" constant reference. Another reason is if you ever have getLinkedList() in your class, and this class switches the reference under you, you could introduce lots of bugs. – vtlinh Aug 19 '15 at 18:36

score 0 · Answer 3 · answered Mar 01 '11 at 22:20

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.

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

3 Answers3

Linked