Різниця між масивами та пов'язаними списками

Масиви проти пов'язаних списків

Масиви - це найбільш часто використовувана структура даних для зберігання колекції елементів. Більшість мов програмування надають методи легко оголошувати масиви та елементи доступу до масивів. Пов'язаний список, точніше окремо пов'язаний список, також є структурою даних, яка може використовуватися для зберігання колекції елементів. Він складається з послідовності вузлів і кожен вузол має посилання на наступний вузол у послідовності.

Показаний на малюнку 1 - це фрагмент коду, який зазвичай використовується для оголошення та призначення значень масиву. На малюнку 2 зображено, як виглядатиме масив у пам'яті.

Наведений вище код визначає масив, який може зберігати 5 цілих чисел, і до них доступ, використовуючи індекси від 0 до 4. Одне важливе властивість масиву полягає в тому, що весь масив виділяється як єдиний блок пам'яті і кожен елемент отримує власний простір у масиві. Як тільки масив визначений, його розмір фіксується. Отже, якщо ви не впевнені в розмірі масиву під час компіляції, вам доведеться визначити достатньо великий масив, щоб бути в безпечній частині. Але більшу частину часу ми фактично будемо використовувати меншу кількість елементів, ніж ми виділили. Тож чималий обсяг пам’яті насправді витрачено. З іншого боку, якщо "достатньо великий масив" насправді недостатньо великий, програма вийде з ладу.

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

Малюнок 3: Елемент пов'язаного списку

На малюнку 4 зображений зв'язаний список з трьома елементами. Кожен елемент зберігає свої дані та всі елементи, крім останнього, зберігає посилання на наступний елемент. Останній елемент містить нульове значення у наступному полі. Будь-який елемент у списку можна отримати, починаючи з заголовка та слідуючи наступному вказівнику, поки ви не зустрінете потрібний елемент.

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