Page 27 - 4656

Алгоритми і структури даних. Лабораторний практикум.

виникає необхідність включити в нього додаткові елементи.
Точно так, фіксований масив, з якого було видалено багато
елементів (або вони просто не використовуються) є дуже
неефективним з точки зору використання пам'яті.
Функціонування списків можливо в ситуації, коли пам'ять
комп'ютера фрагментована, тоді як масиви переважно
потребують неперервної області для зберігання.
З іншого боку, масиви дозволяють безпосередній доступ
до будь-якого елементу. Однобічно зв'язані списки, натомість,
потребують проходження усіх попередніх елементів. Це
призводить до складнощів застосування списків в задачах, де
необхідно швидко знаходити елемент за його індексом,
наприклад в алгоритмах сортування. Кешування списків в таких
випадках майже не дає ефекту.
Іншим очевидним недоліком списків є необхідність разом
з корисною інформацією додаткового збереження інформації про
вказівники, що позначається на ефективності використання
пам'яті цими структурами.
Переваги списків над масивами
Можливість додавати вузол у кінець списку. Масив має
статичний розмір, і, якщо, вільного місця там немає, доведеться
створювати масив більшого розміру, копіювати у нього елементи
«старого» масиву і тільки після цього додавати новий елемент
Можливість видаляти вузол і звільнювати пам'ять, яку він
займав. У масиві можна лише зсунути елементи і розглядати
його, як масив меншого розміру. Пам'ять при цьому не
звільняється.
Можливість вставляти вузол у середину списку. При
умові, що масив не заповнений до кінця, можна «розсунути»
елементи і вставити між ними необхідний. Якщо ж масив
повний — доведеться створювати новий масив більшого розміру,
копіювати елементи і вставляти новий.
Недоліки списків перед масивами:
25