Page 26 - 4656

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

Лабораторна робота № 3.
З'єднані структури даних

Мета: ознайомитись із роботою із впорядкованим
масивом, непрямими посиланнями, з'єднаними вузлами,
вставлянням елементу в список, вставлянням в початок списку,
стиранням із впорядкованого з'єднаного списку, вкладеними
класами.
Теоретичні відомості

Зв'язаний список в програмуванні — одна з
найважливіших структур даних, в якій елементи лінійно
впорядковані, але порядок визначається не номерами елементів,
а вказівниками, які входять в склад елементів списку та вказують
на наступний за даним елемент (в однозв'язаних або однобічно
зв'язаних списках) або на наступний та попередній елементи (в
двозв'язаних або двобічно зв'язаних списках). Список має
«голову» — перший елемент та «хвіст» — останній елемент.
Зв'язані списки мають серію переваг порівняно з
|масивами. Зокрема, в них набагато ефективніше (за час О(1),
тобто незалежно від кількості елементів) виконуються процедури
додавання та вилучення елементів. Натомість, масиви набагато
кращі в операціях, які потребують безпосереднього доступу до
кожного елементу, що у випадку зі зв'язаними списками
неможливо та потребує послідовного перебору усіх елементів, які
передують даному.
Списки мають деякі переваги над масивами. Вони досить
ефективні щодо операцій додавання або видалення елементу в
довільному місці списка, виконуючи їх за постійний час, тоді як
масиви для цього потребують часу O(n), тобто час зростає з
ростом кількості елементів масиву.
В списках також не існує проблеми «розширення», яка
рано чи пізно виникає в масивах фіксованого розміру, коли
24