Skip to main content

Як вузли зв'язані між собою у списку?

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

Вузли у зв'язаному списку пов'язані між собою посиланнями (вказівниками) - спеціальними полями, які зберігають адресу наступного (або попереднього) вузла в пам'яті.

Тобто кожен вузол знає, куди йти далі, утворюючи ланцюжок.

1. Однозв'язний список

Кожен вузол містить:

  • дані,
  • посилання на наступний вузол (next).

Приклад:

javascript
head → [10 | *] → [20 | *] → [30 | None]
  • head вказує на перший вузол;
  • next першого вузла вказує на другий;
  • next другого - на третій;
  • next останнього (tail) = None → кінець списку.

Суть: рух можливий тільки вперед.

2. Двозв'язний список

Кожен вузол зберігає два посилання:

  • prev - на попередній вузол,
  • next - на наступний вузол.

Приклад:

javascript
None ← [10 | * | *] ↔ [20 | * | *] ↔ [30 | * | None]
  • head.prev = None
  • tail.next = None
  • Кожен внутрішній вузол знає своїх сусідів з обох боків.

Суть: можна рухатися вперед і назад.

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

Останній вузол не вказує на None, а замикається назад на перший (head):

javascript
[A | *] → [B | *] → [C | *] ↑__________________↓
  • tail.next = head
  • Іноді і head.prev = tail (у циклічному двозв'язному списку).

Суть: рух відбувається по колу - список не має кінця.

4. Візуально (аналогія)

Уяви потяг:

  • кожен вагон (вузол) знає, до якого вагона він причеплений далі,
  • іноді й до якого - позаду.
  • Якщо зчеплення замкнене по колу - це циклічний список.

Підсумок:

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

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

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

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

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