Список (інформатика)

В інформатики, список ( англ. list ) - Це абстрактний тип даних, що представляє собою упорядкований набір значень, в якому деяке значення може зустрічатися більше одного разу. Примірник списку є комп'ютерною реалізацією математичного поняття кінцевої послідовності - кортежу. Примірники значень, що знаходяться в списку, називаються елементами списку ( англ. item, entry або element ); Якщо значення зустрічається кілька разів, кожне входження вважається окремим елементом.

Структура односвязного списку з трьох елементів

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


1. Визначення

За допомогою нотації методу синтаксично-орієнтованого конструювання Ч. Хоара визначення списку можна записати наступним чином:

List (A) = NIL + (A \ times List (A))
prefix = \ text {constructor}List (A)
head, tail = \ text {selectors}List (A)
null, nonnull = \ text {predicates}List (A)
NIL, nonNIL = \ text {parts}List (A)

Перший рядок даного визначення позначає, що список елементів типу A (Кажуть: "список над A ") Являє собою розмічених об'єднання порожнього списку і декартова твори атома типу A зі списком над A . Для створення списків використовуються два конструктора (другий рядок визначення), перший з яких створює порожній список, а другий - непорожній відповідно. Цілком зрозуміло, що другий конструктор отримує на вхід в якості параметрів деякий атом і список, а повертає список, першим елементом якого є вихідний атом, а рештою - елементи вихідного списку. Тобто виходить префіксація атома до списку, з чим і пов'язане таке найменування конструктора. Тут необхідно відзначити, що порожній список [] не є атомом, а тому не може префіксіроваться. З іншого боку, порожній список є як би нульовим елементом для конструювання списків, тому будь список містить у самому своєму кінці саме порожній список - з нього починається конструювання.

Третій рядок визначає селектори для списку, тобто операції для доступу до елементів усередині списку. Селектор head отримує на вхід список і повертає перший елемент цього списку, тобто типом результату є тип A . Цей селектор не може отримати на вхід порожній список - в цьому випадку результат операції невизначений. Селектор tail повертає список, отриманий з вхідного в результаті відсікання його голови (першого елемента). Цей селектор також не може приймати на вхід порожній список, так як в цьому випадку результат операції невизначений. За допомогою цих двох операцій можна дістати зі списку будь-який елемент. Наприклад, щоб отримати третій елемент списку (якщо він є), необхідно послідовно два рази застосувати селектор tail , Після чого застосувати селектор head . Іншими словами, для отримання елемента списку, який знаходиться на позиції n (Починаючи з 0 для першого елемента, як це прийнято в програмуванні), необхідно n раз застосувати селектор tail , Після чого застосувати селектор head .

Четвертий рядок визначення описує предикати для списку, тобто функції, що повертають булеве значення в залежності від деяких умов. Перший предикат повертає значення true у випадку, якщо заданий список порожній. Другий предикат діє навпаки. Нарешті, п'ятий рядок описує частині списку, які, як уже сказано, являють собою порожній і непорожній списки.


2. Властивості

У певній таким чином структури даних є деякі властивості:

  • Розмір списку - кількість елементів у ньому, крім останнього "нульовий" елемент, що є за визначенням порожнім списком.
  • Тип елементів - той самий тип A , Над якими будується список; всі елементи в списку повинні бути цього типу.
  • Отсортірованность - список може бути відсортований відповідно до деякими критеріями сортування (наприклад, за зростанням цілочисельних значень, якщо список складається з цілих чисел).
  • Можливості доступу - деякі списки в залежності від реалізації можуть забезпечувати програміста селекторами для доступу безпосередньо до заданого за номером елементу.
  • Сравниваемо - списки можна порівнювати один з одним на відповідність, причому залежно від реалізації операція порівняння списків може використовувати різні технології.

Як повинно бути зрозуміло з назви розглянутої структури даних, списки використовуються для зберігання наборів однотипних елементів. Такі елементи можуть бути відсортовані для використання у функціях пошуку або функціях для швидкої вставки нових елементів в список.


3. Списки в мовах програмування

3.1. Функціональні мови

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

3.1.1. Мова Haskell

3.1.2. Мова Lisp

3.2. Імперативні мови

Перегляд цього шаблону Типи даних
Неінтерпретіруемие
Числові
Текстові
Покажчик

Адреса Посилання

Композитні
Інші

Логічний Нижчий тип Колекція Перераховуються тип Виняток First-class function Opaque data type Recursive data type Семафор Потік Вищий тип Type class Unit type Void

Пов'язані теми
Перегляд цього шаблону Структури даних ( список)
Типи
Масиви
Списки
Дерева
Графи