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

Question

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

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

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

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

РЕДАКТИРОВАТЬ: Даже если у нас есть указатель на узел, мы должны начать с головы только правильно?Так как же это постоянное время работы

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

Answer 2

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

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

Answer 3

Вы упускаете суть, я думаю здесь. Это просто ВСТАВКА и УДАЛЕНИЕ, которые имеют постоянное время, а не также нахождение точки вставки или удаления! Время постоянно, потому что вам просто нужно установить ссылки (ссылки) на предыдущий и следующий элемент в списке - тогда как, например, с ArrayList, в случае вставки вам нужно выделить память для (как минимум) еще одного элемента и перенести существующие данные во вновь выделенный массив (или, удалив, вам придется перемещать элементы в массиве после удаления элемента).

Answer 4

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

Кажется, вы пропустили первое предположение.