Лінійний список
Матеріал з Вікіпедії — вільної енциклопедії.
ЛІНІЙНИЙ СПИСОК в інформатиці та програмуванні - це послідовність з n≥0 елементів X[1],X[2], ... X[n], де справедлива наступна умова: якщо n>0 та X[1] - перший елемент у списку, а X[n] -- останній, то k-й елемент розташований між X[k-1] та X[k+1] елементами для усіх 1<k<n.
З такими структурами даних виконуються наступні операції:
- отримання k-го елемента списку для читання чи запису в нього нового значення
- додавання нового елемента в будь-яку позицію в списку
- видалення елемента списку
- об'єднання в одному списку двох або більше лінійних списків
- розбиття списку на два або більше фрагментів
- створення копії списку
- визначення кількості елементів в списку
- сортування елементів списку
- пошук елементу, який задовільняє певним критеріям
Важливими окремими випадками лінійних списків, в яких операції додавання та вилучення певних значень можуть бути виконані лише для першого чи останнього елементу, є:
- стек -- лінійний список, в якому операції додавання та вилучення виконуються лише на одному кінці списку (верхівці стеку)
- черга (однобічна черга) - лінійний список, в якому усі операції додавання виконується на одному кінці (в голові черги), а операції вилучення - на іншому кінці списку (в хвості черги).
- дек або двобічна черга (англ. double-ended queue, deq) - лінійний список, в якому всі операції вставки та видалення виконуються на обох кінцях списку.
Не менш важливим окремим випадком лінійного списку є зв'язаний список, в якому кожний елемент окрім поля даних зберігає також вказівник на наступний. Така структура дозволяє зняти обмеження на зберігання лінійного списку в безперервній області пам'яті.
Важливим узагальненням лінійного списку є багатовимірний масив.
