Питання для самоконтролю — Розділ 10. Колекції

10.1. Список List

Що таке List<T> з точки зору внутрішньої реалізації? Поясніть різницю між Count і Capacity. Що відбувається, коли Count досягає Capacity?

Що виведе наступний код? Поясніть складність кожної операції.

var list = new List<string> { "А", "Б", "В" };
list.Insert(0, "Початок");
list.Remove("Б");
list.Add("Г");
Console.WriteLine(list.Count);
Console.WriteLine(list[0]);

Поясніть стратегію подвоєння ємності в List<T>. Чому складність Add є амортизованою O(1), а не завжди O(1)?
Порівняйте List<T> і T[] (масив) за такими критеріями: зміна розміру, індексований доступ, частота вставки в середину. Коли варто обирати масив?
Чим відрізняються методи Remove(item) і RemoveAt(i)? Яка складність кожного і чому?
Напишіть код, який з колекції List<Patient> (де Patient має поля Name та IsActive) видаляє всіх неактивних пацієнтів одним викликом методу. Який метод для цього потрібен?
Поясніть, що таке Predicate<T> і як він використовується в методах Find, FindAll, Exists, RemoveAll. Наведіть приклад лямбда-вираза для кожного.
Якщо відомо наперед, що список міститиме близько 10 000 елементів, як ефективно ініціалізувати List<T>, щоб уникнути зайвих перевиділень пам'яті? Запишіть відповідний код.

10.2. Двозв'язаний список LinkedList

Що таке двозв'язаний список і як він відрізняється від List<T> на рівні внутрішньої структури? Що зберігає LinkedListNode<T> крім самого значення?
Поясніть, чому вставка та видалення у LinkedList<T> на відомій позиції є O(1), тоді як пошук конкретного елемента — O(n).

Що виведе наступний код?

var list = new LinkedList<int>(new[] { 1, 2, 3, 4 });
var node = list.Find(2);
list.AddAfter(node, 99);
list.RemoveFirst();
Console.WriteLine(list.First.Value);
Console.WriteLine(list.Count);

Поясніть різницю між Remove(T value) і Remove(LinkedListNode<T> node) у LinkedList<T>. Яка складність кожного варіанту і чому?
Для якого сценарію LinkedList<T> є кращим вибором ніж List<T>? Наведіть конкретний приклад задачі (не з лекції), де це дає реальну перевагу у складності.
Реалізуйте функцію обходу LinkedList<string> у зворотному порядку (від Last до First) через цикл while. Яка властивість вузла для цього потрібна?
Порівняйте LinkedList<T> і List<T> за витратами пам'яті. Чому LinkedList<T> використовує більше пам'яті на один елемент?
Ситуація: вам потрібна черга з пріоритетами, де ургентні пацієнти вставляються на початок, а планові — в кінець. Яку колекцію обрати і чому?

10.3. Черга Queue

Що означає принцип FIFO? Поясніть його на прикладі черги пацієнтів у реєстратурі. Які два методи є ключовими для Queue<T>?
Яка внутрішня структура Queue<T> і чому видалення з початку (Dequeue) є O(1), на відміну від List<T>.RemoveAt(0) — O(n)?

Що виведе наступний код? Що станеться при останньому Dequeue?

var q = new Queue<string>();
q.Enqueue("Перший");
q.Enqueue("Другий");
q.Enqueue("Третій");
Console.WriteLine(q.Dequeue());
Console.WriteLine(q.Peek());
Console.WriteLine(q.Count);
q.Dequeue();
q.Dequeue();
q.Dequeue(); // черга порожня!

Чим TryDequeue відрізняється від Dequeue? Коли слід використовувати Try-варіант?
Поясніть різницю між Peek() і Dequeue(). Для чого корисний Peek() у реальному коді?
Напишіть клас AppointmentQueue, який обгортає Queue<Patient> і має методи: Enqueue(Patient), ServeNext() (обслуговує і повертає наступного пацієнта або null, якщо черга порожня), Count.
Реалізація черги через List<T> з видаленням через RemoveAt(0) — чому це антипатерн при великій кількості елементів? Оцініть складність для N операцій.
У яких ситуаціях Queue<T> є неправильним вибором? Наведіть конкретні сценарії, де краще підійдуть Stack<T> або List<T>.

10.4. Stack

Що означає принцип LIFO? Наведіть два практичних приклади з реального програмування (не з лекції), де LIFO є природньою моделлю.

Що виведе наступний код? Поясніть порядок виведення.

var stack = new Stack<string>();
stack.Push("А");
stack.Push("Б");
stack.Push("В");
foreach (var item in stack)
    Console.Write(item + " ");
Console.WriteLine();
Console.WriteLine(stack.Pop());
Console.WriteLine(stack.Peek());

Stack<T> ініціалізується з List<string> { "А", "Б", "В" }. Який елемент стане вершиною і чому? Перевірте свою відповідь логікою.
Поясніть внутрішню структуру Stack<T>: чому Push і Pop є O(1), і в якому випадку виникає O(n)?
Реалізуйте функцію bool IsBalanced(string expression), яка перевіряє правильність розстановки дужок ()[]{} через Stack<char>.
Порівняйте Stack<T> і Queue<T> за такими критеріями: принцип обробки, типовий сценарій, методи додавання/вилучення, поведінка foreach.
Чому ToArray() у Stack<T> повертає елементи у порядку LIFO (вершина першою)? Як це може ввести в оману програміста?
Спроєктуйте клас HistoryNavigator<T>, який через Stack<T> реалізує функціональність "назад/вперед": методи Navigate(page), GoBack(), GoForward(). Які стеки потрібні?

10.5. Словник Dictionary

Що таке хеш-таблиця і як вона забезпечує O(1) пошук за ключем? Поясніть поняття бакету і колізії.

Що виведе наступний код? Знайдіть потенційну проблему.

var dict = new Dictionary<string, int> { ["A"] = 1, ["B"] = 2 };
dict["C"] = 3;
dict["A"] = 10;
Console.WriteLine(dict["A"]);
Console.WriteLine(dict["D"]); // ?

Поясніть різницю між dict["key"] і dict.TryGetValue("key", out var value). Коли виникне виняток при першому варіанті?
Чим Add(key, value) відрізняється від dict[key] = value при вже існуючому ключі? Що відбудеться в кожному випадку?
Напишіть метод Dictionary<string, int> CountDiagnoses(List<Patient> patients), який підраховує, скільки разів зустрічається кожен діагноз. Використайте TryGetValue або ContainsKey.
Поясніть, чому метод ContainsValue є O(n), тоді як ContainsKey — O(1). Як це пов'язано з внутрішньою структурою словника?
Що таке HashSet<T> і чим він відрізняється від Dictionary<K, V>? Наведіть три сценарії, де HashSet<T> є більш підходящим вибором, ніж List<T>.
Для правильної роботи Dictionary<K, V> тип ключа K повинен коректно реалізовувати два методи. Які саме і чому? Що відбудеться, якщо власний клас використовується як ключ без перевизначення цих методів?

10.6. Клас ObservableCollection

Яку ключову проблему вирішує ObservableCollection<T>, яку не вирішує List<T>? В яких фреймворках і технологіях вона є обов'язковою?
Що таке подія CollectionChanged і який об'єкт вона передає підписникам? Перелічіть типи дій (Action), про які сигналізує ця подія.

Що виведе наступний код? У якому порядку з'являться повідомлення?

var col = new ObservableCollection<string>();
col.CollectionChanged += (s, e) =>
    Console.WriteLine($"{e.Action}: {e.NewItems?[0] ?? e.OldItems?[0]}");
col.Add("Петренко");
col.Add("Коваль");
col.Remove("Петренко");
col[0] = "Мельник";

Чим метод Move(oldIndex, newIndex) відрізняється від RemoveAt + Insert? Чому він є унікальним для ObservableCollection<T> і чому він важливий для UI?
Порівняйте ObservableCollection<T> і List<T> за такими критеріями: сповіщення про зміни, методи, застосування, продуктивність при пакетних операціях.
Поясніть антипатерн: чому не слід додавати 10 000 елементів до ObservableCollection<T> по одному в циклі? Як правильно вирішити цю задачу?
Напишіть клас WardMonitor, який підписується на CollectionChanged і веде рахунок поточної кількості пацієнтів (враховуючи Add, Remove, Reset).
В якому просторі імен знаходиться ObservableCollection<T>? Чим він відрізняється від System.Collections.Generic? Що потрібно додати у using?

10.7. Інтерфейси IEnumerable та IEnumerator

Що таке IEnumerable<T> і IEnumerator<T>? Яку роль кожен з них грає в роботі foreach?
Запишіть, у що компілятор розгортає наступний foreach:
```
foreach (var p in ward)
    Console.WriteLine(p);
```
Перелічіть методи та властивості, що викликаються.
Що таке відкладене виконання (deferred execution) в контексті IEnumerable<T>? Чому наступний код виводить [Generator] після рядка "Отримали IEnumerable"?
```
IEnumerable<int> Gen() { Console.WriteLine("[Generator]"); yield return 1; }
var seq = Gen();
Console.WriteLine("Отримали IEnumerable");
foreach (var x in seq) Console.WriteLine(x);
```
Поясніть, що таке «подвійна пастка» відкладеного виконання. Коли виклик foreach двічі по одному IEnumerable<T> може призвести до подвійного запиту до бази даних?
Реалізуйте клас EvenNumbers : IEnumerable<int>, який перебирає парні числа від 0 до заданого max. Використайте yield return в GetEnumerator.
Що містить інтерфейс IEnumerator<T>: методи і властивості? Чому foreach загортає виклики в try/finally з Dispose()?
Порівняйте оголошення параметра методу як IEnumerable<T> та List<T>. Який варіант є більш гнучким і чому? Коли все ж потрібен конкретний тип?

Знайдіть і поясніть помилку у наступному коді:

IEnumerable<string> GetFromDb() { /* дорогий запит */ yield return "A"; yield return "B"; }
var results = GetFromDb();
int count = results.Count(); // System.Linq
foreach (var r in results) Console.WriteLine(r);

10.8. Ітератори та yield return

Що таке ітераторний метод і які умови робить звичайний метод ітераторним? Що компілятор генерує замість методу з yield return?
Поясніть різницю між yield return і yield break. Коли потрібен yield break?

Що виведе наступний код? Поясніть порядок виведення крок за кроком.

IEnumerable<int> Numbers()
{
    Console.WriteLine("Старт");
    yield return 1;
    Console.WriteLine("Після 1");
    yield return 2;
    Console.WriteLine("Після 2");
}
foreach (var n in Numbers())
    Console.WriteLine($"Отримано: {n}");

Поясніть, як компілятор перетворює ітераторний метод на клас-машину стану. Де зберігаються локальні змінні між двома викликами MoveNext()?
Напишіть ітераторний метод IEnumerable<T> TakeWhile<T>(IEnumerable<T> source, Func<T, bool> predicate), який повертає елементи доки виконується умова, а потім зупиняється через yield break.
Порівняйте yield return з явним написанням класу IEnumerator<T> за обсягом коду, читабельністю та можливостями. В яких 5% випадків явний IEnumerator<T> все ж кращий?
Спроєктуйте ітераторний метод IEnumerable<Patient> GetCritical(IEnumerable<Patient> all, int minSeverity), який лінивим чином фільтрує пацієнтів. Чому це краще за FindAll у контексті великих послідовностей?
Що відбудеться, якщо викликати foreach двічі по одному і тому ж ітераторному методу? Чи виконається тіло методу двічі? Як це пов'язано з GetEnumerator()?