Циклічні списки

Циклічні, або кільцеві, списки - найпоширеніша різновидність двонаправлених списків. У такому списку остання ділянка посилається на заголовну як на наступну, а ця, в свою чергу, посилається на останню ділянку як на попередню. Така організація спрощує процедуру пошуку або перебору записів з довільного місця з автоматичним переходом від кінця на початок, і навпаки. Бувають також однозв‘язні кільцеві списки, в яких остання ділянка посилається на заголовну як на наступну. На рис.8.6 зображено циклічний двозв‘язаний список.

Рис.8.6. Циклічний список

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

Операція виключення ділянки із кільцевого двозв‘язного списку також зводиться до коректування двох посилань - у "сусіда ліворуч" змінюється вказівник на наступну ділянку, а у "сусіда праворуч" - вказівник на попередню ділянку.

Циклічний двозв‘язний список можна відобразити у одномірний масив аналогічно лінійному списку. У такому випадку процедури включення-виключення елементів зводяться до обчислення індексів вказівників, як і в лінійному списку, і заміни вмістимого елементів масиву з цими індексами. Якщо тіло елемента списку являв собою рядок символів або бітів, а вказівники - цілі числа, то не в кожній мові програмування таке відображення можливе. Тому, наприклад, простіше відображувати списки у два масиви - один для тіла елемента, другий - для довідкової частини.

Частіше, однак, елементи списку не розташовують у якому-небудь масиві, а просто розміщають кожний окремо в оперативній пам'яті, виділеній даній задачі. Зазвичай елементи списку розміщаються в динамічній пам'яті. У якості вказівників у цьому випадку використовують адреси елементів в оперативній пам'яті.

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

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