Лінійний двохзв’язний (двонаправлений) список. Загальні відомості

У даній темі описуються основні операції, що виконуються над лінійним двохз’язним (двонаправленим) списком. Продовженням даної теми є практичний приклад реалізації класу List<T>, який можна знайти за наступним посиланням:

Лінійний двозв’язний список. Приклад шаблонного класу

Зміст

Пошук на інших ресурсах:

1. Загальний вигляд двохзв’язного списку. Базовий елемент списку. Рисунок

У двохзв’язному списку базовий елемент списку (вузол) має наступні поля:

data – дані. Даними може бути будь-яке значення будь-якого типу;
next – покажчик на наступний елемент;
prev – покажчик на попередній елемент.

Рисунок 1. Базовий елемент списку

На мові C++ (та і на інших мовах) двозв’язний список створюється розробкою спеціального класу. У класі базовими даними, що представляють список, є:

begin – покажчик на перший елемент списку;
end – покажчик на останній елемент списку;
count – кількість елементів у списку.

Загальний вигляд двохзв’язного списку зображено на рисунку 2.

Рисунок 2. Загальний вигляд двозхв’язного списку

⇑

2. Створення списку

Перед додаванням нових елементів у список першочерговою задачею є створення порожнього списку.

При створенні списку можна виділити такі етапи:

оголошення покажчиків на початок та кінець списку (begin, end);
встановлення нульових значень покажчикам;
встановлення довжини списку count у нульове значення.

Рисунок 3. Створення списку. Етап 1 – оголошення внутрішніх змінних. Етап 2 – заповнення змінних нульовими значеннями

⇑

3. Додавання елементу в кінець списку

При додаванні елементу в кінець списку виділяють такі дві ситуації:

додавання елементу до порожнього списку;
додавання елементу до непорожнього списку (списку, який містить елементи).

3.1. Додавання нового елементу в кінець порожнього списку

Процес додавання елементу в кінець порожнього списку складається з наступних кроків:

створити новий елемент elem та заповнити його даними (рисунок 4);
встановити початок та кінець списку (begin, end) так, щоб вони показували на новостворений елемент elem (рисунок 5);
збільшити загальну кількість елементів у списку (поле count).

Рисунок 4. Створення елементу та заповнення його даними. Заповнюються поля next, prev та data елементу elem

На рисунку 5 встановлюється значення покажчиків begin та end так, що вони вказують на створений елемент elem.

Рисунок 5. Додавання елементу до порожнього списку. Налаштування покажчиків початку та кінця списку

⇑

3.2. Додавання нового елементу до списку в якому вже є елементи

Додавання нового елементу до непорожнього списку складається з таких кроків:

створення нового елементу elem. Заповнення полів data та next елементу (рисунок 6);
налаштування покажчика prev елементу elem таким чином, що він вказує на поточну позицію покажчика кінця списку end (рисунок 7);
налаштування покажчика next останнього елементу end таким чином, щоб він вказував на елемент elem (рисунок 7);
зміщення покажчика кінця списку elem на одну позицію, яка визначена покажчиком elem.

Рисунок 6. Створення елементу. Налаштування покажчика next та поля даних data елементу elem

Рисунок 7. Додавання елементу в кінець непорожнього списку. Встановлення покажчика prev елементу elem та покажчика next останнього елементу списку end

Рисунок 8. Додавання елементу в кінець непорожнього списку. Встановлення покажчика кінця списку end на останню позицію

⇑

4. Вставка елементу в задану позицію списку

На відміну від операції додавання елементу до кінця списку, існує операція вставки елементу в список.

Якщо відбувається вставка елементу в порожній список, то ця операція є такою самою як додавання елементу до порожнього списку (дивіться пункт 3.1).

При вставці елементу в список, що вже містить елементи, важливим є позиція вставки. В залежності від позиції розглядаються наступні ситуації:

елемент вставляється в першу позицію списку;
елемент вставляється в другу, третю і т.д. позицію списку а також останню позицію списку;
елемент вставляється за останньою позицією списку. У цьому випадку дана вставка є такою самою як додавання елементу в кінець непорожнього списку як описується в пункті 3.2.

⇑

4.1. Вставка елементу в першу позицію списку, що містить елементи

Послідовність дій при вставці елементу в першу позицію списку наступна:

створити елемент та заповнити його даними (рисунок 9). Заповнюються поля data та prev;
встановити покажчик next елементу elem на перший елемент в списку begin (рисунок 10);
встановити покажчик prev першого елементу списку на елемент elem, що вставляється (рисунок 11);
перенаправити покажчик begin так, щоб він вказував на новостворюваний елемент elem (рисунок 12);
збільшити загальну кількість елементів у списку.

На рисунках 9, 10, 11, 12 зображено вищенаведені кроки у візуалізованій формі.

Рисунок 9. Вставка елементу на початок непорожнього списку. Створення нового елементу elem

Рисунок 10. Налаштування покажчика next елементу, який вставляється

Рисунок 11. Присвоєння покажчику prev першого елементу списку begin адреси елементу elem, який вставляється

Рисунок 12. Вставка елементу на початок списку. Перенаправлення покажчика begin на адресу елементу elem

⇑

4.2. Вставка елементу в середину списку, що містить елементи

Для вставки елементу в середину списку в деяку позицію index потрібно виконати таку послідовність кроків:

отримати елемент elemPrev який слідує перед позицією вставки. Іншими словами, отримати елемент в позиції index-1 (рисунок 13);
отримати елемент elemCur, який розміщується в позиції вставки index (рисунок 13);
створити новий елемент elemIns, який буде вставлятись між елементами elemPrev та elemCur. Заповнити поле data елементу (рисунок 14);
встановити покажчик next елементу elemIns рівним адресі елементу elemCur (рисунок 15);
встановити покажчик prev елементу elemIns рівним адресі елементу elemPrev (рисунок 15);
змістити покажчик next елементу elemPrev на елемент elemIns (рисунок 16);
змістити покажчик prev елементу elemCur на елемент elemIns (рисунок 16).

Вищенаведений покроковий процес відображено на рисунках 13, 14, 15, 16.

Рисунок 13. Вставка елементу в непорожній список. Отримати елементи в позиціях index-1 та index

Рисунок 14. Вставка елементу в непорожній список. Створення нового елементу. Заповнення поля data

Рисунок 15. Вставка елементу в непорожній список. Встановлення покажчиків pred та next елементу, що вставляється

Рисунок 16. Вставка елементу в непустий список. Перенаправлення покажчику next попереднього елементу elemPrev та покажчику prev наступного елементу elemCur на елемент elemIns, що вставляється

⇑

5. Видалення елементу зі списку

При видаленні елементу зі списку, що містить елементи, розглядаються три можливі ситуації:

видаляється перший елемент списку;
видаляється не перший і не останній елемент;
видаляється останній елемент списку.

⇑

5.1. Видалення першого елементу зі списку

При видаленні першого елементу зі списку послідовність кроків наступна:

запам’ятати адресу першого елементу в значення elem (рисунок 17);
змінити значення покажчика begin так, щоб він вказував на наступний елемент (рисунок 18). Якщо наступного елементу немає, то покажчик матиме значення nullptr;
встановити значення покажчика prev у нульове значення (рисунок 19);
звільнити пам’ять, виділену для елементу elem;
зменшити загальну кількість елементів на 1.

Якщо у списку тільки один елемент, то вищенаведені кроки також підійдуть для цього випадку. Нижче на рисунках 17, 18, 19, 20 зображено основні кроки цього процесу.

Рисунок 17. Видалення першого елементу зі списку. Крок 1. Запам’ятати значення початку списку begin

Рисунок 18. Видалення першого елементу зі списку. Крок 2. Зміщення покажчика begin на наступний елемент

Рисунок 19. Видалення першого елементу зі списку. Крок 3. Встановлення покажчика prev початку списку begin в нульове значення

Рисунок 20. Видалення першого елементу зі списку. Знищення елементу elem (звільнення пам’яті)

⇑

5.2. Видалення з середини списку

Якщо елемент видаляється з середини списку, то послідовність кроків наступна:

на основі індексу елементу index отримати покажчик на елемент elem, що видаляється, а також на попередній elemPrev та наступний elemNext елементи (рисунок 21);
встановити покажчик next елементу elemPrev рівним адресі елементу elemNext (рисунок 22);
встановити покажчик prev елементу elemNext рівним адресі елементу elemPrev (рисунок 22);
знищити (звільнити пам’ять) елемент elem (рисунок 23).

Рисунок 21. Видалення елементу зі списку. Крок 1. Отримати елемент, що видаляється а також попередній та наступний елементи

Рисунок 22. Видалення елементу зі списку. Крок 2. Встановлення покажчиків попереднього елементу elemPrev та наступного елементу elemNext в обхід елементу elem

Рисунок 23. Видалення елементу зі списку. Крок 3. Знищення елементу elem

⇑

5.3. Видалення останнього елементу зі списку

Для видалення останнього елементу зі списку виконується наступна послідовність дій:

запам’ятати адресу останнього елементу в списку у покажчику elem;
перемістити на попередній елемент покажчик end, який вказував на останній елемент у списку;
звільнити пам’ять, що була виділена під останній елемент у списку;
встановити покажчик next елементу end в нульове значення.

Операція видалення останнього елементу зі списку підходить для випадку, коли в списку є тільки один елемент.

Рисунок 24. Видалення останнього елементу зі списку. Запам’ятовування адреси останнього елементу

Рисунок 25. Видалення останнього елементу зі списку. Переміщення покажчика end на попередній елемент списку

Рисунок 26. Видалення останнього елементу зі списку. Звільнення пам’яті, що була виділена під останній елемент

Рисунок 27. Видалення останнього елементу зі списку. Встановлення в нульове значення покажчика next останнього елементу списку

BestProg

C++. Лінійний двохзв’язний (двонаправлений) список