Временная сложность Stack ADT, реализованной с использованием связанного списка

Question

Какова временная сложность функций put (x) и get () для абстрактного типа данных Stack, который реализован с использованием LinkedList?

Сначала я подумал, что они оба O (1).Но если get () должен пройти от головного узла до последнего элемента в списке, чтобы найти тот, который нужно удалить и вернуть, функция get () будет иметь вид O (n).

Put (x)) функция также должна пройти по всему списку, чтобы найти последний узел, где будет установлен новый узел.Так что это тоже будет O (n).

Если бы использовалась «специализированная» версия LinkedList, которая всегда сохраняла указатель на последний узел в списке, они оба стали бы операциями с постоянным временем.Правильно ли я понимаю, что стандартная реализация LinkedList не будет иметь это в наличии?

Answer 1

Вам не нужно вставлять в конец списка. Если вы вставляете в начало списка (с одной ссылкой), они оба O(1).

Стек содержит 1,2,3:

[1]->[2]->[3]

Push 5:

[5]->[1]->[2]->[3]

Pop:

[1]->[2]->[3], returning 5

Answer 2

Для двусвязного списка операции стека push и pop должны иметь значение O (1).

Если вы застряли с односвязным списком, предполагая, что вы в порядке с постоянными накладными расходами на удержание указателя на хвост, а также на голову, вы можете иметь O (1) операций очереди с постановкой в ​​очередь и удалением из очереди. И поскольку с помощью амортизируемых постоянных накладных расходов вы можете сделать стек из двух очередей, в конце концов, вы можете получить O (1) push и pop.