1.1. Визначення двонаправленого списку
Динамічний список, в якому кожен елемент (крім можливо першого і останнього) пов'язаний з попереднім і наступним за ним елементами називається двусвязного. Кожен елемент такого списку має два поля з покажчиками: одне поле містить посилання на наступний елемент, інше поле - посилання на попередній елемент і третє поле - інформаційне. Наявність посилань на наступну ланку і на попереднє дозволяє рухатися по списку від кожної ланки в будь-якому напрямку: від ланки до кінця списку або від ланки до початку списку, тому такий список називають ще і двонаправленим.
Рис.1. рядок символів BETA представлена двусвязного списком
Перша ланка не має посилання на попереднє, остання ланка не має посилання на наступну ланку (див. Рис.2.).
Рис.2. рядок символів BETA представлена циклічним списком
Такий список (див. Рис.2.) Називають кільцевим (циклічним). Тут перша ланка має посилання на останнє, а остання ланка на перше. Тому починати обробку такого списку можна як з першої ланки, так і з останнього. Двусвязний список може мати головній ланка (див. Рис.3.).
Рис.3. Головній ланка двусвязного списку
Головній ланка дозволяє обробляти перше і останнє ланки також як інші.
Можливі й інші структури двусвязного списків.
Завдання двусвязного списку:
list2 * next, * pred;>
Тут type - тип інформаційного поля елемента списку. Змінна-вказівник headlist2 задає список як єдиний програмний об'єкт, її значення - покажчик на перший (або титульний) елемент списку (див. Рис.3.).
Приклад 2. Формування двонаправленого кільцевого списку
list2 * next, * pred;>
l -> next = l; // кільцевого списку
l -> pred = l; // з заголовних ланкою
while ((sym = getchar ())! = '\ n')
x -> elem = sym; // Створення чергового ланки
x -> next = r -> next; // Поле next - покажчик на наступну ланку
// отримало значення покажчика на першу ланку списку
x -> pred = r; // Поле pred - покажчик на попереднє ланка отримало
// значення покажчика на поточний остання ланка списку
r -> next = x; // Поле next поточного останнього елемента - покажчик на
// наступний елемент отримало значення покажчика на новий
// елемент, таким чином, нова ланка додано в кінець
r -> next -> pred = x; // Поле pred заголовного елемента - покажчик
// на останню ланку списку отримало значення покажчика
// на доданий в кінець списку елемент, таким чином,
// сформований кільцевої список
// Поточний покажчик набув значення посилання на
// новий останній елемент списку
Основні операції, що виконуються над двусвязного списком, ті ж, що і для однозв'язного списку. Так як двусвязний список більш гнучкий, ніж однозв'язний, то при включенні елемента в список, можна використовувати покажчик як на елемент, за яким відбувається включення, так і покажчик на елемент перед яким відбувається включення. При виключення елемента зі списку можна використовувати як покажчик на сам виключається елемент, так і покажчик на елемент передує або наступний за виключається. Але так як елемент двусвязного списку має два покажчика, то при виконанні операцій включення / виключення елемента треба змінювати більше зв'язків, ніж в однозв'язного списку.
Пошук елемента в двусвязного списку можна вести:
а) переглядаючи елементи від початку до кінця списку,
б) переглядаючи елементи від кінця списку до початку,
в) переглядаючи список в обох напрямках одночасно: від початку до середини списку і від кінця до середини (враховуючи, що елементів в списку може бути парне або непарна кількість).
Приклад 3. Фрагменти програм, що виконують різні дії з двусвязного списком:
// списку без заголовного ланки
if (p = = NULL) return;
// p НЕ дорівнює вказівником на початок списку - ph
// списку з заголовних ланкою
if (p -> next = = p) return;
pr = p -> pred; // Поточний покажчик pr отримав значення посилання
// на останній елемент списку
// НЕ дорівнює вказівником на головній ланка списку - p
x = new list2; // Включення нового елемента (в список з
x -> pred = p -> pred; // заголовних ланкою) перед елементом, на
x -> next = p; // який посилається p
p -> pred -> next = x;
p -> pred -> next = p -> next; // Виняток зі списку з заголовним
p -> next -> pred = p -> pred; // ланкою елемента, на який
delete p; // посилається покажчик p