Структура стека LinkedList Big O

Question

Ответ на следующий вопрос: O (n) для pop и O (1) для pu sh. Но я не совсем понимаю, почему поп не может быть O (1). У нас есть хвостовой указатель, указывающий на конец связанного списка, и мы должны получить к нему доступ в O (1) раз, верно? Я что-то здесь пропустил?

Каково время выполнения операций pu sh и pop , если нижняя часть стека должна быть во главе связанная структура памяти? где n - количество узлов в структуре.

Answer 1

Подумайте об инвариантах вашего стека: tail указывает на последний элемент.

Операция pop удаляет последний элемент - это означает, что нам нужно перенастроить tail. как нам это сделать? Имея двусвязный список, мы могли бы просто следовать указателю назад к предыдущему узлу - но, как ясно показывает ваша иллюстрация, такой стрелки назад к предыдущему узлу в односвязном списке нет.

Вместо этого нам нужно начинать с head (единственный другой узел, для которого мы держим указатель) и выполнять итерацию до тех пор, пока мы не достигнем второго до последнего узла, а затем установить tail для указания на этот узел.