Если есть список вида: [] -> [] -> [] -> nullptr , то можно ли как-то сделать метод pop(), удаляющий последний элемент за O(1)? Проблема в том, что, если удалять [] -> nullptr, то предыдущему нужно выставить указатель на nullptr, иначе будет указатель на удаленную память. Чтобы его найти, нужно пройтись по всему списку с начала.
Вопрос Однонаправленный список c++
- Автор темы Серёжа123
- Дата начала
Для ускорения таких часто-используемых операций создается класс, который хранит первый элемент, предпоследний, и размер. Ну и само собой реализацию методов. Тогда удаление/добавление и просмотр в начало и в конец всегда будет O(1)
Для удаления последнего элемента из однонаправленного списка за O(1) необходимо хранить указатель на предыдущий элемент в каждом узле списка. Таким образом, при вызове метода pop() можно удалить последний элемент списка и изменить указатель на nullptr в предыдущем элементе за O(1), не проходя по всему списку с начала. Однако, если в списке нет указателей на предыдущий элемент, то удаление последнего элемента потребует прохода по всему списку с начала, что займет O
времени.
времени.Похожие темы
- Закрыта
