Почему не LinkedList.Clear () O (1)

Question

Я предполагал, что LinkedList.Clear () был O (1) в проекте, над которым я работаю, так как я использовал LinkedList, чтобы истощить BlockingQueue в моем потребителе, который нуждается в высокой пропускной способности, очистив и повторно использовав LinkedList впоследствии.

Оказывается, что предположение было неверным, поскольку код (OpenJDK) делает это:

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

Это было немного удивительно, есть ли веская причина, по которой LinkedList.Clear не мог просто "забыть" свои header.next и header.previous член?

Answer 1

Исходный код в версии, которую я смотрю (сборка 1.7.0-ea-b84) в Eclipse, имеет следующий комментарий над ними:

// 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

Это дает достаточно ясное объяснение, почему ониделая это, хотя я согласен, что немного тревожно, что он превращает операцию O (1) в O (n).

Answer 2

, хотя причина оптимизации GC меня не впечатлила - в вашем случае это явно имеет неприятные последствия -

очистка и повторное использование LinkedList

это не звучит правильно. почему бы просто не создать новый объект LinkedList?

Answer 3

Поскольку я не могу комментировать ответы (?): Указатели между следующим и предыдущим значения не имеют. Поскольку ни одна из внутренних записей не будет доступна из любого корня GC, будет собрана вся структура. Если бы java использовал сборщик пересчёта, мы застряли бы с проблемой цикла.

Правильные ответы - это то, что отмечает Джон Скит.