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

Найбільш природним і простим типом списку є однонаправлений, призначений для того, щоб проглядати його в одному напрямі - від початку до кінця. Однонаправлений список найчастіше зображують у вигляді ланцюга, тому його називають також ланцюговим, або лінійним однозв‘язним (рис.8.2).

Рис.8.2. Приклад однонаправленого списку

Довідка кожної ділянки такого списку складається з двох значень. Першим є довжина N_i i -ї ділянки, яка, в свою чергу, складається з довжини запису і довжини довідки. Другим значенням довідки є посилання на початок наступної ділянки. Далі розміщується тіло ділянки або безпосередньо запис. Заголовна ділянка складається з трьох полів: довжини заголовної ділянки; посилання на початок першої ділянки; посилання на початок вільного місця. Перші два значення утворюють довідку заголовної ділянки, а посилання на вільне місце являє собою тіло цієї ділянки. У довідці останньої ділянки поле вказівника порожнє. У загальному випадку всі записи в однонаправленому списку можуть мати різну довжину.

Однонаправлений список можна відобразити в одномірний масив наступним способом. Заголовний запис буде займати елементи масиву S[o], S[1], S[2]. Далі розміщуються інші записи. Якщо індекс ділянки, що містить запис X, має значення і, то в елементі S[i] знаходяться довжина цієї ділянки, в елементі S[і+1] - індекс ділянки з наступним записом списку (або нуль, якщо запис X останній). Починаючи з елемента S[i+2] знаходиться сам запис (тіло ділянки).

Схема процедури включення нового запису Z після ділянки з індексом і показана нарис. 8.3. При цьому спочатку формується нова ділянка з записом Z, яка розміщується на вільному місці пам‘яті, а потім коректується зв‘язок і -ї ділянки.

Рис.8.3. Схема процедури включення елемента в ланцюговий список

Процедура виключення елемента з такого списку також зводиться до корекції зв‘язків між ділянками (рис.8.4). Припустимо, що потрібно виключити зі списку ділянку, яка розміщується після ділянки з індексом і. Отже, індекс ділянки, що виключається, розміщений в S[і+1]. Значення S[і+1] заміняється на значення, яке зберігалось у довідці ділянки, що виключається.

Рис. 8.4. Схема процедури виключення елемента

з однонаправленого списку

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

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