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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

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

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

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

Операції[ред. | ред. код]

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

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

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

Реалізації[ред. | ред. код]

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

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

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

Підтримка мов програмування[ред. | ред. код]

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

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

Використання[ред. | ред. код]

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

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

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

Абстрактне визначення[ред. | ред. код]

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

nil: () → L
cons: E × LL
first: LE
rest: LL

з аксіомами: first (cons (e, l)) = e

rest (cons (e, l)) = l

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

cons (e, l) ≠ e
cons (e1, l1) = cons (e2, l2) if e1 = e2 and l1 = l2

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

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

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

Список монад[ред. | ред. код]

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

де append визначається наступним чином:

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

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

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

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

References[ред. | ред. код]

  1. Abelson, Harold; Sussman, Gerald Jay (1996). Structure and Interpretation of Computer Programs. MIT Press. 
  2. 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. 
  3. Barnett, Granville; Del tonga, Luca (2008). Data Structures and Algorithms. mta.ca. Процитовано 12 November 2014. 
  4. Lerusalimschy, Roberto (December 2003). Programming in Lua (first edition) (вид. First). Lua.org. ISBN 8590379817. Процитовано 12 November 2014. 
  5. Steele, Guy (1990). Common Lisp (вид. Second). Digital Press. с. 29–31. ISBN 1-55558-041-6. 

Див. також[ред. | ред. код]