Я предполагал, что 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 не может просто "забыть" свой заголовок .next и header.previous?
Исходный код в версии, которую я смотрю (build 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).
хотя меня не очень впечатлила причина оптимизации GC - это явно отразилось на вашем случае -
очистка и повторное использование LinkedList
что звучит не так. почему бы просто не создать новый объект LinkedList?
Так как я не могу прокомментировать ответы (?): указатели между следующим и предыдущим не имеют значения. Поскольку ни одна из внутренних записей не будет доступна из любого корня GC, будет собрана вся структура. Если бы java использовал сборщик refcounting, мы бы столкнулись с проблемой цикла.
Правильные ответы - это то, что отмечает Джон Скит.