Page 51 - Bkhargava_-_Grokaem_algoritmy

50 Глава 2. Сортировка выбором

А при работе с массивом придется сдвигать вниз все остальные элементы.

---.... ~ &HMJ
ТРЕНМ- ЧАЕ-
ОБЕ.а.
РО&КА ПИТИЕ ~
·~
~
~
.~

А если свободного места не осталось, все данные придется скопировать
в новую область памяти! В общем, списки лучше подходят для вставки
элементов в середину.

Удаление

Что, если вы захотите удалить элемент? И снова список лучше подходит
для этой операции, потому что в нем достаточно изменить указатель в пре­
дыдущем элементе. В массиве при удалении элемента все последующие
элементы нужно будет сдвинуть вверх.

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

Ниже приведены примеры времени выполнения основных операций с мас­
сивами и связанными списками.

МАС.С.И&ЬI с.пис.ки

ЧТЕНИЕ 0(1) Otn)
ЬСП&КА 0~) Ou>

'j.Jl.AЛEHИE Q(.t\) 0(1)

www.trk.kg