Page 72 - 4656

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

Точно так, фіксований масив, з якого було видалено багато
елементів (або вони просто не використовуються) є дуже
неефективним з точки зору використання пам'яті.
Функціонування списків можливо в ситуації, коли пам'ять
комп'ютера фрагментована, тоді як масиви переважно
потребують неперервної області для зберігання.
З іншого боку, масиви дозволяють безпосередній доступ
до будь-якого елементу. Однобічно зв'язані списки, натомість,
потребують проходження усіх попередніх елементів. Це
призводить до складнощів застосування списків в задачах, де
необхідно швидко знаходити елемент за його індексом,
наприклад в алгоритмах сортування. Кешування списків в таких
випадках майже не дає ефекту.
Іншим очевидним недоліком списків є необхідність разом
з корисною інформацією додаткового збереження інформації про
вказівники, що позначається на ефективності використання
пам'яті цими структурами.
Двобічне та однобічне зв'язування.
Двобічне зв'язування потребує більше пам'яті на елемент
та більших обчислювальних затрат на виконання елементарних
операцій. Але такими списками легше маніпулювати, тому що
вони дозволяють проходження по списку в обох напрямах, що є
необхідною умовою функціонування деяких алгоритмів.
За визначенням, список - це послідовність з n≥0 елементів
X[1],X[2], … X[n], для якої виконується наступна умова: якщо
n>0 та X[1] — перший елемент у списку, а X[n] - останній, то k-й
елемент розташований між X[k-1] та X[k+1] елементами для усіх
1<k<n.
З такими структурами даних виконуються наступні
операції:
 отримання k-го елемента списку для читання чи запису в нього
нового значення;

70