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