Чим масив відрізняється від списку?
Масив і список - обидві структури даних, у яких зберігаються набори елементів, але вони по-різному влаштовані всередині і призначені для різних завдань.
1. Структура зберігання
- Масив зберігає елементи у безперервних комірках пам'яті. Це означає, що кожен елемент лежить строго поряд із попереднім, і всі вони одного типу (наприклад, лише числа).
- Список (зв'язний список) зберігає елементи в окремих вузлах, кожен із яких містить значення і посилання на наступний елемент. Тому елементи можуть розташовуватися в пам'яті будь-де.
2. Швидкодія операцій
| Операція | Масив | Список |
|---|---|---|
| Доступ за індексом | O(1) - прямий доступ | O(n) - потрібно пройти по вузлах |
| Вставка/видалення в середині | O(n) - потребує зсуву | O(1), якщо вузол відомий |
| Пошук елемента | O(n) | O(n) |
| Використання пам'яті | Компактне | Більше (через посилання) |
3. Тип даних
- Масив зберігає однорідні дані - всі елементи одного типу (у мовах на кшталт C, Java, C++).
- Список може зберігати різнотипні елементи і навіть інші списки.
4. Розмір
- Масив зазвичай має фіксований розмір (не можна просто "додати" елемент без виділення нової пам'яті).
- Список може динамічно рости і зменшуватися - просто змінюються посилання.
5. Приклад візуально
Масив:
[10][20][30][40] - елементи підряд.
Список:
[10 | *] → [20 | *] → [30 | *] → [40 | None] - кожен елемент "вказує" на наступний.
6. Приклад у Python
У Python
list- це динамічний масив, а не класичний зв'язний список. Але якщо говорити про теорію, під "списком" зазвичай мають на увазі саме зв'язний список.
Підсумок:
Масив - швидший для доступу і економніший за пам'яттю. Список - гнучкіший для вставок і видалень, але повільніший за прямого звернення.
Коротка відповідь
Для співбесідиPremium
Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.