Перегляд вихідного коду сторінки Список (абстрактний тип даних)

У [[Інформатика|комп'ютерній науці]], '''список''' або '''послідовність'''&nbsp;— [[абстрактний тип даних]], який являє собою зліченне число впорядкованих [[Величина (інформатика)|значень]], де одне і теж саме значення може зустрічатися більше одного разу. Екземпляр списку&nbsp;— це комп'ютерне подання [[Математика|математичного]] поняття скінченної [[Послідовність|послідовності]]; (потенційно) нескінченний аналог списку&nbsp;— це [[Потік (програмування)|потік]].

Списки є основним прикладом [[Контейнер (програмування)|контейнерів]], оскільки вони містять інші значення. Якщо ж значення зустрічається кілька разів, у кожному випадку воно розглядається, як окремий елемент.

[[Файл:Singly-linked-list.svg|thumb|right|Структура однобічно зв'язаного списку, котрий реалізує список з 3-х цілих елементів.]]
Назва «список» також використовується для кількох конкретних [[Структура даних|структур даних]], які можна використати для реалізації абстрактних списків, особливо [[Зв'язаний список|зв'язаних списків]].

Багато [[Мова програмування|мов програмування]] забезпечують підтримку типів даних списку, і мають спеціальний синтаксис і семантику для списків і перелік операцій. Список часто можна побудувати шляхом написання послідовності елементів, розділених [[Кома (розділовий знак)|комами]], [[Крапка з комою|крапками з комою]] та/або [[пробіл|пропусками]], в межах пари роздільників, таких як круглі дужки '()', квадратні дужки '[]', фігурні дужки '{}', або кутові дужки '<>'. В [[Об'єктно-орієнтоване програмування|об'єктно-орієнтованих мовах програмування]], списки зазвичай подаються як [[Об'єкт (програмування)|екземпляри]] підкласів загального класу «списку», і проходяться через окремі [[Ітератор (шаблон проєктування)|ітератори]]. Тип даних «список» часто реалізується з використанням [[Структура даних|структури даних]] [[Масив (структура даних)|«масив»]] або зв'язаних списків деякого виду, але і інші [[Структура даних|структури даних]] можуть бути більш відповідними для деяких застосувань. У деяких контекстах, наприклад, у програмуванні на [[Lisp]], термін список може стосуватися конкретно зв'язаного списку, а не масиву.

У теорії типів і [[Функційне програмування|функційному програмуванні]], абстрактні списки зазвичай {{Нп|Індуктивний тип|індуктивно||Inductive type}} визначаються двома операціями: ''NIL'', що дає порожній список, і ''CONS'', яка додає елемент у початок списку.<ref>{{cite book|last1=Reingold|first1=Edward|last2=Nievergelt|first2=Jurg|last3=Narsingh|first3=Deo|title=Combinatorial Algorithms: Theory and Practice|url=https://archive.org/details/combinatorialalg0000rein|date=1977|publisher=Prentice Hall|location=Englewood Cliffs, New Jersey|isbn=0-13-152447-X|pages=[https://archive.org/details/combinatorialalg0000rein/page/38 38]–41}}</ref>

== Операції ==
Реалізація структури даних списку може надати деякі з таких [[Операція (математика)|операцій]]:
* [[Конструктор (програмування)|конструктор]] для створення порожнього списку;
* операція для перевірки чи список порожній, чи ні;
* операція для додавання об'єкта на початок списку;
* операція для додавання об'єкта в список;
* операція для визначення першого компонента (або «голови») списку;
* операція для посилання на список, що складається з усіх компонентів списку, за винятком його першого елемента («голови»), (це називається «хвіст» списку).
В іноземній термінології використовуються такі позначення: голова списку&nbsp;— {{lang-en|head}}, хвіст&nbsp;— {{lang-en|tail}}.

== Реалізації ==
Списки зазвичай реалізуються або у вигляді [[Зв'язаний список|зв'язаних списків]] (або [[Однобічно зв'язаний список|однобічно]], або [[Двобічно зв'язаний список|двобічно]]) або у вигляді [[Масив (структура даних)|масивів]], як правило, змінної довжини або [[Динамічний масив|динамічних масивів]].

Стандартний спосіб реалізації списків, що походить з мови програмування [[Lisp]], передбачає, що кожен елемент списку має значення і вказівник, який вказує місце розташування наступного елемента списку. Це призводить або до [[Зв'язаний список|зв'язаного списку]] або до [[Дерево (структура даних)|дерева]], залежно від того, чи має список вкладені підсписки. Деякі старі реалізації Lisp (такі як реалізація Lisp Symbolics 3600) також підтримують «стислі списки» (з використанням CDR кодування), які мали спеціальне внутрішнє подання (невидиме для користувача). Списками можна маніпулювати за допомогою [[Ітерація|ітерації]] або [[Рекурсія|рекурсії]]. Перше часто є кращим в [[Імперативне програмування|імперативних мовах програмування]], тоді як останнє є нормою у [[Функційне програмування|функційних мовах]].

Списки можуть бути реалізовані у вигляді [[Збалансоване дерево|збалансованих двійкових дерев пошуку]], котрі містять пари індекс-значення, забезпечуючи доступ до будь-якого елемента за однаковий час (наприклад, як крайові, так і внутрішні вузли зберігають індекс найправішого нащадка, що використовується для направлення пошуку), затрачаючи час, логарифмічний від розміру списку, але, поки список не дуже змінюється, це також забезпечує ілюзію випадкового доступу і робить можливим операції перестановки, префіксних і додавання також за логарифмічний час.<ref>{{cite web|last1=Barnett|first1=Granville|last2=Del tonga|first2=Luca|title=Data Structures and Algorithms|url=http://www.mta.ca/~rrosebru/oldcourse/263114/Dsa.pdf|website=mta.ca|accessdate=12 листопада 2014|date=2008|archive-date=12 листопада 2014|archive-url=https://web.archive.org/web/20141112201707/http://www.mta.ca/~rrosebru/oldcourse/263114/Dsa.pdf}}</ref>

== Підтримка у мовах програмування ==
Деякі мови не пропонують структуру даних «список», але підтримують використання [[Асоціативний масив|асоціативних масивів]] або свого роду таблиць, щоб емулювати списки. Наприклад, [[Lua]] надає таблиці. Хоча Lua зберігає списки, які мають числові індекси, як масиви, вони як і раніше відображаються у вигляді словників.<ref>{{cite book|last1=Lerusalimschy|first1=Roberto|title=Programming in Lua (first edition)|date=December 2003|publisher=Lua.org|isbn=8590379817|edition=First|url=http://www.lua.org/pil/11.3.html|accessdate=12 листопада 2014|archive-date=9 жовтня 2014|archive-url=https://web.archive.org/web/20141009214154/http://www.lua.org/pil/11.3.html}}</ref>

У [[Lisp]], списки є основним типом даних і можуть містити як програмний код, так і дані. В більшості діалектів, список перших трьох простих чисел можна записати у вигляді <code>(list 2 3 5)</code>. У деяких діалектах Lisp, зокрема в [[Scheme]], список є набором пар, що складаються зі значення і вказівника на наступну пару (або нульового значення), що реалізує [[однобічно зв'язаний список]].<ref>{{cite book|last1=Steele|first1=Guy|title=Common Lisp|url=https://archive.org/details/commonlisplangua0000stee|date=1990|publisher=Digital Press|isbn=1-55558-041-6|pages=[https://archive.org/details/commonlisplangua0000stee/page/29 29]–31|edition=Second}}</ref>

== Використання ==
Як випливає з назви, списки можна використати для зберігання списку елементів. Однак, на відміну від традиційних [[Масив (структура даних)|масивів]], списки можуть розширюватися і стискатися, і зберігаються в пам'яті динамічно.

В обчислювальній техніці, списки легше реалізувати, ніж множини. Скінченну [[множина|множину]] в математичному сенсі можна реалізувати у вигляді списку з додатковими обмеженнями, а саме, елементи, що повторюються, заборонені і порядок не має значення. Сортування списку прискорює процес визначення наявності об'єкта у множині, але підтримання порядку вимагає більше часу для додання нового запису до списку. Більш ефективно множини реалізуються з використанням [[Збалансоване дерево|збалансованих двійкових дерев пошуку]] або [[Геш-таблиця|геш-таблиць]], а не списком.

Списки також є основою для інших абстрактних типів даних, зокрема [[Черга (структура даних)|черг]], [[стек]]ів і їх варіацій.

== Абстрактне визначення ==
Абстрактний список типу L з елементами деякого типу Е ([[Поліморфізм (програмування)|мономорфний]] список) визначається такими функціями:

: nil: () → ''L''
: cons: ''E'' × ''L'' → ''L''
: first: ''L'' → ''E''
: rest: ''L'' → ''L''

з аксіомами:

: first (cons (''e'', ''l'')) = ''e''
: rest (cons (''e'', ''l'')) = ''l''

для будь-якого елемента '' е '' і будь-якого списку '' L''. Мається на увазі, що:

: cons (''e'', ''l'') ≠ ''l''
: cons (''e'', ''l'') ≠ ''e''
: cons (''e''<sub>1</sub>, ''l''<sub>1</sub>) = cons (''e''<sub>2</sub>, ''l''<sub>2</sub>) if ''e''<sub>1</sub> = ''e''<sub>2</sub> and ''l''<sub>1</sub> = ''l''<sub>2</sub>

Зауважимо, що first (nil ()) і rest (nil ()) не визначені.

Ці аксіоми еквівалентні аксіомам типу даних абстрактного [[Стек|стеку]].

В [[Теорія типів|теорії типів]], наведене вище визначення простіше розглядається як визначення {{Нп|Індуктивний тип|індуктивного типу||Inductive type}} в термінах конструкторів: nil і cons. В алгебраїчних термінах, це можна подати як перетворення 1 + ''E'' &times; ''L'' → ''L''. ''first'' та ''rest'' потім отримуються шляхом зіставлення зі зразком у конструкторі ''cons'' і окремо обробляється випадок nil.

=== Список монад ===
Тип списку утворює [[Монади (програмування)|монаду]] з такими функціями (використано ''E*'', а не ''L'' для відображення мономорфних списків з елементами типу Е):

: <math>\text{return}\colon A \to A^{*} = a \mapsto \text{cons} \, a \, \text{nil}</math>
: <math>\text{bind}\colon A^{*} \to (A \to B^{*}) \to B^{*} = l \mapsto f \mapsto \begin{cases} \text{nil} & \text{if} \ l = \text{nil}\\ \text{append} \, (f \, a) \, (\text{bind} \, l' \, f) & \text{if} \ l = \text{cons} \, a \, l' \end{cases}</math>

де ''append'' визначається так:

: <math>\text{append}\colon A^{*} \to A^{*} \to A^{*} = l_1 \mapsto l_2 \mapsto \begin{cases} l_2 & \text{if} \ l_1 = \text{nil} \\ \text{cons} \, a \, (\text{append} \, l_1' \, l_2) & \text{if} \ l_1 = \text{cons} \, a \, l_1' \end{cases}</math>

Як альтернатива, монаду можна визначити в термінах операцій ''return'', ''fmap'' та ''join:''
: <math>\text{fmap} \colon (A \to B) \to (A^{*} \to B^{*}) = f \mapsto l \mapsto \begin{cases} \text{nil} & \text{if} \ l = \text{nil}\\ \text{cons} \, (f \, a) (\text{fmap} f \, l') & \text{if} \ l = \text{cons} \, a \, l' \end{cases}</math>
: <math>\text{join} \colon {A^{*}}^{*} \to A^{*} = l \mapsto \begin{cases} \text{nil} & \text{if} \ l = \text{nil}\\ \text{append} \, a \, (\text{join} \, l') & \text{if} \ l = \text{cons} \, a \, l' \end{cases}</math>

Зверніть увагу, що ''fmap'', ''join'', ''append'' та ''bind'' чітко визначені, оскільки вони застосовуються до більш і більш глибоких аргументів за кожного рекурсивного виклику.

Тип списку є адитивною монадою, з ''nil'', як монадичним нулем, і ''append'', як монадичною сумою.

Списки утворюють [[моноїд]] відносно операції додавання. Одиничний елемент моноїда є порожній список, ''nil''. Насправді, це {{Нп|вільний моноїд|||Free monoid}} над множиною елементів списку.

== Примітки ==
{{reflist}}

== Джерела ==
* {{CLRS|chapter=10.2 Зв'язані списки}}

{{Структури даних}}
{{Типи даних}}

[[Категорія:Типи даних]]
[[Категорія:Абстрактні типи даних]]
[[Категорія:Складені типи даних]]