Сложность удаления последнего элемента в двойном связанном списке

Question

Если вы хотите удалить Узел A , вам придется пройти только один и сложность составит O (1)

Если вы хотите удалить Узел C , вам придется пройти два раза, и сложность составит O (n)

Если вы хотитеудалите Узел D , тогда вам придется пройти три раза, и сложность может быть O (n) Однако сложность удаления последнего узла в двойном связанном списке равна O (1)

Я не понимаю, как это работает?

Я проверил эту ссылку, но не получил / не понял свой ответ Ссылка

Answer 1

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

Answer 2

Сложность заключается не в удалении элемента, а в определении его.

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

Если кто-то попросит вас удалить элемент списка k ^th , вы должны начать с началаи перейдите k ссылок, чтобы найти элемент, прежде чем вы можете удалить его.Это будет O (k), который в худшем случае будет O (n-1).