Однозв’язний список на c - it notes
У стандартну бібліотеку C ++ входить чимало основних структур даних. Серед яких ви знайдете списки, стеки, черги, безлічі і інші. Але щоб ефективно користуватися ними, ви повинні добре уявляти особливості їх роботи. Йтиметься про одну з базових структур: однозв'язного списку.
Одинзв'язні списки в теорії
Щоб зрозуміти, як будується однозв'язний список, уявіть собі ланцюг. У ланцюзі є початок і кінець, а також ланки, які послідовно з'єднуються один з одним. Ви легко можете пройти від початку ланцюга до її кінця, переходячи послідовно від однієї ланки до іншого:
Саме так і працюють одинзв'язні списки. Початок списку називають головним елементом, а ланки - вузлами. Кінець списку визначається за допомогою спеціального вузла (NULL). При цьому на кожен вузол "вішають" значення, щоб структура була корисною:
Перевага однозв''язних списків полягає в тому, що вставка і видалення вузлів відносно легко здійснюється в будь-якому місці списку. Однак структура списку обмежує доступ до його вузлів за індексом. Список можна індексувати, як масив. Щоб потрапити на деякий вузол однозв'язного списку, необхідно послідовно пройти весь шлях від головного елемента до потрібного вузла.
Інтерфейс класу однозв'язного списку
Однозв'язний список призначений для зберігання упорядкованого набору однотипних елементів. Щоб не визначати для кожного типу даних свій список, визначимо шаблонний клас:
Наш клас однозв'язного списку буде підтримувати додавання вузла в його початок, видалення останнього доданого вузла і отримання значення головного елемента. Крім того, ми реалізуємо обхід списку за допомогою ітераторів, а також додамо функцію-член для розрахунку довжини списку.
Вузол визначається за допомогою структури Node. яка містить два поля: m_t - значення, прив'язане до вузла, і m_next - покажчик на наступний вузол.
Спочатку список порожній, тому головний елемент вказує на NULL:
Додавання елемента в однозв'язний список
Додавання вузла в однозв'язний список здійснюється в самий початок. Доданий вузол сам стане новим головним елементом списку:
Видалення елемента з однозв'язного списку
При видаленні вузла з однозв'язного списку усікається його головний елемент. Якщо в списку ще залишаються вузли, то новим головним елементом стає вузол, наступний за головним елементом, інакше залишається NULL:
Список є динамічною структурою. При додаванні нових вузлів виділяється пам'ять з купи, яку потрібно звільнити, щоб не створювати витоків пам'яті. Маючи функцію видалення елементів, реалізувати деструктор однозв'язного списку зовсім не складно:
Итератор однозв'язного списку
Функціональність для додавання / видалення вузлів в список краще не змішувати з завданням його обходу. Для цього існують ітератори. Створимо итератор однозв'язного списку в стилі C ++. Повернемося до його визначенню, яке раніше пропустили:
Як ітераторів для початку і кінця списку повернемо наступне:
Тепер список легко можна обійти від початку до кінця. Але не забудемо про функцію для обчислення його довжини. Скористаємося механізмом ітераторів, щоб спростити завдання:
висновок
Враховуйте, що розглянутий приклад є лише короткою демонстрацією принципів роботи з однозв'язного списком в C ++. У реальних програмах практично завжди краще використовувати стандартну бібліотечну реалізацію списку і будь-який інший структури даних. Тоді вам не тільки потрібно робити менше роботи, але ви отримаєте в розпорядження добре налагоджену і оптимізовану версію, якої зможете сміливо користуватися.