Skip to main content

Як зв'язаний список зберігається в пам'яті?

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

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

1. Як виглядає структура

Кожен вузол зберігає:

  • дані (наприклад, число, рядок, об'єкт),
  • вказівник (посилання) на наступний вузол, а іноді й на попередній.

Приклад для однозв'язного списку:

javascript
[дані | next] → [дані | next] → [дані | None]

У пам'яті це може виглядати так (умовні адреси):

javascript
Адреса 1000: [10 | next = 2056] Адреса 2056: [20 | next = 3172] Адреса 3172: [30 | next = None]

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

2. Чому вузли не поспіль

Пам'ять виділяється динамічно (через malloc, new або аналогічні механізми). Система дає вільну ділянку, яка може бути будь-де. Тому наступний елемент списку може перебувати на зовсім іншій адресі.

3. Як програма "знаходить" елементи

  • У списку є посилання на перший елемент (head).
  • З head програма бере адресу наступного вузла з поля next.
  • Потім з того - ще одну адресу, і так по ланцюжку, поки не дійде до None.
javascript
head → вузол1 → вузол2 → вузол3 → ...

4. Для двозв'язного списку

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

javascript
[prev | дані | next]

Це дозволяє рухатися в обидва боки (вперед і назад).

5. Візуально

javascript
+------+ +------+ +------+ | 10 |•---->| 20 |•---->| 30 |X +------+ +------+ +------+ (адреси можуть бути 1000, 2056, 3172)

6. Ключова особливість

  • На відміну від масиву, де елементи "лежать поруч", у списку логічна послідовність не збігається з фізичним розташуванням.
  • Це робить список гнучким (можна додавати й видаляти елементи без зсуву), але знижує ефективність при випадковому доступі (O(n)).

Підсумок:

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

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

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

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

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