Зв'язаний список
Зв'язаний список у програмуванні — одна з найважливіших структур даних, у якій елементи лінійно впорядковані, але порядок визначається не номерами елементів, а вказівниками, які входять до складу елементів списку та вказують на наступний за цим елемент (в однозв'язаних або однобічно зв'язаних списках) або на наступний та попередній елементи (у двозв'язаних або двобічно зв'язаних списках). Список має «голову» — перший елемент та «хвіст» — останній елемент.
Зв'язані списки мають низку переваг порівняно з масивами. Зокрема, у них набагато ефективніше (за час О(1), тобто незалежно від кількості елементів) виконуються процедури додавання та вилучення елементів. Натомість, масиви набагато кращі в операціях, які потребують безпосереднього доступу до кожного елемента, що в разі зі зв'язаними списками неможливо та потребує послідовного перебору всіх елементів, які передують цьому.
Однобічно зв'язаний список з трьох елементів
В однобічно зв'язаному списку, який є найпростішим різновидом зв'язаних списків, кожний елемент складається з двох полів: data або даних, та вказівника next на наступний елемент. Якщо вказівник не вказує на інший елемент (інакше: next = NULL), то вважається, що цей елемент — останній у списку.
Двобічно зв'язаний список
У двобічно зв'язаному списку елемент складається з трьох полів — вказівника на попередній елемент prev, поля даних data та вказівника next на наступний елемент. Якщо prev=NULL, то в елемента немає попередника (тобто він є «головою» списку), якщо next=NULL, то в нього немає наступника («хвіст» списка).
Кільцевий однобічно зв'язаний список
У кільцевому списку перший та останній елемент зв'язані. Тобто поле prev голови списка вказує на хвіст списка, а поле next хвоста списка вказує на голову списка.
Списки інтенсивно застосовуються в програмуванні як самостійні структури. Також на їхній основі можуть будуватися складніші структури даних на кшталт дерева. На базі списків також можуть бути реалізовані стеки та черги.
Загалом, якщо необхідно оперувати з динамічними множинами, де присутні інтенсивні операції з додавання або видалення елементів, існують досить переконливі аргументи для використання саме зв'язаних списків.
Списки мають деякі переваги над масивами. Вони досить ефективні щодо операцій додавання або видалення елементу на початку, або в кінці списка, виконуючи їх за постійний час O(1), тоді як масиви для цього потребують часу O(n) (окрім видалення останнього елемента), тобто час зростає з ростом кількості елементів масиву. Водночас додавання/видалення довільного елемента залежить від розміру списку і складність такого алгоритму O(n).
У списках також не існує проблеми «розширення», яка рано чи пізно виникає в масивах фіксованого розміру, коли виникає необхідність помістити в нього додаткові елементи. Так само фіксований масив, з якого було видалено багато елементів (або вони просто не використовуються) є дуже неефективним з огляду використання пам'яті. Функціонування списків можливо в ситуації, коли пам'ять комп'ютера фрагментована, тоді як масиви переважно потребують неперервної області для зберігання.
З іншого боку, масиви дозволяють безпосередній доступ до будь-якого елемента. Однобічно зв'язані списки, натомість, потребують проходження всіх попередніх елементів. Це призводить до складнощів застосування списків у задачах, де необхідно швидко знаходити елемент за його індексом, наприклад в алгоритмах сортування. Кешування списків у таких випадках майже не дає ефекту.
Іншим очевидним недоліком списків є необхідність разом з корисною інформацією додаткового збереження інформації про вказівники, що позначається на ефективності використання пам'яті цими структурами.
Двобічне зв'язування потребує більше пам'яті на елемент та більших обчислювальних затрат на виконання елементарних операцій. Але такими списками легше маніпулювати, тому що вони дозволяють проходження по списку в обох напрямах, що є необхідною умовою функціонування деяких алгоритмів.
- Дональд Кнут. Fundamental Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 1. — 650 с. — ISBN 0-201-89683-4.(англ.)
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 10.2 Зв'язані списки. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.