2001-gre-vs-practice.pdf/Q09

Ссылки сюда (1) →

Вопрос: Q09-e5724f

Рассмотрим односвязный список, где F это указатель на начало списка, а L на конец. Время выполнения каких операций из предложенных зависит от длины списка?

Ответы

• Правильный ответ: Удаление последнего элемента списка
• Удаление первого элемента списка
• Добавление элемента в конец
• Добавление элемента в начало
• Поменять местами первые 2 элемента списка

Объяснение

Исходники — вопрос 9 на 16 странице книги «2001-gre-vs-practice.pdf»

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

Остальные операции можно выполнить за O(1), зная F и L.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.