Двобічно зв'язаний список

Двобічно зв'язаний список — вид зв'язаного списку, у якому посилання в кожному вузлі вказують на попередній і на подальший вузол у списку.

Doubly-linked-list.svg
Вузол двобічно зв'язаного списку складається з трьох полів: вказівника на попередній елемент prev, поля даних data та вказівника next на наступний елемент.
Файл:Рис.1 Двозв'язковий список у графічному виляді2.png
Рис.1. Кільцевий двобічно зв'язаний список

Якщо в списку після останнього елемента йде перший, то такий список називається кільцевим двобічно зв'язаним списком. Тобто, поле prev голови списку вказує на хвіст списку, а поле next хвоста списку вказує на голову списку.

По двобічно зв'язаному списку можна пересуватися в будь-якому напрямку — як від початку до кінця, так і навпаки. Для нього простіше проводити видалення і перестановку елементів, оскільки завжди відомі адреси тих елементів списку, вказівник яких спрямований на змінюваний елемент.

Переваги двобічно зв'язаного списку над однобічно зв'язаним спискомРедагувати

  1. Додавання нового вузла в певну позицію.
  2. Видалення i-го елемента з послідовності.
  3. Перегляд списку в обох напрямках.

Існують і недоліки: з'являється додаткова змінна — вказівник на попередній елемент (prev). У даній статті описаний принцип роботи двобічно зв'язного циклічного списку. Єдина відмінність двобічно зв'язного циклічного списку від двобічно зв'язного списку в тому, що останній елемент указує на перший, а перший — на останній. Дана відмінність дає змогу виключати перевірки на «перший» і «останній» елемент. Двобічно зв'язаний циклічний список (далі просто Двобічно зв'язаний список) візуально можна представити в наступному вигляді (рис.1):

Стандартні функції для двобічно зв'язного спискуРедагувати

Функція push (додати новий елемент в i-ту позицію списку). Вона виконує наступні дії:

  1. Створює новий елемент.
  2. Копіює значення інформаційного поля.
  3. Якщо даний елемент є єдиним:
    1. Обидва покажчики (next і prev) посилаються на цей елемент (рис. 2).
    2. Покажчик first вказує на єдиний елемент у списку.
  4. Інакше зсувається покажчик на i-й елемент і додається новий елемент перед i-м.

Додати нове значення у двобічно зв'язний список (push 4), новий елемент додаватиметься після першого. Після операції push список міститиме один елемент (рис. 2).

Файл:Рис.2 Додавання нового значення1.png
рис.2 Додавання нового значення

Додавши ще кілька значень (push 6 і push 7), кожен новий елемент буде додаватися після першого. Список міститиме три елементи (рис. 3) у такій послідовності:

Файл:Рис 3. Додавання нових значень1.png
Рис 3. Додавання нових значень

Функція pop виштовхує i-й елемент зі списку. Вона виконує наступні дії:

  1. Якщо список порожній, вихід із функції.
  2. Якщо в список містить єдиний елемент:
    1. Копіюється значення інформаційного поля.
    2. Видаляється елемент зі списку.
    3. Присвоюється заголовку пусто.
  3. Інакше — зсувається покажчик на i-й елемент;
    1. якщо заголовок вказує на i-й елемент (first == t), тоді переміщається заголовок на наступний елемент (First = t-> next)
    2. копіюється значення інформаційного поля;
    3. видаляється i-й елемент зі списку.
  4. Повертається значення інформаційного поля.

Виконавши функцію pop над лінійним списком (виштовхується 3-й елемент). Отримується наступний стан зв'язного списку (рис. 4).

Файл:Рис 4. Виштовхування елементу.1.png
рис 4. Виштовхування елементу.

Функція print_all пробігає по всіх елементах і виводить в консоль значення інформаційного поля. Перегляд елементів здійснюється зліва направо, але легко можна переписати функцію і змінити перегляд елементів справа наліво (замінити a = a-> next на a = a-> prev). Функція clean видаляє всі елементи в списку і привласнює заголовку пусто (first = null). Після цієї операції список повертається в початковий стан.

Приклад реалізації двобічно зв'язаного списку на С++Редагувати

ПосиланняРедагувати

  • [1] Двобічно зв'язні списки(рос.)
  • [2] Двобічно зв'язний список(рос.)