У яких задачах краще використовувати список, а не масив?

Використовувати зв'язаний список замість масиву вигідно там, де важлива гнучкість структури й часті зміни даних, а не швидкий доступ за індексом.

Ось конкретні випадки, коли список кращий за масив.

---

#1. Коли потрібно часто вставляти й видаляти елементи

Зв'язаний список дозволяє вставляти й видаляти елементи:

• на початку - за O(1);
• у середині або в кінці (якщо є посилання) - теж за O(1).

У масиві ці операції вимагають зсуву елементів → O(n).

Приклад задач:

• Черги, стеки, буфери повідомлень.
• Історія дій (Undo/Redo).
• Керування пам'яттю або списками завдань, де часто щось додається й прибирається.

---

#2. Коли розмір даних заздалегідь невідомий

Масив вимагає знати або хоча б оцінити розмір заздалегідь. Якщо даних стає більше, потрібно перестворювати масив і копіювати елементи (O(n)). Зв'язаний список просто додає нові вузли динамічно.

Приклад задач:

• Потокові дані (вхідні події, логування).
• Динамічні структури (черга друку, список активних клієнтів).

---

#3. Коли важлива економія при фрагментованій пам'яті

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

Приклад задач:

• Низькорівневі системи (ОС, драйвери), де виділення великого блоку пам'яті проблематичне.
• Реалізація алокаторів пам'яті, таблиць вільних блоків.

---

#4. Коли потрібна структура, де елементи часто переміщуються

Якщо дані часто переставляються, міняються місцями, додаються в середину - у списку це просто перестановка посилань, без копіювання.

Приклад задач:

• Реалізація LRU-кешу,
• Черги з пріоритетом, де елементи часто оновлюються.

---

#5. Коли потрібен нескінченний або циклічний обхід

Циклічний список зручно використовувати, коли структура має "ходити по колу".

Приклад задач:

• Ігри (раунд за раундом),
• Планувальники завдань (round-robin scheduling),
• Кільцеві буфери.

---

#6. Коли важливе швидке додавання на початок

Масив додає на початок за O(n) - усі елементи зсуваються. Список робить це за O(1) - просто переназначається head.

Приклад задач:

• Реалізація стека, де додавання й видалення - завжди з "голови".

---

Підсумок:

Зв'язаний список кращий за масив, коли:

• дані часто змінюються,
• розмір непередбачуваний,
• пам'ять фрагментована,
• потрібен швидкий доступ для вставок і видалень.

А масив кращий, якщо потрібен швидкий доступ за індексом і висока щільність зберігання.