Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «У яких задачах краще використовувати список, а не масив?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)Використовувати **зв'язаний список** замість масиву вигідно там, де **важлива гнучкість структури й часті зміни даних**, а не швидкий доступ за індексом. **Ключове:** зв'язаний список кращий за масив, коли дані часто змінюються, розмір непередбачуваний, пам'ять фрагментована або потрібен швидкий доступ для вставок і видалень; масив кращий, якщо потрібен швидкий доступ за індексом і висока щільність зберігання.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)ЗображенняВикористовувати **зв'язаний список** замість масиву вигідно там, де **важлива гнучкість структури й часті зміни даних**, а не швидкий доступ за індексом. Ось конкретні випадки, коли список кращий за масив. --- ### **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`. **Приклад задач:** - Реалізація **стека**, де додавання й видалення - завжди з "голови". --- **Підсумок:** > Зв'язаний список кращий за масив, коли: > > - дані часто змінюються, > - розмір непередбачуваний, > - пам'ять фрагментована, > - потрібен швидкий доступ для вставок і видалень. > > А масив кращий, якщо потрібен **швидкий доступ за індексом** і **висока щільність зберігання**.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.