Колекція (абстрактний тип даних)

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

Як правило, елементи даних будуть одного типу або, у мовах, що підтримують наслідування, походять від одного загального типу предка. Колекція — це концепція, застосовна до абстрактних типів даних, і не передбачає конкретної реалізації як конкретної структури даних, хоча зазвичай існує вибір.

Приклади колекцій включають списки, множини, мультимножини, дерева та графи.

Масив не вважається колекцією, оскільки він має фіксований розмір. Динамічний масив, зазвичай, вважається колекцією.

Лінійні колекції

Багато колекцій визначають лінійне впорядкування з доступом з одного або обох кінців. Фактична структура даних, яка реалізує таку колекцію, не обов’язково повинна бути лінійною — наприклад, пріоритетна черга часто реалізується як купа, яка є різновидом дерева. Важливі лінійні колекції включають:

• списки;
• стеки;
• черги;
• пріоритетні черги;
• двосторонні черги;
• двосторонні пріоритетні черги.

Асоціативні колекції

Ці колекції можна інтерпретувати як функції: за наявності вхідних даних колекція дає результат. Важливі асоціативні колекції включають:

• множини;
• мультимножини;
• асоціативні масиви.

Графи

...

Дерева

...

Абстракція і реалізація

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