На практике добавляется связанный список O (N) или O (1)?

Question

Говорят, что добавление и удаление в связанном списке происходит в постоянное время, то есть O (1), но доступ к элементам происходит во времени, пропорциональном размеру списка, то есть O (N). Мой вопрос заключается в том, как вы можете удалить или добавить какой-либо элемент без его первого перехода? В этом случае это не дополнение или исключение порядка O (N)?

На примере Java, что происходит, когда мы используем API, как это:

    LinkedList stamps = new LinkedList(); 

    stamps.add(new Stamp("Brazil")); 
    stamps.add(new Stamp("Spain")); 
    --- 
    ---- 
    stamps.add(new Stamp("UnitedStates"); //say this is kth element in the list 
    ---- 
    stamps.add(new Stamp("India"); 

Тогда, когда кто-то делает stamps.remove (к), как это может произойти операция в постоянном времени?

Answer 1

Удаление элементов из связанного списка работает в постоянное время, только если у вас есть указатель на фактический узел в списке. Если единственное, что у вас есть, это информация, которую вы хотите удалить «n» -й узел, тогда нет способа узнать, какой из них она есть - в этом случае вам необходимо сначала пройти по списку, что, конечно, O (п).

Добавление, с другой стороны, всегда работает в постоянное время, поскольку оно никоим образом не связано с количеством элементов, уже содержащихся в списке. В приведенном примере каждый вызов функции add() равен O (1), не считая стоимости вызова конструктора класса Stamp. Добавление в связанный список просто привязывает другой элемент к его концу. Это, конечно, предполагает, что реализация связанного списка знает, какой узел находится в конце списка. Если он этого не знает, то, конечно, требуется обход всего списка.