Списком називається упорядкована множина, що складається з перемінного числа елементів, до яких застосовні операції включення, виключення. Список, що відбиває відносини сусідства між елементами, називається лінійним. Елементи списку називають вузлами (nodes). Логічні списки вже були розглянуті, але там мова йшла про напівстатичні структури даних і на розмір списку накладалися обмеження. Якщо обмеження на довжину списку не допускаються, то список представляється в пам'яті у вигляді зв'язної структури. Лінійні зв'язні списки є найпростішими динамічними структурами даних.
МАШИННЕ ПРЕДСТАВЛЕННЯ ЗВ'ЯЗНИХ ЛІНІЙНИХ СПИСКІВ.
У пам'яті зв’язний список (linked list) являє собою сукупність дескриптора й однакових по розміру і формату записів, розміщених довільно в деякій області пам'яті і зв'язаних один з одним у лінійно упорядкований ланцюжок за допомогою покажчиків. Запис містить інформаційні поля і поля покажчиків на сусідні елементи списку, причому деякими полями інформаційної частини можуть бути покажчики на блоки пам'яті з додатковою інформацією, що відноситься до елемента списку. Дескриптор списку реалізується у вигляді особливого запису і містить таку інформацію про список, як адреса початку списку, код структури, ім'я списку, наявне число елементів у списку, опис елемента і т.д. Дескриптор може знаходитися в тій же області пам'яті, де й елементи списку, або для нього виділяється яке-небудь інше місце.
Розрізняють лінійні і кільцевіоднозв'язні та двозв'язні списки.
Однозв'язний список у кожнім вузлі має інформаційне поле і поле адреси наступного елемента. Список повинний мати покажчик на початок списку або голову списку (head), що по формату відмінний від інших елементів. У полі покажчика останнього елемента списку або хвоста (rear) знаходиться спеціальна ознака nil (у Pascal), NULL (у С++), що свідчить про кінець списку. У випадку пустого списку його head = nil . Для опису елемента списку використовуються дані типу запис. (У всіх наступних прикладах інформаційне поле представлено полем data цілого типу).
Наприклад, у мові Pascal у С++
| type ptr_el_sp=^el_sp; el_sp=record info:integer; next:ptr_el_sp; end; | struct el_spis{ int info; el_spis *next; }; |
Двозв'язний лінійний список – це список, у якому кожен елемент містить два покажчики: на наступний і попередній елементи списку. Такі списки називають ще двоспрямованими. Для зручності обробки списку додають ще один елемент – покажчик кінця списку. Наявність двох покажчиків у кожнім елементі ускладнює список і приводить до додаткових витрат пам'яті, але в той же час забезпечує більш ефективне виконання деяких операцій над списком.
При виконанні операцій над списками можливий випадок, коли адреса першого елемента списка змінюється. А загубити вказівник на перший елемент – це загубити увесь список. Саме тому при розробці алгоритмів роботи зі списками необхідно передбачити обробку першого елемента поза циклом, що веде до ускладнення коду програми. Як вихід, замість вказівника на перший елемент списку використовують заголовок. Заголовок або заголовочний вузол – це такий елемент списку поле даних якого не є частиною списку (не містить даних), а у полі адреси зберігається адреса першого вузла даного списку. В такому списку усі вузли, що містять дані обробляються по єдиному алгоритму.
Різновидом лінійного списку є кільцевий список. При цьому в однозв'язному списку покажчик останнього елемента повинний указувати на перший елемент. У двозв'язному списку в першому й останньому елементах перевизначаються відповідні покажчики так, що покажчик у останньому елементі вказує на перший елемент, а в першому – на останній. При роботі з такими списками трохи спрощуються деякі процедури, виконувані над списком. Однак, при перегляді такого списку варто прийняти деяких запобіжних заходів, щоб не потрапити в нескінченний цикл.
ОПЕРАЦІЇ НАД ЗВ'ЯЗНИМИ ЛІНІЙНИМИ СПИСКАМИ. До головних операцій відносяться такі: перебір елементів, вставка елемента в список, перестановка двох елементів, видалення елементу, копіювання декількох елементів.
Перебір елементів списку – це послідовний доступ до усіх елементів списку від початку до кінця списку або до знаходження шуканого елемента. У кільцевому списку закінчення перебору повинне відбуватися не по ознаці останнього елемента оскільки така ознака відсутня, а по досягненню елемента, з якого почався перебір.
Вставка елемента в список передбачає додавання елемента в будь-яке місце списку: на початку, коли змінюється адреса початкового елемента списку, в кінець (для двоспрямованих списків змінюється адреса останнього елемента) або в середину. Для кільцевих списків різниці для цієї операції не існує.
Видалення елементаз будь-якого місця списку. Змінюється адреса початку списку при видалені першого елемента, кінця – при видаленні останнього і лише зв’язки між елементами – при видаленні елементу всередині.
Перестановка елементів списку. При цьому змінюється адреса початку списку при перестановці першого елемента, кінця – при перестановці останнього і лише зв’язки між елементами – при перестановці елементів в середині списку.
Копіювання частини списку. Операція копіювання припускає дублювання даних у пам'яті. При копіюванні вихідний список зберігається в пам'яті, і створюється новий список, але поля зв'язків у новому списку інші, оскільки елементи нового списку розташовані по інших адресах у пам'яті.
Злиття двох списків. Операція злиття полягає у формуванні з двох списків одного (аналогічна операції зчеплення рядків).
Вказані операції не змінюють адреси списку як що цей список має головний елемент. В усіх операціях надзвичайно важлива послідовність корекції покажчиків, що забезпечує коректну зміну списку. При неправильному порядку корекції легко втратити частину або, навіть, увесь список.