В 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, в случае вставки вам нужно выделить память (по крайней мере) еще один элемент и переносить существующие данные в вновь выделенный массив (или с удалением вы должны перемещать элементы в массиве вокруг, как только вы удалили элемент).
