Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Яка складність вставки в кінець списку?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)Складність **вставки в кінець зв'язаного списку** залежить від того, **чи зберігається вказівник на останній елемент (**`tail`**)**. **Ключове:** вставка в кінець виконується за O(1), якщо є вказівник `tail`, і за O(n), якщо потрібно проходити весь список до кінця.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)ЗображенняСкладність **вставки в кінець зв'язаного списку** залежить від того, **чи зберігається вказівник на останній елемент (**`tail`**)**. --- ### **1. Якщо** `tail` **відсутній** (тільки `head` - як у простому однозв'язному списку) Щоб додати новий елемент у кінець, потрібно: 1. Почати з `head`; 2. Пройти всі вузли, поки не знайдеш останній (`next = None`); 3. Додати новий вузол і зв'язати його. Це вимагає пройти **весь список** - **Складність: O(n)**. --- ### **2. Якщо** `tail` **зберігається окремо** (структура списку містить обидва вказівники: `head` і `tail`) Тоді: 1. Створюється новий вузол; 2. Поточний `tail.next` вказує на нього; 3. `tail` оновлюється на новий вузол. Усе виконується за **постійний час** - **Складність: O(1)**. --- ### **3. Для двозв'язного списку** Та сама логіка: - без `tail` - **O(n)**; - з `tail` - **O(1)**. --- ### **Порівняння з масивом** | Структура | Вставка в кінець | |---|---| | Масив (динамічний) | амортизовано **O(1)**, але іноді **O(n)** при розширенні | | Зв'язаний список з `tail` | **O(1)** | | Зв'язаний список без `tail` | **O(n)** | --- **Підсумок:** > Вставка в кінець зв'язаного списку виконується: > • за **O(1)**, якщо є вказівник `tail`, > • за **O(n)**, якщо потрібно проходити весь список до кінця.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.