Лінійний список

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

ЛІНІЙНИЙ СПИСОК в інформатиці та програмуванні - це послідовність з 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) - лінійний список, в якому всі операції вставки та видалення виконуються на обох кінцях списку.

Не менш важливим окремим випадком лінійного списку є зв'язаний список, в якому кожний елемент окрім поля даних зберігає також вказівник на наступний. Така структура дозволяє зняти обмеження на зберігання лінійного списку в безперервній області пам'яті.

Важливим узагальненням лінійного списку є багатовимірний масив.