Основні теоретичні відомості. Динамічний список, у якому кожний елемент (окрім першого і останнього) пов’язаний з попереднім і наступним за ним елементами

Динамічний список, у якому кожний елемент (окрім першого і останнього) пов’язаний з попереднім і наступним за ним елементами, називається двозв’язним. Кожний елемент такого списку має два поля з покажчиками: одне поле містить посилання на наступний елемент, інше поле – посилання на попередній елемент і третє поле – інформаційне. Наявність посилання на наступну ланку і на попереднє дозволяє рухатися по списку від кожної ланки у будь-якому напрямку: від ланки до кінця списку або від ланки до початку списку, тому такий список ще називають двоспрямованим. Наприклад, рядок символів 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(); }