Skip to main content

Що таке циклічний список (circular linked list)?

Структури данихJunior~1 хв читання
Запропонувати правку

Циклічний список (circular linked list) - це різновид зв'язаного списку, у якому останній вузол не вказує на None, а посилається назад на перший вузол (head), утворюючи замкнуте коло.

Тобто під час обходу списку можна рухатися нескінченно по колу - після останнього елемента знову йде перший.

1. Візуально

Однозв'язний циклічний список:

javascript
head → [10 | *] → [20 | *] → [30 | *] ──┐ ↑──────────────────────────────┘
  • У останнього вузла next вказує на head.
  • Немає "кінця списку" - обхід можна почати з будь-якого вузла і завжди повернутися назад.

2. Двозв'язний циклічний список

У ньому кожен вузол має і prev, і next, і обидва вказівники замикаються по колу:

javascript
↰ [10] ↔ [20] ↔ [30] ↺
  • head.prev = tail
  • tail.next = head

3. Як зберігається

Кожен вузол має посилання, як у звичайному списку, але:

  • при створенні останнього елемента його next вказує на head,
  • (у двозв'язному варіанті ще й head.prev вказує на tail).

4. Основні операції

ОпераціяСкладністьОпис
ОбхідO(n)Можна обійти, починаючи з будь-якого вузла, але потрібно стежити, щоб не зациклитися.
Вставка/видалення за відомого вузлаO(1)Просто переназначаються посилання.
ПошукO(n)Як і у звичайному списку.

5. Переваги

  • Можна обходити список по колу без перевірки "кінця".
  • Зручний для циклічних структур: черг, буферів, ігрових циклів, кругового розподілу завдань ("round-robin").
  • Немає "мертвого кінця" (None), кожен вузол пов'язаний з іншими.

6. Недоліки

  • Потрібно обережно працювати з циклами, інакше програма може застрягти в нескінченному обході.
  • Складніше контролювати початок і кінець.

7. Приклад на Python

python
class Node: def __init__(self, data): self.data = data self.next = None # створення циклічного списку: 10 → 20 → 30 → назад на 10 n1 = Node(10) n2 = Node(20) n3 = Node(30) n1.next = n2 n2.next = n3 n3.next = n1 # цикл head = n1

Підсумок:

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

Коротка відповідь

Для співбесіди
Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.

Запропонувати правку