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

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

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

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

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

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

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

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

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

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

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

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

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

Графи

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

...

Дерева

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

...

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

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

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