Page 40 - 6110

9.5 Зв'язані списки та масиви
Списки мають деякі переваги над масивами. Вони досить
ефективні щодо операцій додавання або видалення елементу в
довільному місці списка, виконуючи їх за постійний час, тоді як
масиви для цього потребують часу Т(n), тобто час зростає з ростом
кількості елементів масиву.
В списках також не існує проблеми “розширення”, яка рано чи
пізно виникає в масивах фіксованого розміру, коли виникає
необхідність включити в нього додаткові елементи. Точно так,
фіксований масив, з якого було видалено багато елементів (або вони
просто не використовуються) є дуже неефективним з точки зору
використання пам’яті. Функціонування списків можливо в ситуації,
коли пам’ять комп’ютера фрагментована, тоді як масиви переважно
потребують неперервної області для зберігання.
З іншого боку, масиви дозволяють безпосередній доступ до
будь-якого елементу. Однобічно зв'язані списки, натомість,
потребують проходження усіх попередніх елементів. Це призводить
до складнощів застосування списків в задачах, де необхідно швидко
знаходити елемент за його індексом, наприклад в алгоритмах
сортування. Кешування списків в таких випадках майже не дає
ефекту.
Іншим очевидним недоліком списків є необхідність разом з
корисною інформацією додаткового збереження інформації про
вказівники, що позначається на ефективності використання пам'яті
цими структурами.

9.6 Двобічне та однобічне зв'язування
Двобічне зв'язування потребує більше пам'яті на елемент та
більших обчислювальних затрат на виконання елементарних
операцій. Але такими списками легше маніпулювати, тому що вони
дозволяють проходження по списку в обох напрямах, що є
необхідною умовою функціонування деяких алгоритмів.

Контрольні запитання

1 Що таке “лінійний список” в інформатиці та програмуванні?
2 Які операції виконуються з лінійними списками?
3 Які окремі випадки лінійних списків, в яких операції додавання та
вилучення певних значень можуть бути виконані лише для першого
чи останнього елементу, Вам відомі?
4 Що таке “стек” в інформатиці та програмуванні?
5 Які основні операції зі стеком Вам відомі?
6 Які додаткові операції зі стеком Вам відомі?
39