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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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] Двобічно зв'язний список(рос.)