Однонаправлені списки

На цьому кроці ми розглянемоодноспрямовані списки.

Підспискомми розумітимемо кінцевий упорядкований набір об'єктів довільних розміру та природи.

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

Пов'язані списки можуть матипоодинокіабоподвійнізв'язки.

Список зодним зв'язком(односпрямований список) містить елементи, кожен з яких має зв'язок з наступним елементом даних. У списку зподвійним зв'язком(двонаправлений список) кожен елемент має зв'язок, як з наступним елементом, так і з попереднім елементом. Тип зв'язаного списку вибирається залежно від завдання, що розв'язується.

Однонаправлені списки

Лінійний (односпрямований) список є динамічною структурою даних, дані в яку можуть включатися і вилучатися довільно обране місце.

Побудуємо модель списку за допомогою певної структури даних, що складається з динамічних змінних. Кожен елемент списку представимо записом мови Pascal, що складається із двох полів:

інформаційного поляабополя даних, яке в загальному випадку може містити довільне(Фіксована для даного типу елемента) кількість полів різних типів;
посилання на наступний елементсписку.

Кожну таку пару називатимемоланкою, а посилання, що містяться в кожній з ланок, будемо використовувати для з'єднання ланок у ланцюжок. Такий спосіб представлення впорядкованої послідовності елементів називаєтьсязчепленням.

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

Розглянемо схематичне зображення односпрямованого списку:

Мал.1. Схематичне зображення односпрямованого списку без великої ланки

Над списками виконуються такі операції

початкове формування списку (запис першої компоненти);
додавання компоненти до кінця списку;
визначення першого елемента у лінійному списку;
читання компоненти із заданим ключем; із заданою властивістю;
вставка компоненти у задане місце списку (зазвичай до компоненти із заданим ключем або після неї);
виключення компоненти із заданим ключем зі списку.
упорядкування вузлів лінійного списку у визначеному порядку.

Опис компоненти однонаправленого списку дамо так:

Для формування односпрямованого списку та роботи з ним необхідно описати чотири змінні типи покажчик на запис. Домовимося, щоpBeginвизначає початок списку, аpCKey, pPredRec, pAuxвизначимо як допоміжні (покажчик на компоненту із заданим ключем, покажчик на компоненту перед заданим ключем, часовийпокажчик):

На наступному кроці ми розглянемоформування списку із збереженням порядку вступних елементів.