Page 39 - 6110

9.4 Зв'язаний список
Зв'язаний список в програмуванні – це одна з найважливіших
структур даних, в якій елементи лінійно впорядковані, але порядок
визначається не номерами елементів, а вказівниками, які входять в
склад елементів списку та вказують на наступний за даним елемент
(в однозв'язаних або однобічно зв'язаних списках) або на наступний
та попередній елементи (в двозв'язаних або двобічно зв'язаних
списках). Список має “голову” – перший елемент та “хвіст” –
останній елемент.
Зв'язані списки мають серію переваг порівняно з масивами.
Зокрема, в них набагато ефективніше (за час T(1), тобто незалежно
від кількості елементів) виконуються процедури додавання та
вилучення елементів. Натомість, масиви набагато кращі в
операціях, які потребують безпосереднього доступу до кожного
елементу, що у випадку зі зв'язаними списками неможливо та
потребує послідовного перебору усіх елементів, які передують
даному.
В однобічно зв'язаному списку, який є найпростішим
різновидом зв'язаних списків, кожний елемент складається з двох
полів: даних (data), та вказівника на наступний елемент (next). Якщо
вказівник не вказує на інший елемент (інакше: next = NULL), то
вважається, що даний елемент – останній в списку.
В двобічно зв'язаному списку елемент складається з трьох полів:
вказівника на попередній елемент (prev), поля даних (data) та
вказівника на наступний елемент (next). Якщо prev=NULL, то в
елемента немає попередника (тобто він є “головою” списку), якщо
next=NULL, то в нього немає наступника (“хвіст” списка).
В кільцевому списку перший та останній елемент зв'язані.
Тобто, поле prev голови списка вказує на хвіст списка, а поле next
хвоста списка вказує на голову списка.
Списки інтенсивно застосовуються в програмуванні як
самостійні структури. Також на їх основі можуть будуватись більш
складні структури даних, такі як дерева. На базі списків також
можуть бути реалізовані стеки та черги.
В загальному випадку, якщо необхідно оперувати з
динамічними множинами, де присутні інтенсивні операції з
додавання або видалення елементів, існують досить переконливі
аргументи для використання саме зв'язаних списків.

38