Page 52 - Bkhargava_-_Grokaem_algoritmy

Упражнения 51

Заметим, что вставка и удаление выполняются за время 0(1) только в том
случае, если вы можете мгновенно получить доступ к удаляемому элементу.
На практике обычно сохраняются ссылки на первый и последний элементы
связанного списка, поэтому время удаления этих элементов составит всего
0(1).

Какая структура данных используется чаще: массивы или списки? Очевидно,
это зависит от конкретного сценария использования. Массивы чрезвычайно
популярны из-за того, что они поддерживают произвольный доступ. Всего
существуют два вида доступа: произвольный и последовательный. При по­
следовательном доступе элементы читаются по одному, начиная с первого.
Связанные списки поддерживают только последовательный доступ. Если вы
захотите прочитать 10-й элемент связанного списка, вам придется прочитать
первые 9 элементов и перейти по ссылкам к 10-му элементу. Я часто говорю,
что массивы обладают более высокой скоростью чтения; это объясняется
тем, что они поддерживают произвольный доступ. Многие реальные ситуа­
ции требуют произвольного доступа, поэтому массивы часто применяются
на практике. Также массивы и списки используются для реализации других
структур данных (о которых будет рассказано в книге далее).

Упражнения

2.2 Допустим, вы пишете приложение для приема заказов от посетителей
ресторана. Приложение должно хранить список заказов. Официанты
добавляют заказы в список, а повара читают заказы из списка и вы­
полняют их. Заказы образуют очередь: официанты добавляют заказы
в конец очереди, а повар берет первый заказ из очереди и начинает
готовить.

www.trk.kg