Реалізація однозв’язного списку на си
Про дносвязний список - структура даних, в якій кожен елемент (вузол) зберігає інформацію, а також посилання на наступний елемент. Останній елемент списку посилається на NULL.
Для нас однозв'язний список корисний тим, що
- 1) Він дуже просто влаштований і все алгоритми інтуїтивно зрозумілі
- 2) однозв'язного список - хороша вправа для роботи з покажчиками
- 3) Його дуже просто візаулізіровать, це дозволяє "в картинках" пояснити алгоритм
- 4) Не дивлячись на свою простоту, одинзв'язні списки часто використовуються в програмуванні, так що це не пусте вправу.
- 5) Ця структуру даних можна визначити рекурсивно, і вона часто використовується в рекурсивних алгоритмах.
Для простоти розглянемо однозв'язний список, який зберігає цілочисельне значення.
Однозв'язний список складається з вузлів. Кожен вузол містить значення і покажчик на наступний вузол, тому подаємо його в якості структури
Щоб не писати кожен раз struct ми визначили новий тип.
Тепер наше завдання написати функцію, яка б збирала список з значень, які ми їй передаємо. Стандартне ім'я функції - push, вона повинна отримувати в якості аргументу значення, яке вставить в список. Нове значення буде завантажувати в початок списку. Кожен новий елемент списку ми повинні створювати на купі. Отже, нам буде зручно мати один покажчик на перший елемент списку.
Спочатку списку немає і покажчик посилається на NULL.
Для додавання нового вузла необхідно
- 1) Виділити під нього пам'ять.
- 2) Поставити йому значення
- 3) Зробити так, щоб він посилався на попередній елемент (або на NULL, якщо його не було)
- 4) Перекинути покажчик head на новий вузол.
1) Створюємо новий вузол
Створили новий вузол, на який посилається локальна змінна tmp
2) Надаємо йому значення