В Java, почему вставка или удаление в объединенном списке является постоянной операцией времени? Разве это не вводит в заблуждение?

Вставка или удаление элемента в определенной точке списка, предполагая, что у нас есть указатель на node, уже является операцией с постоянным временем. - from Статья Википедии о Связанном списке

Обход связанного списка в одном связанном списке всегда начинается с головы. Мы должны продолжать идти, пока не удовлетворим данному условию.

Таким образом, любая операция будет выполняться в худшем случае O (n), если мы не имеем дело с головкой node.

Мы НЕ МОЖЕМ ПРЯМО СЕЙЧАС перейти к указанному указателю в связанном списке. Так почему же он сказал, что это операция с постоянным временем?

EDIT: Даже если у нас есть указатель на node, мы должны начинать с головы только вправо? Итак, как работает постоянное время работы

Ответ 1

Первая из: LinkedList, реализованная в Sun JDK, фактически имеет ссылку на последний элемент, а также на первый элемент (там только запись head, но head.previous указывает на последний элемент). Это означает, что даже в худшем случае переход по списку к элементу, указанному индексом, должен занимать n/2 операции. Это также двойной список.

Кроме того: вставка в начало или конец LinkedList тривиально O (1), потому что вам не нужно перемещать все элементы.

Вставка/удаление в другом месте зависит от того, как именно вы это делаете! Если вы используете Iterator (ListIterator для добавления), то операция может быть O (1), так как Iterator уже будет иметь ссылку на соответствующую запись.

Если вы используете add(int, E) или remove(int), то LinkedList должен найти соответствующую запись (O (n)), а затем удалить элемент (O (1)), поэтому вся операция будет O (n).

Ответ 2

Вы сами сказали: "Предположим, что у нас есть указатель на node уже". Это позволяет избежать обхода, который вы определяете как причину линейного времени.

По общему признанию, текст Википедии немного неоднозначен, так как есть два задействованных узла: тот, который вставлен, и тот, который в списке, куда его вставить.

Ответ 3

", предположив, что мы уже имеем указатель на node, является операцией с постоянным временем"

Вы пропустили первое предположение, похоже.

Ответ 4

Вам не хватает точки, о которой я думаю здесь. Просто INSERTION и DELETION имеют постоянное время, а не нахождение точки вставки или удаления! Время является постоянным, потому что вам просто нужно установить ссылки (ссылки) на предыдущий и следующий элементы в списке - тогда как, например, с ArrayList, в случае вставки вам нужно выделить память (по крайней мере) еще один элемент и переносить существующие данные в вновь выделенный массив (или с удалением вы должны перемещать элементы в массиве вокруг, как только вы удалили элемент).