Застосування лінійних списків

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

На базі лінійних списків можуть будуватися стеки, черги, деки. Представлення черги за допомогою лінійного списку дозволяє досить просто забезпечити будь-які бажані дисципліни обслуговування черги. Особливо це зручно, коли число елементів у черзі важко передбачити. Типовий приклад застосування списків – таблиця імен в трансляторах для мов програмування. Кожний опис призводить до додавання нового імені, а при виході з області дії його опису це ім’я зі списку видаляється.

Лінійні зв'язні списки іноді використовуються також для представлення таблиць – у тих випадках, коли розмір таблиці може істотно змінюватися в процесі її існування. Однак, та обставина, що доступ до елементів зв'язного лінійного списку може бути тільки послідовним, не дозволяє застосувати до такої структури деякі ефективні алгоритми, наприклад, двійковий пошук, що істотно обмежує їхню застосовність. Оскільки упорядкованість такої таблиці не може допомогти в організації пошуку, задачі сортування таблиць, представлених лінійними зв'язними списками, виникають значно рідше, ніж для таблиць у векторному представленні. Однак, у деяких випадках для таблиці, хоча і не потрібно часте виконання пошуку, але задача генерації звітів вимагає розташування записів таблиці в деякому порядку. Для упорядкування записів такої таблиці застосовні будь-які алгоритми з раніше розглянутих. Але деякі алгоритми, можливо, зажадають яких-небудь ускладнень структури. Наприклад, швидке сортування Хоара доцільно проводити тільки на двозв’язному списку, у цифровому сортуванні зручно створювати проміжні списки для цифрових груп і т.д.

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

– учасників бойових дій;

– людей з вищою освітою;

– матерів, що мають більше трьох дітей і т.і.

Для того, щоб при вибірці кожної підмножини не виконувати повний перегляд з відсіванням записів, що не стосуються необхідної підмножини, у кожен запис включаються додаткові поля посилань, кожне з яких зв'язує в лінійний список елементи відповідної підмножини. У результаті виходить багатозв’язний список або мультисписок, кожен елемент якого може входити одночасно в кілька однозв'язних списків (див. рис 7.1). Такий список буде мати декілька дескрипторів (для кожного підсписку – окремий дескриптор), наприклад, дескриптор підсписка учасників бойових дій, тих, хто має вищу освіту, багатодітних сімей.

Рис. 7.1. Структура мультисписку

Мультисписки мають такі переваги:

– забезпечують економію пам'яті оскільки при багатьох списках інформаційна частина в пам’яті існує в єдиному екземплярі (штащ);

– цілісність даних – у тім розумінні, що всі підзадачи працюють з однієї і тією ж версією інформаційної частини і зміни в даних, зроблені однієї підзадачею негайно стають доступними для іншої пїдзадачи. Кожна пїдзадача працює зі своєю підмножиною як з лінійним списком, використовуючи для цього призначене поле зв'язків, наприклад, head1, head2, head3.

Специфіка мультисписка виявляється тільки в операції видалення елемента зі списку. Видалення елемента з якого-небудь одного списку ще не означає необхідності видалення елемента з пам'яті, тому що елемент може залишатися в складі інших списків. Пам'ять повинна звільнятися тільки в тому випадку, коли елемент уже не входить ні в один із приватних списків мультисписка. Звичайно задача видалення спрощується тим, що один із часткових списків є головним. А в головний список обов'язково входять усі наявні елементи. Тоді виключення елемента з будь-якого неголовного списку складається тільки в перевизначені покажчиків, але не в звільненні пам'яті. Видалення елементу ж з головного списку вимагає не тільки звільнення пам'яті, але і перевизначення покажчиків як у головному списку, так і у всіх неголовних списках, у які елемент, що видаляється, входив.