Двобічно зв'язаний список — вид зв'язаного списку, у якому посилання в кожному вузлі вказують на попередній і на подальший вузол у списку.
Якщо в списку після останнього елемента йде перший, то такий список називають кільцевим двобічно зв'язаним списком. Тобто, поле prev голови списку вказує на хвіст списку, а поле next хвоста списку вказує на голову списку.
По двобічно зв'язаному списку можна пересуватися в будь-якому напрямку — як від початку до кінця, так і навпаки. Для нього простіше проводити видалення і перестановку елементів, оскільки завжди відомі адреси тих елементів списку, вказівник яких спрямований на змінюваний елемент.
Переваги та недоліки Переваги двобічно зв'язаного списку над однобічно зв'язаним списком: Додавання нового вузла в певну позицію. Видалення i-го елемента з послідовності. Перегляд списку в обох напрямках.
Існують і недоліки: з'являється додаткова змінна — вказівник на попередній елемент (prev).
Нижче описаний принцип роботи двобічно зв'язного циклічного списку. Єдина відмінність двобічно зв'язного циклічного списку від двобічно зв'язного списку в тому, що останній елемент указує на перший, а перший — на останній. Дана відмінність дає змогу виключати перевірки на «перший» і «останній» елемент.
Аби уникнути проблем з порожніми вказівниками та створення циклу можна використовувати спеціальний порожній вузол - перший вузол списку посилатиметься на нього як на попередника (prev), а останній - як на наступника (next).
Операції з двобічним списком
Стандартні функції для двобічно зв'язного списку Функція push (додати новий елемент в i-ту позицію списку). Вона виконує наступні дії: Створює новий елемент. Копіює значення інформаційного поля. Якщо даний елемент є єдиним: Обидва покажчики (next і prev) посилаються на цей елемент (рис. 2). Покажчик first вказує на єдиний елемент у списку. Інакше зсувається покажчик на i-й елемент і додається новий елемент перед i-м.
Додати нове значення у двобічно зв'язний список (push 4), новий елемент додаватиметься після першого. Після операції push список міститиме один елемент (рис. 2).
Додавши ще кілька значень (push 6 і push 7), кожен новий елемент буде додаватися після першого. Список міститиме три елементи (рис. 3) у такій послідовності:
Функція pop виштовхує i-й елемент зі списку. Вона виконує наступні дії: Якщо список порожній, вихід із функції. Якщо в список містить єдиний елемент: Копіюється значення інформаційного поля. Видаляється елемент зі списку. Присвоюється заголовку пусто. Інакше — зсувається покажчик на i-й елемент; якщо заголовок вказує на i-й елемент (first == t), тоді переміщається заголовок на наступний елемент (First = t-> next) копіюється значення інформаційного поля; видаляється i-й елемент зі списку. Повертається значення інформаційного поля.
Виконавши функцію pop над лінійним списком (виштовхується 3-й елемент). Отримується наступний стан зв'язного списку (рис. 4).
Функція print_all пробігає по всіх елементах і виводить в консоль значення інформаційного поля. Перегляд елементів здійснюється зліва направо, але легко можна переписати функцію і змінити перегляд елементів справа наліво (замінити a = a-> next на a = a-> prev). Функція clean видаляє всі елементи в списку і привласнює заголовку пусто (first = null). Після цієї операції список повертається в початковий стан.
Див. також Зв'язаний список XOR-зв'язний список
Джерела