Зв’язний список - студопедія

Структура даних, що представляє собою кінцеве безліч впорядкованих елементів (вузлів), пов'язаних один з одним за допомогою покажчиків, називається зв'язковим списком. Кожен елемент зв'язного списку містить поле з даними, а також покажчик (посилання) на наступний і / або попередній елемент. Ця структура дозволяє ефективно виконувати операції додавання і видалення елементів для будь-якої позиції в послідовності. Причому це не зажадає реорганізації структури, яка б була потрібна в масиві. Мінусом зв'язного списку, як і інших структур типу «список», в порівнянні його з масивом є відсутність можливості працювати з даними в режимі довільного доступу, т. Е. Список - структура послідовно доступу, в той час як масив - довільного. Останній недолік знижує ефективність ряду операцій.

Кожен вузол однозв'язного (односпрямованого зв'язкового) списку містить покажчик на наступний вузол (рис. 2.7). З однієї точки можна потрапити лише в наступну точку, рухаючись тим самим в кінець. Так виходить своєрідний потік, поточний в одному напрямку.

Малюнок 2.7 - однозв'язного список

Повторимо вже раніше сказане. На зображенні кожен з блоків представляє елемент (вузол) списку. Head list - заголовний елемент списку (для нього передбачається поле next). Він не містить дані, а тільки посилання на наступний елемент. На наявність даних вказує поле info. а посилання - поле next (далі за посилання буде відповідати і поле prev). Ознакою відсутності покажчика є поле nil.

Однозв'язний список не найзручніший тип зв'язного списку, т. К. З однієї точки можна потрапити лише в наступну точку, рухаючись тим самим в кінець. Коли крім покажчика на наступний елемент є вказівник на попередній, то такий список називається двусвязного.

Малюнок 2.8 - двусвязного список

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

Коли кількість пам'яті, з яких-небудь причин, обмежена, тоді альтернативою двусвязного списку може послужити XOR-зв'язний список (рис. 2.9). Останній використовує логічну операцію XOR (виключає «АБО», сувора диз'юнкція), яка для двох змінних повертає істину лише за умови, що істинно тільки одне з них, а друге, відповідно, помилково. Таблиця істинності операції:

Малюнок 2.9 - XOR-зв'язний список

Ще один вид зв'язного списку - кільцевої список. У кільцевому однозв'язного списку останній елемент посилається на перший. У разі двусвязного кільцевого списку, плюс до цього, перший елемент посилається на останній (рис. 2.10). Таким чином, виходить зациклена структура.

Малюнок 2.10 - Кільцевій зв'язний список

Розглянемо основні операції над зв'язковими списками.

На прикладі двусвязного списку, розберемо принцип роботи цієї структури даних. При реалізації списку зручно використовувати структури (в Pascal - записи).

Загальна форма опису вузла двонаправленого зв'язного списку і покажчика на перший елемент списку:

інформаційне поле 1;

інформаційне поле 2;

інформаційне поле n;

покажчик на наступний елемент;

покажчик на попередній елемент;

struct DoubleList // опис вузла списку

int data; // інформаційне поле

DoubleList * next; // покажчик на наступний елемент

DoubleList * prev; // покажчик на попередній елемент

DoubleList * head; // покажчик на перший елемент списку

Тепер, припускаючи, що описаний вузол і покажчик на голову списку (див. Приклад вище), напишемо функції обробки списку.

void AddList (int value, int position)

DoubleList * node = new DoubleList; // створення нового елемента

node-> data = value; // присвоєння елементу значення

if (head == NULL) // якщо контактів немає

node-> next = node; // установка покажчика next

node-> prev = node; // установка покажчика prev

head = node; // визначається голова списку

for (int i = position; i> 1; i--) p = p-> next;

node-> next = p; // додавання елемента

cout<<"\nЭлемент добавлен. \n\n";

int DeleteList (int position)

if (head == head-> next) // якщо це останній елемент в списку

delete head; // видалення елемента

for (int i = position; i> 1; i--) a = a-> next;

if (a == head) head = a-> next;

a-> prev-> next = a-> next; // видалення елемента

cout<<"\nЭлемент удален. \n\n";

Якщо список порожній, то виводиться повідомлення, що сповіщає про це, і функція повертається в місце виклику.

Функція PrintList виводить на екран всі елементи списку:

if (head == NULL) cout<<"Список пуст\n";

cout<<"\nЭлементы списка: ";

Вивести список можна і за допомогою циклу, тобто итеративно. Тепер з'єднаємо ці три функції в одній програмі, а також напишемо головну функцію, що відповідає за виклик підпрограм: