Лінійний однозв’язний список. Загальні відомості. Базові операції над списком
Зміст
- 1. Поняття про однозв’язний список. Особливості кодування. Базові операції над списком
- 2. Загальний вигляд списку. Структура, що описує один елемент списку
- 3. Формування списку
- 4. Вставка елементу в задану позицію списку
- 5. Видалення елементу зі списку в заданій позиції
- Споріднені теми
Пошук на інших ресурсах:
1. Поняття про однозв’язний список. Особливості кодування. Базові операції над списком
Однозв’язний список є динамічною структурою даних, яка реалізує формування та обробку набору елементів. Елементи однозв’язного списку можуть бути посортованими або не посортованими.
Однозв’язний список може зберігатися:
- в оперативній пам’яті;
- у файлі.
В однозв’язному списку виділяють окремий елемент (Element), який ще називається вузол (Node).
Кожен елемент (вузол) однозв’язного списку складається з двох частин:
- дані. Це може бути змінна будь-якого примітивного типу (int, double, char, …), об’єкт класу чи складна структура. Дані можуть складатися з декількох полів (змінних);
- адреса або позиція наступного елементу. Якщо однозв’язний список зберігається в оперативній пам’яті, то це є покажчик (адреса) на такий самий елемент (вузол). Якщо однозв’язний список зберігається в файлі, то це є позиція наступного елементу в файлі.
Реалізувати вузол можна з допомогою класу або структури. Також можна створювати однозв’язний список на основі шаблонного класу, який оперує деяким узагальненим типом T.
Сукупність елементів (вузлів), в яких покажчик попереднього елементу вказує на наступний елемент, утворює однозв’язний список.
Для списку можна виділити наступні основні операції:
- формування списку;
- додавання елементу в кінець списку;
- вставка елементу в задану позицію списку;
- видалення елементу зі списку з заданої позиції;
- очищення списку;
- заміна елементу в списку;
- пошук елементу в списку за індексом чи деяким критерієм.
За бажання перелік операцій можна розширити додавши власні ідеї (наприклад, вставка групи елементів в список, сортування елементів у списку, створення посортованого списку тощо).
⇑
2. Загальний вигляд списку. Структура, що описує один елемент списку
Загальний вигляд лінійного однозв’язного списку зображено на рисунку 1.
Рисунок 1. Загальний вигляд списку
На рисунку 2 зображено структуру Element, що використовується як базовий елемент лінійного однозв’язного списку. В кожному елементі зберігаються дані деякого типу T.
Рисунок 2. Структура Element, що описує один елемент списку з програмним кодом на мові C++
⇑
3. Формування списку
3.1. Створити порожній список
Створення списку включає в себе такі етапи.
1. Оголошення покажчиків на початок та кінець списку.
2. Встановлення нульових значень покажчикам.
3. Встановлення кількості елементів в значення 0.
Рисунок 3. Формування списку: 1) – оголошення покажчиків; 2) – встановлення нульових значень
⇑
3.2. Додавання елементу в кінець списку
При додаванні елементу в кінець списку розглядають 2 можливі ситуації:
- додавання елементу до порожнього списку;
- додавання елементу до непорожнього списку (списку, в якому є елементи).
⇑
3.2.1. Додавання нового елементу в кінець порожнього списку
При додаванні елементу в кінець порожнього списку виділяють наступні операції (рисунок 4):
1. Створити новий елемент. Тут потрібно виділити пам’ять для нового елементу та заповнити її деякими даними (_data). Для цього оголошується покажчик (наприклад, elem):
Element<T>* elem = new Element<T>; elem->data = _data;
2. Встановити покажчик next в нульове значення
elem->next = nullptr;
3. Встановити покажчики begin та end рівними значенню покажчика elem.
begin = end = elem;
4. Збільшити кількість елементів у списку на 1
count++;
Рисунок 4. Додавання елементу в кінець порожнього списку: 1 – створення елементу; 2 – встановлення покажчика next; 3 – встановлення покажчиків begin та end
⇑
3.2.2. Додавання елементу в кінець існуючого списку
Якщо список вже існує, то послідовність кроків що додають елемент до списку, наступна (рисунок 5):
1. Створити новий елемент та заповнити його даними (рисунок 5). Заповнити поля data та next. Створення здійснюється таким самим чином як у випадку з порожнім списком:
Element<T>* elem = new Element<T>; elem->data = _data; elem->next = nullptr;
2. Встановити покажчик next елементу, на який вказує покажчик end, в значення адреси елементу elem (рисунок 6)
end->next = elem;
3. Встановити покажчик end рівним значенню покажчика elem
end = elem;
4. Збільшити кількість елементів у списку на 1
count++;
Вищенаведені кроки більш красномовно відображаються на рисунках 5, 6, 7.
Рисунок 5. Створення елементу та заповнення його даними
Рисунок 6. Зміна покажчика next елементу end
Рисунок 7. Встановлення покажчика end на останній елемент списку
⇑
4. Вставка елементу в задану позицію списку
При вставці елементу в задану позицію списку розглядаються 2 варіанти:
- список порожній (немає елементів);
- список має хоча б один елемент.
Якщо список порожній, то вставка замінюється додаванням першого елементу як описано в пункті 3.2.1.
Якщо у списку є елементи, то тут розглядаються 3 варіанти:
- вставка елементу в першу позицію списку;
- вставка елементу в середині списку;
- вставка елементу за останнім елементом списку. Якщо відбувається вставка за останнім елементом списку, то це є додавання елементу в кінець списку як описано в пункті 3.2.2.
⇑
4.1. Список не порожній. Вставка елементу в першу позицію списку
Якщо відбувається вставка елементу в першу позицію списку, то послідовність операцій наступна:
1. Створити новий елемент (рисунок 8). Виділити пам’ять під новий елемент. Заповнити елемент даними.
// Спроба виділення пам'яті під нову комірку Element<T>* elem = new Element<T>; elem->data = _data;
2. Встановити покажчик next елементу на початок списку (рисунок 9).
elem->next = begin;
3. Встановити початок списку на нову комірку (рисунок 10).
begin = elem;
Усі вищенаведені кроки графічно зображені на рисунках 8, 9, 10.
Рисунок 8. Створення нового елементу. Заповнення полів елементу значеннями
Рисунок 9. Вставка елементу на початок списку. Встановлення поля next рівним адресі першого елементу списку
Рисунок 10. Присвоєння покажчику початку списку адреси новоствореного елементу
⇑
4.2. Список не порожній. Вставка елементу в середину списку
Якщо елемент вставляється перед другою, третьою і т.д. а також останньою позицією списку, то виконуються наступні кроки.
1. Створити елемент. Заповнити поле даних елементу
Element<T>* elem = new Element<T>; elem->data = _data;
2. Визначити позицію елементу, що слідує перед позицією вставки елементу. Отримати покажчик на цю позицію.
Element<T>* elemPrev = Move(index - 1);
тут Move() – метод, що повертає позицію елементу, що знаходиться перед позицією вставки index.
3. Встановити покажчик next елементу elem, який вставляється
elem->next = elemPrev->next;
4. Встановити покажчик next попереднього елементу elemPrev так, щоб він вказував на елемент elem, що вставляється.
elemPrev->next = elem;
Попередні 4 кроки зображено на рисунках 11, 12, 13, 14.
Рисунок 11. Створення елементу. Заповнення елементу даними
Рисунок 12. Вставка елементу в список. Пошук елементу, що слідує перед позицією вставки
Рисунок 13. Вставка елементу в список. Встановлення покажчика next елементу, що вставляється
Рисунок 14. Вставка елементу в список. Встановлення покажчика next елементу, що слідує перед позицією вставки
⇑
5. Видалення елементу зі списку в заданій позиції
Щоб видалити елемент зі списку спочатку робиться перевірка, чи список порожній. Якщо список не порожній (список містить хоча б один елемент), то виконується видалення елементу.
При видаленні елементу зі списку розглядаються 2 можливі ситуації:
- видаляється перший елемент зі списку;
- видаляється не перший елемент зі списку (другий, третій і т.д.).
⇑
5.1. Список не порожній. Видалення першого елементу зі списку
Якщо видаляється перший у списку елемент, то послідовність кроків видалення наступна.
1. Отримати адресу першого елементу (рисунок 15)
Element<T>* delElem = begin;
2. Перемістити покажчик на початок списку begin на наступний елемент
begin = begin->next;
3. Звільнити пам’ять, виділену для елементу delElem
delete delElem;
На рисунках 15, 16, 17 зображено весь процес видалення першого елементу зі списку.
Рисунок 15. Видалення першого елементу зі списку. Крок 1. Створити покажчик на перший елемент
Рисунок 16. Видалення елементу. Крок 2. Зміщення покажчика голови списку на наступний елемент
Рисунок 17. Видалення елементу. Крок 3. Звільнити пам’ять виділену під елемент
⇑
5.2. Список не порожній. Видалення не першого елементу зі списку
Якщо у непорожньому списку видаляється не перший елемент (другий, третій, і т.д., останній), то послідовність кроків наступна.
1. Перемістити покажчик на позицію, що слідує перед видаляємим елементом. Отримати елемент, що передує елементу що видаляється
Element<T>* elemPrev = Move(index - 1);
тут Move() – метод, що повертає елемент за заданою позицією.
2. Запам’ятати елемент який видаляється
Element<T>* elemDel = elemPrev->next;
3. Змістити покажчик next попереднього елементу elemPrev в обхід видаляємого елементу elemDel
elemPrev->next = elemDel->next;
4. Видалити елемент elemDel (звільнити пам’ять, що була виділена для елементу).
delete elemDel;
На рисунках 18, 19, 20, 21 схематично розглянуті вищенаведені кроки.
Рисунок 18. Видалення елементу всередині списку. Перехід на елемент, що слідує перед попереднім
Рисунок 19. Видалення елементу. Отримати елемент, що видаляється
Рисунок 20. Видалення елементу зі списку. Зміщення покажчика next попереднього елементу в обхід видаляємого елементу
Рисунок 21. Видалення елементу зі списку. Звільнення пам’яті, зайнятої під елемент
⇑
Споріднені теми
- Приклад реалізації лінійного однозв’язного списку для узагальненого типу T
- Лінійний двозв’язний список. Загальні відомості. Базові операції над списком
- Лінійний двозв’язний список. Приклад шаблонного класу
- Розробка шаблонного класу, що реалізує стек у вигляді однозв’язного списку
⇑