Основні теоретичні відомості. Динамічний список, у якому кожний елемент (окрім першого і останнього) пов’язаний з попереднім і наступним за ним елементами
Динамічний список, у якому кожний елемент (окрім першого і останнього) пов’язаний з попереднім і наступним за ним елементами, називається двозв’язним. Кожний елемент такого списку має два поля з покажчиками: одне поле містить посилання на наступний елемент, інше поле – посилання на попередній елемент і третє поле – інформаційне. Наявність посилання на наступну ланку і на попереднє дозволяє рухатися по списку від кожної ланки у будь-якому напрямку: від ланки до кінця списку або від ланки до початку списку, тому такий список ще називають двоспрямованим. Наприклад, рядок символів BETA представлений двоспрямованим списком:
Рисунок 2.1 – Рядок символів BETA представлений двоспрямованим списком
Перша ланка не має посилання на попередню, остання ланка не має посилання на наступну ланку (рис.2.1).
Рисунок 2.2 – Рядок символів BETA представлений кільцевим (циклічним) списком
Такий список (рис.2.2.) називають кільцевим (циклічним). Тут перша ланка має посилання на останню, а остання ланка – на першу. Тому починати обробку такого списку можна як з першої ланки, так і з останньої.
Основні операції, що виконуються над двозв’язним списком, такі ж, як і для однозв’язного списку. Так як двозв’язний список більш гнучкий, аніж однозв’язний, то при занесенні елемента до списку, можна використовувати покажчик як на елемент, за яким відбувається занесення, так і покажчик на елемент, перед яким відбувається занесення. При видаленні елемента зі списку можна використовувати як покажчик власне на елемент, що буде видалений, так і покажчик на елемент, що передує або йде наступним за елементом, який буде видалений. Але так як елемент двозв’язного списку має два покажчики, то при виконанні операцій вставки/видалення елемента потрібно змінювати більше зв’язків, ніж у однозв’язному списку. Пошук елемента у двозв’язному списку можна проводити таким чином:
– переглядаючи елементи від початку до кінця списку;
– переглядаючи елементи від кінця списку до початку;
– переглядаючи список у обох напрямках одночасно: від початку до середини списку і від кінця до середини (враховуючи те, що елементів у списку може бути парна або непарна кількість).
Приклад. Список складається із вузлів (елементів), що пов’язанні між собою покажчиками. Тому опишемо допоміжний клас для подання одного вузла списку:
class Node
{public:
char d; // дані
Node *next; // покажчик на наступний вузол
Node *prev; // покажчик на попередній вузол
Node (char dat = 0) { d = dat; next = 0; prev = 0;}// конструктор
};
class List2
{ Node *pbeg, *pend; // покажчики на початок та кінець списку
public:
List2() { pbeg = 0; pend = 0;} // конструктор
~List2(); // деструктор
void add(char d); // додавання вузла в кінець списку
void print(); // друк списку в прямому напрямку
};
Розглянемо реалізацію методів класу. Метод add виділяє пам'ять під новий об’єкт типу Node та приєднує його к списку, оновлюючи покажчики на його початок та кінець:
void List2::add(char d)
{ Node *pv = new Node(d); // виділення пам'яті під новий вузол
if(!pbeg) { pbeg = pend = pv; } // перший вузол
else { // зв’язування нового вузла з попереднім:
pv->prev = pend; pend->next = pv;
pend = pv; // оновлення покажчика на кінець списку
}
}
Метод друку списку в прямому напрямку поелементно переглядає список, переходячи по відповідним посиланням:
void List2::print()
{ Node *pv = pbeg;
cout << endl << " list: ";
while(pv) {cout << pv->d << " "; pv = pv->next; }
cout << endl; }
Деструктор списку звільняє пам'ять з-під усіх елементів списку:
List2::~List2()
{ If (pbeg) { Node *pv = pbeg;
while(pv) { pv = pv->next; delete pbeg; pbeg = pv; }}
}
Нижче наведений приклад програми, що використовує клас List2. Програма формує список рядку 'BETA' та друкує його на екран.
void main()
{ List2 l;
l.add('B');
l.add('E');
l.add('T');
l.add('A');
l.print();
getch(); }