Масив і Зв'язаний список це два способи організації даних у пам’яті. Перш ніж зрозуміти відмінності між Масив і Зв'язаний список , ми спочатку дивимося в масиві і пов’язаний список .
відкритий файл java
Що таке масив?
Структура даних, яка містить елементи одного типу. Структура даних — це спосіб організації даних; масив є структурою даних, оскільки він послідовно організовує дані. Масив — це велика частина пам’яті, у якій пам’ять поділена на малі-маленькі блоки, і кожен блок здатний зберігати певне значення.
Припустимо, ми створили масив, який складається з 10 значень, тоді кожен блок буде зберігати значення цілого типу. Якщо ми спробуємо зберегти значення в масиві різних типів, це буде неправильний масив і викличе помилку під час компіляції.
Оголошення масиву
Масив можна оголосити так:
data_type name of the array[no of elements]
Щоб оголосити масив, нам спочатку потрібно вказати тип масиву, а потім ім’я масиву. У квадратних дужках нам потрібно вказати кількість елементів, які має містити наш масив.
Розберемося на прикладі.
int a[5];
У наведеному вище випадку ми оголосили масив із 5 елементів за допомогою ' a ім'я ан ціле число тип даних.
Що таке пов’язаний список?
Зв’язаний список — це набір вузлів, які зберігаються випадковим чином. Кожен вузол складається з двох полів, тобто даних і посилання . Тут дані — це значення, що зберігається на цьому конкретному вузлі, а посилання — це покажчик, який містить адресу наступного вузла.
Відмінності між масивом і пов’язаним списком
Ми не можемо сказати, яка структура даних краща, тобто масив або зв'язаний список . Існує ймовірність того, що одна структура даних є кращою для одного типу вимог, тоді як інша структура даних краща для іншого типу вимог. Існують різні фактори, наприклад те, які часті операції виконуються зі структурою даних або розмір даних, а також інші фактори, на основі яких вибирається структура даних. Тепер ми побачимо деякі відмінності між масивом і пов’язаним списком на основі деяких параметрів.
вставити в клавіатуру
1. Вартість доступу до елемента
У випадку масиву, незалежно від розміру масиву, масиву потрібен постійний час для доступу до елемента. У масиві елементи зберігаються безперервно, тому, якщо ми знаємо базову адресу елемента, ми можемо легко отримати адресу будь-якого елемента в масиві. Нам потрібно виконати просте обчислення, щоб отримати адресу будь-якого елемента в масиві. Отже, доступ до елемента в масиві є O(1) з точки зору складності часу.
У зв’язаному списку елементи не зберігаються безперервно. Він складається з кількох блоків, і кожен блок представлений як вузол. Кожен вузол має два поля, тобто одне для поля даних, а інше зберігає адресу наступного вузла. Щоб знайти будь-який вузол у пов’язаному списку, нам спочатку потрібно визначити перший вузол, відомий як головний вузол. Якщо нам потрібно знайти другий вузол у списку, то нам потрібно буде пройти від першого вузла, а в гіршому випадку, щоб знайти останній вузол, ми обійдемо всі вузли. Середній випадок доступу до елемента - O(n).
Ми робимо висновок, що вартість доступу до елемента в масиві менша, ніж вартість зв’язаного списку. Тому, якщо у нас є якісь вимоги щодо доступу до елементів, то масив є кращим вибором.
2. Вартість вставки елемента
У вставці може бути три сценарії:
У випадку пов’язаного списку, щоб вставити елемент на початку зв’язаного списку, ми створимо новий вузол, а адреса першого вузла додамо до нового вузла. Таким чином, новий вузол стає першим вузлом. Отже, часова складність не пропорційна розміру списку. Часова складність буде постійною, тобто O(1).
Якщо масив не заповнений, ми можемо безпосередньо додати новий елемент через індекс. У цьому випадку часова складність буде постійною, тобто O(1). Якщо масив заповнений, нам спочатку потрібно скопіювати його в інший масив і додати новий елемент. У цьому випадку часова складність буде O(n).
Щоб вставити елемент у кінець пов’язаного списку, нам потрібно пройти весь список. Якщо пов’язаний список складається з n елементів, то часова складність буде O(n).
Припустімо, ми хочемо вставити елемент у iтисположення масиву; нам потрібно зрушити n/2 елементів вправо. Тому часова складність пропорційна кількості елементів. Часова складність буде O(n) для середнього випадку.
вікно попередження javascript
У випадку пов’язаного списку ми повинні перейти до тієї позиції, де ми маємо вставити новий елемент. Незважаючи на те, що ми не повинні виконувати будь-які перемикання, ми повинні перейти до положення n/2. Витрачений час пропорційний n кількості елементів, а часова складність для середнього випадку буде O(n).
Отриманий пов’язаний список:
Реалізація масиву проста порівняно зі зв’язаним списком. Під час створення програми за допомогою зв’язаного списку програма більш схильна до помилок, таких як помилка сегментації або витік пам’яті. Отже, під час створення програми у пов’язаному списку потрібно бути дуже уважним.
Зв’язаний список має динамічний розмір, тоді як масив є статичним. Тут статичність не означає, що ми не можемо визначити розмір під час виконання, але ми не можемо змінити його, коли розмір визначено.
3. Вимоги до пам'яті
Оскільки елементи в масиві зберігаються в одному безперервному блоці пам’яті, тому масив має фіксований розмір. Припустимо, що у нас є масив розміром 7, і масив складається з 4 елементів, тоді решта простору не використовується. Пам'ять, зайнята 7 елементами:
Пам'ять = 7*4 = 28 байт
Де 7 — кількість елементів у масиві, а 4 — кількість байтів цілого типу.
У випадку пов’язаного списку невикористаної пам’яті немає, але додаткова пам’ять зайнята змінними-вказівниками. Якщо дані цілого типу, то загальна пам'ять, яку займає один вузол, становить 8 байт, тобто 4 байти для даних і 4 байти для змінної покажчика. Якщо зв’язаний список складається з 4 елементів, то простір пам’яті, який займає зв’язаний список, буде:
веб-драйвер
Пам'ять = 8*4 = 32 байти
Зв’язаний список буде кращим вибором, якщо частина даних має більший розмір. Припустимо, дані мають розмір 16 байт. Обсяг пам’яті, який займає масив, становитиме 16*7=112 байт, тоді як зв’язаний список займатиме 20*4=80, тут ми вказали 20 байт як 16 байт для розміру даних плюс 4 байти для змінної покажчика. Якщо ми обираємо більший розмір даних, зв’язаний список споживатиме менше пам’яті; інакше це залежить від факторів, які ми приймаємо для визначення розміру.
Давайте розглянемо відмінності між масивом і зв’язаним списком у табличній формі.
| Масив | Зв'язаний список |
|---|---|
| Масив — це набір елементів даних подібного типу. | Зв’язаний список — це набір об’єктів, відомих як вузол, де вузол складається з двох частин, тобто даних і адреси. |
| Елементи масиву зберігаються в безперервному місці пам’яті. | Елементи пов’язаного списку можна зберігати будь-де в пам’яті або зберігати у випадковому порядку. |
| Масив працює зі статичною пам'яттю. Тут статична пам'ять означає, що розмір пам'яті фіксований і не може бути змінений під час виконання. | Зв'язаний список працює з динамічною пам'яттю. Тут динамічна пам'ять означає, що розмір пам'яті можна змінювати під час виконання відповідно до наших вимог. |
| Елементи масиву не залежать один від одного. | Елементи пов’язаного списку залежать один від одного. Оскільки кожен вузол містить адресу наступного вузла, тому для доступу до наступного вузла нам потрібно отримати доступ до його попереднього вузла. |
| Масив займає більше часу під час виконання будь-яких операцій, таких як вставка, видалення тощо. | Зв’язаний список займає менше часу під час виконання будь-яких операцій, таких як вставка, видалення тощо. |
| Доступ до будь-якого елемента в масиві є швидшим, оскільки до елемента в масиві можна отримати прямий доступ через індекс. | Доступ до елемента у зв’язаному списку відбувається повільніше, оскільки він починається з першого елемента зв’язаного списку. |
| У випадку масиву пам'ять виділяється під час компіляції. | У випадку пов’язаного списку пам’ять виділяється під час виконання. |
| Використання пам'яті в масиві неефективне. Наприклад, якщо розмір масиву дорівнює 6, а масив складається лише з 3 елементів, то решта простору буде невикористаною. | Використання пам’яті є ефективним у випадку пов’язаного списку, оскільки пам’ять може бути виділена або звільнена під час виконання відповідно до наших вимог. |