Список (абстрактний тип даних)

У комп'ютерній науці, список або послідовність — абстрактний тип даних, який являє собою зліченне число впорядкованих значень, де одне і теж саме значення може зустрічатися більше одного разу. Екземпляр списку — це комп'ютерне подання математичного поняття скінченної послідовності; (потенційно) нескінченний аналог списку — це потік.

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

Структура однобічно зв'язаного списку, котрий реалізує список з 3-х цілих елементів.

Назва «список» також використовується для кількох конкретних структур даних, які можна використати для реалізації абстрактних списків, особливо зв'язаних списків.

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

У теорії типів і функційному програмуванні, абстрактні списки зазвичай індуктивно^[en] визначаються двома операціями: NIL, що дає порожній список, і CONS, яка додає елемент у початок списку.^[1]

Операції

Реалізація структури даних списку може надати деякі з таких операцій:

• конструктор для створення порожнього списку;
• операція для перевірки чи список порожній, чи ні;
• операція для додавання об'єкта на початок списку;
• операція для додавання об'єкта в список;
• операція для визначення першого компонента (або «голови») списку;
• операція для посилання на список, що складається з усіх компонентів списку, за винятком його першого елемента («голови»), (це називається «хвіст» списку).

В іноземній термінології використовуються такі позначення: голова списку — англ. head, хвіст — англ. tail.

Реалізації

Списки зазвичай реалізуються або у вигляді зв'язаних списків (або однобічно, або двобічно) або у вигляді масивів, як правило, змінної довжини або динамічних масивів.

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

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

Підтримка у мовах програмування

Деякі мови не пропонують структуру даних «список», але підтримують використання асоціативних масивів або свого роду таблиць, щоб емулювати списки. Наприклад, Lua надає таблиці. Хоча Lua зберігає списки, які мають числові індекси, як масиви, вони як і раніше відображаються у вигляді словників.^[3]

У Lisp, списки є основним типом даних і можуть містити як програмний код, так і дані. В більшості діалектів, список перших трьох простих чисел можна записати у вигляді (list 2 3 5). У деяких діалектах Lisp, зокрема в Scheme, список є набором пар, що складаються зі значення і вказівника на наступну пару (або нульового значення), що реалізує однобічно зв'язаний список.^[4]

Використання

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

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

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

Абстрактне визначення

Абстрактний список типу 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₁, l₁) = cons (e₂, l₂) if e₁ = e₂ and l₁ = l₂

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

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

В теорії типів, наведене вище визначення простіше розглядається як визначення індуктивного типу^[en] в термінах конструкторів: nil і cons. В алгебраїчних термінах, це можна подати як перетворення 1 + E × L → L. first та rest потім отримуються шляхом зіставлення зі зразком у конструкторі cons і окремо обробляється випадок nil.

Список монад

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

${\displaystyle {\text{return}}\colon A\to A^{*}=a\mapsto {\text{cons}}\,a\,{\text{nil}}}$

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

Як альтернатива, монаду можна визначити в термінах операцій return, fmap та join:

${\displaystyle {\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}}}$

${\displaystyle {\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}}}$

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

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

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

Примітки

1. Reingold, Edward; Nievergelt, Jurg; Narsingh, Deo (1977). Combinatorial Algorithms: Theory and Practice. Englewood Cliffs, New Jersey: Prentice Hall. с. 38–41. ISBN 0-13-152447-X.
2. Barnett, Granville; Del tonga, Luca (2008). Data Structures and Algorithms (PDF). mta.ca. Архів оригіналу (PDF) за 12 листопада 2014. Процитовано 12 листопада 2014.
3. Lerusalimschy, Roberto (December 2003). Programming in Lua (first edition) (вид. First). Lua.org. ISBN 8590379817. Архів оригіналу за 9 жовтня 2014. Процитовано 12 листопада 2014.
4. Steele, Guy (1990). Common Lisp (вид. Second). Digital Press. с. 29–31. ISBN 1-55558-041-6.

Джерела

• Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 10.2 Зв'язані списки. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.