Двозв'язаний список LinkedList<T>

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

List<T> — потужна колекція загального призначення, але вона побудована на масиві. Це означає, що вставка або видалення елемента не в кінці списку вимагає зсуву всіх сусідніх елементів: O(n) за часом. Якщо ваш алгоритм часто додає або видаляє елементи на початку, у кінці або після конкретного відомого елемента — LinkedList<T> може бути значно ефективнішим вибором.

Клас LinkedList<T> з простору імен System.Collections.Generic представляє двозв'язний список — лінійну структуру даних, в якій кожен елемент зберігає посилання одночасно на наступний і попередній елемент. Завдяки цьому вставка та видалення на відомій позиції виконуються за O(1) — без жодних зсувів.

Внутрішня структура

На відміну від List<T>, де елементи зберігаються в суцільному масиві пам'яті, LinkedList<T> зберігає кожен елемент окремо у вигляді вузла — об'єкта класу LinkedListNode<T>. Вузли з'єднані між собою посиланнями: кожен знає свого сусіда ліворуч і праворуч. Сам список зберігає лише два покажчики — на голову (перший вузол) і хвіст (останній вузол).

Коли потрібно вставити вузол між двома існуючими, достатньо переписати чотири посилання — без копіювання даних. Саме тому вставка і видалення на відомій позиції — O(1). Але є і зворотний бік: індексований доступ (list[i]) відсутній — щоб дістатись до i-го елемента, треба пройти від голови до нього крок за кроком, що дає O(n).

LinkedListNode: вузол списку

Якщо у List<T> кожен елемент — це просто значення типу T, то в LinkedList<T> кожен елемент обгортається у вузол LinkedListNode<T>. Саме через вузли виконуються всі операції вставки після/перед конкретним елементом.

Клас LinkedListNode<T> має три властивості:

• Value — значення вузла типу T. Єдине місце, де зберігається сам елемент.
• Next — посилання на наступний вузол типу LinkedListNode<T>. У хвостового вузла — null.
• Previous — посилання на попередній вузол типу LinkedListNode<T>. У головного вузла — null.

Зберігши посилання на конкретний вузол у змінній, ви отримуєте точку вставки: можна додати нового сусіда за O(1), не шукаючи позицію повторно.

Властивості LinkedList

Сам клас LinkedList<T> визначає три властивості:

• Count — кількість елементів у списку.
• First — перший вузол списку як об'єкт LinkedListNode<T>. Для порожнього списку — null.
• Last — останній вузол списку. Для порожнього списку — null.

Створення та ініціалізація

LinkedList<T> можна створити порожнім або ініціалізувати з будь-якої колекції, що реалізує IEnumerable<T>:

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

// З іншої колекції
var names = new List<string> { "Петренко", "Коваль", "Сидоренко" };
LinkedList<string> fromList = new LinkedList<string>(names);

// З масиву
LinkedList<string> fromArray = new LinkedList<string>(new[] { "A", "B", "C" });

Обхід вперед і назад — runnable приклад

Одна з практичних переваг LinkedList<T> — можливість рухатись у будь-якому напрямку через властивості Next і Previous. Це корисно, наприклад, при роботі з хронологічними записами, де потрібен перегляд як від найстаршого до найновішого, так і у зворотному порядку:

Методи LinkedList

LinkedList<T> надає повний набір методів для роботи з вузлами. Ключова особливість: методи AddAfter, AddBefore, Remove(node) приймають вузол (LinkedListNode<T>), а не значення — тому для цільової вставки потрібно спочатку отримати або зберегти посилання на вузол.

Додавання:

• AddFirst(T value) / AddFirst(LinkedListNode<T> node) — вставляє на початок списку.
• AddLast(T value) / AddLast(LinkedListNode<T> node) — вставляє в кінець списку.
• AddAfter(LinkedListNode<T> node, T value) / AddAfter(node, LinkedListNode<T> newNode) — вставляє після вказаного вузла.
• AddBefore(LinkedListNode<T> node, T value) / AddBefore(node, LinkedListNode<T> newNode) — вставляє перед вказаним вузлом.

Всі методи Add* повертають LinkedListNode<T> — посилання на щойно створений вузол. Збережіть його, якщо плануєте звертатись до цього вузла пізніше.

Видалення:

• RemoveFirst() — видаляє перший вузол. Новим першим стає наступний за ним.
• RemoveLast() — видаляє останній вузол.
• Remove(LinkedListNode<T> node) — видаляє конкретний вузол за посиланням: O(1).
• Remove(T value) — знаходить перший вузол із вказаним значенням і видаляє його: O(n).

Пошук:

• Find(T value) — повертає перший LinkedListNode<T> із заданим значенням або null.
• FindLast(T value) — повертає останній відповідний вузол.
• Contains(T value) — перевіряє, чи є значення у списку.

Інше:

• Clear() — очищає весь список.
• CopyTo(T[] array, int index) — копіює елементи в масив.

Маніпуляції з хірургічною чергою — runnable приклад

Розглянемо реалістичний сценарій: черга на хірургічну операцію, де нові пацієнти можуть додаватись як планово (в кінець), так і позачергово (на початок або після конкретного пацієнта):

Складність операцій

Ключовий висновок: LinkedList<T> виграє там, де List<T> витрачає O(n) на зсув елементів — а саме при роботі з початком і серединою колекції. Але LinkedList<T> програє, де потрібен прямий доступ за індексом: його просто немає.

Також слід враховувати витрати пам'яті: кожен вузол LinkedListNode<T> додатково зберігає два посилання (Next і Previous), що збільшує споживання пам'яті порівняно з List<T>, де елементи зберігаються щільно в масиві.

Коли LinkedList, а коли List?

Сценарій	Рекомендація
Часте додавання/видалення на початку або в середині	LinkedList — O(1) після знаходження вузла
Реалізація черги з пріоритетами (вставка між елементами)	LinkedList — природна модель
Потрібен доступ за індексом (list[i])	List — O(1) vs відсутність у LinkedList
Більшість операцій — додавання в кінець і читання	List — менший overhead пам'яті
Колекція невелика (< 100 елементів)	List — різниця несуттєва, код простіший
LINQ-запити, сортування, пошук за умовою	List — краща підтримка в стандартній бібліотеці

Загальна рекомендація: за замовчуванням використовуйте List<T>. Обирайте LinkedList<T> лише тоді, коли профіль операцій вашого алгоритму явно вигравав би від O(1) вставки/видалення на краях або після відомого вузла — і ви готові пожертвувати індексованим доступом та додатковою пам'яттю.