Вопрос Однонаправленный список c++

[Серёжа123]

Если есть список вида: [] -> [] -> [] -> nullptr , то можно ли как-то сделать метод pop(), удаляющий последний элемент за O(1)? Проблема в том, что, если удалять [] -> nullptr, то предыдущему нужно выставить указатель на nullptr, иначе будет указатель на удаленную память. Чтобы его найти, нужно пройтись по всему списку с начала.

 

[MasterMaloy]

Для ускорения таких часто-используемых операций создается класс, который хранит первый элемент, предпоследний, и размер. Ну и само собой реализацию методов. Тогда удаление/добавление и просмотр в начало и в конец всегда будет O(1)

 

[Fort]

Для удаления последнего элемента из однонаправленного списка за O(1) необходимо хранить указатель на предыдущий элемент в каждом узле списка. Таким образом, при вызове метода pop() можно удалить последний элемент списка и изменить указатель на nullptr в предыдущем элементе за O(1), не проходя по всему списку с начала. Однако, если в списке нет указателей на предыдущий элемент, то удаление последнего элемента потребует прохода по всему списку с начала, что займет O времени.

 

[ZJLoNIX]

Храни указатель на последний элемент, но это скорее костыль чем решение

 

[WendeFull]

В однонаправленном списке никак не получится вернуться назад без полного перебора. Для таких целей и нужны двунаправленные списки.