Linijni-spiski-Osnovi-programuvannya

1.

Лінійні списки: Основи
програмування
Презентація виконана студентами групи 213-КІ: Гурова Анастасія та Макаренко
Дар'я. У цій добірці слайдів ми покроково розглянемо, що таке лінійні списки, їхні
основні типи, структуру, ключові операції та приклади коду. Мета — дати чітке,
практичне розуміння теми, яке буде корисне для лабораторних робіт та
підготовки до іспитів.
Теми: визначення, типи списків, структура вузла, операції (вставка, видалення,
пошук), приклади коду на Python та C++, поширені помилки й оптимальні
практики.

2.

Що таке лінійний список?
Лінійний список — це базова структура даних, де елементи розташовані послідовно і пов'язані один з одним за допомогою посилань. Кожен
елемент (вузол) зазвичай містить поле з даними та вказівник (посилання) на наступний вузол у списку. Така структура зручна для
динамічного додавання і видалення елементів без пересування великих масивів пам'яті.
Компоненти вузла
Динамічна структура
Вузол містить дані (value) і посилання next. У
Пам'ять виділяється під кожен вузол окремо —
двозв'язних списках додається prev.
це дає ефективність при зміні розміру списку.
Переваги: легкість вставки/видалення, простота реалізації. Недоліки: повільний випадковий доступ, додаткові витрати пам'яті на вказівники.

3.

Типи лінійних списків
Однозв'язний список
Кожен вузол має посилання лише на наступний вузол. Простий, економний по пам'яті,
підходить для однонаправлених операцій.
Двозв'язний список
Кожен вузол має два посилання: next і prev. Дозволяє швидко переміщатися в обох
напрямках, але потребує більше пам'яті.
Кільцевий список
Останній вузол посилається на перший. Зручно для циклів і обробки, де потрібно
"зациклити" колекцію.
Кожен тип має свої сценарії використання: черги, стекоподібні структури, буфери, реалізація
складних колекцій.

4.

Однозв'язний список: Структура
Ключові терміни: Head — вказівник на перший вузол; Tail — вказівник на останній
вузол (не завжди використовується); Node — елемент зі значенням і вказівником
next. Ініціалізація порожнього списку: head = None.
Head
Початок списку,
важливий для
доступу до всіх
вузлів.
Tail
Node
Швидкий доступ до
Має fields: data, next.
кінця списку для
ефективних вставок
у кінець (за
наявності).
При роботі зі списком слід уважно працювати з граничними випадками: порожній
список, один елемент, вставка/видалення на початку або в кінці.

5.

Приклад коду: Створення вузла (Python)
Нижче — розгорнутий приклад класів Node та LinkedList з коментарями.
Код демонструє створення вузла, додавання в кінець, вивід списку.
Коментарі пояснюють логіку та граничні випадки.
class Node:
def __init__(self, data):
self.data = data
self.next = None
# значення вузла
# вказівник на наступний вузол
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def to_list(self):
result = []
current = self.head
while current:
result.append(current.data)
current = current.next
return result
Пояснення: append проходить список до кінця і додає новий вузол. to_list корисний для перевірки та відладки.

6.

Приклад коду: Вставка та видалення (C++)
Нижче — фрагменти на C++, які ілюструють вставку на початок і видалення вузла зі значенням key. Ці операції
часто використовуються під час реалізації алгоритмів і тестуються на крайніх випадках.
struct Node {
int data;
Node* next;
Node(int d): data(d), next(nullptr) {}
};
void push_front(Node*& head, int new_data) {
Node* new_node = new Node(new_data);
new_node->next = head;
head = new_node;
}
void delete_value(Node*& head, int key) {
Node* temp = head;
Node* prev = nullptr;
while (temp && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (!temp) return; // не знайдено
if (!prev) head = temp->next; else prev->next = temp->next;
delete temp;
}
Порада: завжди звільняйте пам'ять (delete) у C++ і перевіряйте указівники на nullptr, щоб уникнути витоків і аварій.

7.

Операції: пошук, вставка,
видалення
Пошук
Лінійний пошук послідовно проходить вузли. Середня складність O(n).
Використовується, коли індексація недоступна.
Вставка
Вставка на початок — O(1). Вставка в кінець без tail — O(n); з tail — O(1).
Видалення
Видалення за значенням вимагає попередника — знаходження
попереднього елементу робить операцію O(n).
Коротка памятка: в аналізі складності враховуйте пошук попередника і оновлення
вказівників — це джерело помилок при реалізації.

8.

Типові помилки та підводні
камені
Невірне оновлення head або tail при вставці/видаленні перших або останніх
елементів.
Відсутність перевірки на порожній список (nullptr / None).
У C++ — забуте видалення (delete) або подвійне видалення.
Пошкодження next внаслідок неправильного порядку операцій (втрата
посилання на залишок списку).
Ігнорування циклів у кільцевих списках — бескінечні петлі при ітерації.
Рекомендації: писати тести для крайніх випадків, використовувати тимчасові
змінні перед перепризначенням вказівників, і коментувати складні кроки
алгоритму.

9.

Розворот списку (reverse): ідея та
реалізація
Одна з найпопулярніших задач — розвернути зв'язаний список за місцем. Ідея:
ітерувати по списку й послідовно міняти напрямок вказівників, зберігаючи три
змінні: prev, current, next. Складність O(n), додаткова пам'ять O(1).
# Python: reverse inplace
def reverse(head):
prev = None
current = head
while current:
nxt = current.next
current.next = prev
prev = current
current = nxt
return prev
# новий head
Перевіряйте результат на порожньому списку та на списку з одним елементом; ці
випадки повинні повертати коректний head.

10.

Висновки та наступні кроки
Лінійні списки — критична базова структура даних, що формує фундамент для
складніших колекцій (стек, черга, декий графові структури). Вони дають гнучкість
при динамічних операціях, але вимагають обережності з указівниками та
пам'яттю. Для поглиблення рекомендуємо:
1.
Реалізувати одно- та двозв'язні списки з тестами (Python, C++).
2. Розглянути кільцеві списки у задачах з буферами та потоками.
3. Проаналізувати варіанти використання tail для оптимізації вставок.
4. Відпрацювати розворот списку, видалення по значенню і пошук — написати
юніт-тести.
Контакти авторів презентації: Гурова Анастасія, Макаренко Дар'я. Група 213-КІ.
Дякуємо за увагу!