Список List<T>

Пояснює колекцію List<T>: створення списків, ініціалізацію, ємність, індексований доступ, перебір, основні методи додавання, видалення, пошуку, копіювання та розвороту елементів.

10.1. Список List

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

Клас List<T> із простору імен System.Collections.Generic вирішує цю проблему: він надає динамічний масив — структуру, що автоматично розширюється при потребі, зберігаючи при цьому зручний індексований доступ. List<T> є найбільш уживаною колекцією в C# і в більшості задач є правильним вибором за замовчуванням.

Внутрішня структура: динамічний масив

List<T> — це не магія. Всередині він зберігає звичайний масив T[]. Але коли цей масив заповнюється, List<T> автоматично виконує три кроки:

Виділяє новий масив вдвічі більшого розміру.
Копіює всі існуючі елементи в новий масив.
Відпускає старий масив — він стає кандидатом для збирача сміття.

Уточнимо, звідки починається це подвоєння. Список, створений конструктором без параметрів, взагалі не виділяє масиву: його Capacity дорівнює 0 (усередині — спільний порожній масив). Перший Add виділяє буфер на 4 елементи, а далі ємність при кожному заповненні подвоюється: 4 → 8 → 16 → 32 і так далі. Саме цю послідовність показує схема нижче: при Count = Capacity = 4 наступний Add(P5) створює масив на 8 комірок і копіює туди чотири наявні елементи.

Тому List<T> має дві характеристики розміру:

Count — кількість реальних елементів у списку. Саме це значення повертається при list.Count.
Capacity — розмір внутрішнього масиву-буфера (скільки елементів можна вмістити до наступного розширення).

List<T>: динамічний масив — Capacity vs Count

Стратегія подвоєння забезпечує амортизовану O(1) складність для Add: більшість операцій записують елемент у вільний слот (O(1)), а перевиділення пам'яті відбувається log₂(n) разів за n додавань. Якщо ви знаєте заздалегідь скільки елементів очікується — вкажіть Capacity у конструкторі, щоб уникнути зайвих перевиділень:

List<Patient> patients = new List<Patient>(500); // буфер одразу на 500

Зворотна операція — TrimExcess(): якщо список уже наповнено і більше не зростатиме, цей метод зменшує Capacity до Count (точніше — робить це, коли зайвого місця понад 10 %), щоб не тримати в пам'яті порожні комірки.

Складність ключових операцій

Операція	Складність	Причина
`Add(item)`	O(1)*	Запис у кінець; * амортизована
`list[i]`	O(1)	Прямий доступ за індексом
`Insert(i, item)`	O(n)	Зсув елементів праворуч від i
`Remove(item)`	O(n)	Лінійний пошук + зсув
`RemoveAt(i)`	O(n)	Зсув елементів ліворуч від i
`Contains(item)`	O(n)	Лінійний пошук
`Sort()`	O(n log n)	IntroSort, нестабільне

Варто знати, як саме сортує List<T>.Sort(). Це інтроспективне сортування (IntroSort): воно починає як швидке сортування (QuickSort), на дуже глибокій рекурсії перемикається на пірамідальне (HeapSort), а малі відрізки дочищає сортуванням вставками. Так гарантується O(n log n) навіть у найгіршому випадку, на якому «чистий» QuickSort деградує до O(n²). Важливий наслідок: сортування нестабільне — елементи з однаковим ключем можуть помінятися місцями відносно початкового порядку. Якщо порядок рівних важливий (наприклад, пацієнти з однаковим пріоритетом мають лишитися в порядку надходження), використовуйте стабільне сортування OrderBy з LINQ або додавайте до порівняння другий ключ.

Вставка і видалення в середині — O(n). Це ключовий момент: якщо операції вставки/видалення в середині часті — розгляньте LinkedList<T>. Якщо потрібен тільки швидкий пошук — Dictionary<K,V>.

Синтаксис: створення та ініціалізація

List<T> типізується елементом, що зберігається:

// Порожній список
List<string> diagnoses = new List<string>();

// Ініціалізація з елементами одразу
var diagnoses = new List<string> { "Гіпертонія", "Діабет", "Аритмія" };

// Заданою початковою ємністю (без елементів!)
var patients = new List<Patient>(100);

// З іншої колекції або масиву
string[] arr = { "P001", "P002" };
var ids = new List<string>(arr);

У C# 9+ допускається new() без повторення типу, якщо він виводиться з контексту:

List<string> list = new() { "A", "B", "C" };

Основні операції: CRUD пацієнтів у відділенні

Пошук, фільтрація, сортування

List<T> містить методи вищого порядку, що приймають предикати — делегати або лямбда-вирази:

Методи Find, FindAll, Exists, RemoveAll приймають Predicate<T> — делегат виду bool(T item). Зазвичай передається лямбда. Це значно виразніше, ніж ручний цикл з перевіркою умови.

Довідник методів

Метод	Що робить	Складність
`Add(item)`	Додати в кінець	O(1)*
`AddRange(coll)`	Додати колекцію в кінець	O(k)
`Insert(i, item)`	Вставити за індексом	O(n)
`InsertRange(i, coll)`	Вставити колекцію за індексом	O(n+k)
`Remove(item)`	Видалити перше входження	O(n)
`RemoveAt(i)`	Видалити за індексом	O(n)
`RemoveRange(i, count)`	Видалити діапазон	O(n)
`RemoveAll(pred)`	Видалити всі що відповідають умові	O(n)
`Clear()`	Очистити список	O(n)
`Contains(item)`	Чи є елемент	O(n)
`Exists(pred)`	Чи є елемент що відповідає умові	O(n)
`Find(pred)`	Перший що відповідає умові	O(n)
`FindLast(pred)`	Останній що відповідає умові	O(n)
`FindAll(pred)`	Всі що відповідають умові	O(n)
`IndexOf(item)`	Індекс першого входження	O(n)
`GetRange(i, count)`	Підсписок	O(k)
`Sort()`	Сортування	O(n log n)
`Reverse()`	Розвернути порядок	O(n)
`CopyTo(arr)`	Скопіювати в масив	O(n)
`BinarySearch(item)`	Бінарний пошук (список має бути відсортованим)	O(log n)

Коли List, а коли масив?

Критерій	`List<T>`	`T[]` (масив)
Розмір відомий наперед	Можна обидва	Масив дещо ефективніший
Розмір змінюється	List	Незручний — треба перевиділяти
Часте додавання в кінець	List	Масив не підходить
Мінімальний overhead пам'яті	Масив	—
Потрібен `foreach` + LINQ	Обидва (обидва `IEnumerable`)	—
Повернення з методу	Обидва	—

Загальна рекомендація: за замовчуванням використовуйте List<T>. Переходьте на масив лише коли є конкретна причина: фіксований розмір відомий наперед і продуктивність критична.