Двонаправлений список з фіктивними елементами

двонаправлений

Малюнок 3.3 – Двозв'язковий список з фіктивним елементом

На малюнку 3.2 показаний списокL, який використовує фіктивний елементnil[L] (темно - сірий прямокутник). Замістьhead[L] використовуємоnext[nil[L]].(a) Порожній список. (б) Список, у якого елемент із ключем 9 – голова, 1 – хвіст). (в) Той самий список після процедури List-Insert'(L,x), якщоkey[x]=25. (г) Після видалення елемента із ключем 1. Новий хвіст має ключ 4.

Якщо забути про особливі ситуації на кінцях списку, процедуру List-Delete можна записати дуже просто:

двонаправлений

Лістинг 3.8 – Спрощена процедура видалення елемента зі списку

Такі спрощення стануть «законними», якщо додати до спискуLфіктивний елементnil[L],який матиме поляnextтаprevнарівні з іншими елементами списку. Цей елемент (званий англійськоюsentinel,що означає «вартовий») не дозволить вийти за межі списку. Покажчик нею відіграє роль значення NIL. Замкнемо список у кільце: у поляnext[nil[L]] таprev[nil[L]] запишемо вказівники на голову і хвіст списку відповідно, а в поляprevу голови списку таnextу хвоста списку занесемо вказівники наnil[L] (рис. 3.2). При цьомуnext[nil[L]]–покажчик на голову списку, так що атрибутhead[L] стає зайвим. Порожній списокLтепер буде кільцем, в якомуnil[L]–єдиний елемент.

У процедурі List-Search потрібно лише замінити NIL наnil[L] таhead[L] наnext[nil[L]]:

список

Лістинг 3.9 – Процедура пошуку у списку з фіктивнимелементом

Для видалення елемента застосовується процедура List-Delete, наведена вище. Нарешті, додавати елемент до списку можна так:

двонаправлений

Лістинг 3.10 – Процедура додавання до списку з фіктивним елементом

Приклад роботи процедур List-Insert та List-Delete показаний на рис.3.2. Використання фіктивних елементів може поліпшити асимптотику часу роботи алгоритму, але спрощує програму. Іноді (якщо використання фіктивних елементів дозволяє скоротити фрагмент коду, що знаходиться глибоко всередині циклу), можна прискорити виконання програми кілька разів;

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

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

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

Основна відмінність циклічного списку у тому, що у списку немає елементів, містять порожні покажчики, і, отже, не можна виділити крайні елементи. Отже, всі елементи є «середніми».

Циклічні списки також як і лінійні бувають односпрямованими та двоспрямованими.

Циклічний однонаправлений список

Циклічний односпрямований список схожий на лінійний односпрямований список, але його останній елемент містить покажчик,що зв'язує його з першим елементом.

Рисунок 3.4 – Циклічний однозв'язковий список

Основні операції, що здійснюються з циклічним односпрямованим списком:

Вставка елемента в список, як говорилося, простіше, ніж для лінійного односпрямованого списку і реалізується з допомогою однієї процедури: Ins_CicleSingleList. Як вхідні параметри передаються дане для заповнення створюваного елемента, покажчик початку списку і покажчик на поточний елемент у списку, після якого здійснюється вставка. Вихідними параметрами процедур є покажчик початку списку (який можливо зміниться) і покажчик поточного елемента, який вказує на новостворений елемент.

procedure Ins_CicleSingleList(DataElem: TypeData;