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

Як зберігаються дані?

Список масивів та пов'язаний список - загальні терміни, коли мова йде про зберігання та пошук даних. Хоча накопичувачів багато, в кінцевому рахунку вони залежать від механізму зберігання. Ці два механізми зберігання розміщують ваші дані на пристроях зберігання даних та отримують їх у разі потреби. Давайте розглянемо, як вони зберігають дані у своїй пам'яті. У списку масивів використовується послідовне зберігання, а фрагменти даних зберігаються одна за одною. Це, мабуть, простіша форма зберігання - це дозволяє уникнути плутанини. Так, ми можемо отримати наступний елемент або дані з наступного місця пам'яті списку масивів; однак він зберігається за допомогою покажчиків у списку пов'язаних. Тут нам потрібно два місця пам’яті для зберігання - одне для даних, інше для вказівника. Вказівник адреси адреси пам'яті наступних даних. Ми можемо легко зрозуміти, що пов'язаний список ніколи не зберігає дані послідовно; скоріше, він використовує механізм випадкового зберігання. Покажчики є ключовими елементами розміщення місць даних у пам'яті.

Динамічний масив та пов'язаний список

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

Використання пам'яті

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

Розмір початкового списку масивів та пов'язаного списку

За списком Array навіть порожній список вимагає розміру 10, але зі списком зв'язаних нам такий величезний простір не потрібен. Ми можемо створити порожній пов'язаний список розміром 0. Пізніше ми можемо збільшити розмір за потребою.

Отримання даних

Пошук даних простіший у списку масивів, оскільки він зберігається послідовно. Все, що він робить, це визначити перше місце розташування даних; звідти до наступного місця звертаються послідовно, щоб отримати решту. Він обчислює як перше положення даних + 'n', де 'n' - це порядок даних у списку масиву. Список пов'язаних відносин посилається на початковий вказівник на пошук першого місця розташування даних, а звідти він посилається на вказівник, пов'язаний з кожними даними, щоб знайти наступне місце даних. Процес пошуку в основному залежить від покажчиків тут, і вони ефективно показують нам наступне місцезнаходження даних.

Кінець даних

Список масиву використовує нульове значення для позначення кінця даних, тоді як список пов'язаних елементів використовує для цього нульовий покажчик. Як тільки система розпізнає нульові дані, список масиву зупиняє наступне пошук даних. Аналогічним чином нульовий покажчик зупиняє систему від переходу до наступного пошуку даних.

Зворотний обхід

Список "Зв'язаний" дозволяє нам переходити в зворотному напрямку за допомогою десцендентатора (). Однак у нас у списку масивів такого об’єкту немає - зворотна траверсія тут стає проблемою.

Синтаксис

Давайте розглянемо синтаксис Java обох механізмів зберігання.

Створення списку масивів:

Список arraylistsample = новий ArrayList ();

Додавання об'єктів до списку масивів:

Arraylistsample.add ("ім'я1");

Arraylistsample.add ("ім'я2");

Ось так виглядатиме результуючий список масиву - [name1, name2].

Створення пов'язаного списку:

Список linkedlistsample = новий пов'язаний список ();

Додавання об'єктів до пов'язаного списку:

Linkedlistsample.add ("ім'я3");

Linkedlistsample.add ("ім'я4");

Ось так виглядатиме результат пов'язаного списку - [name3, name4].

 Що краще для операцій "Отримати або шукати"?

Список масиву займає час O (1) для здійснення будь-якого пошуку даних, тоді як список пов'язаних значень займає u O (n) для n^го пошук даних. Отже, список масивів завжди використовує постійний час для будь-якого пошуку даних, але у списку зв'язаних значень час залежить від позиції даних. Тому списки масивів завжди є кращим вибором для операцій Get або Search.

Що краще для операцій із вставкою чи доповненням?

Як список масиву, так і пов'язаний список потребують часу (O) для додавання даних. Але якщо масив заповнений, то для списку масивів потрібна значна кількість часу, щоб змінити його розмір та скопіювати елементи на новіший. У такому випадку кращий вибір пов'язаний список.

Що краще для операції видалення?

Операція видалення займає майже однакову кількість часу як у списку масиву, так і у списку пов'язаних. У списку Масив ця операція видаляє дані, а потім зміщує положення даних, щоб сформувати новіший масив - це займає час O (n). У пов'язаному списку ця операція переходить до конкретних даних і змінює позиції вказівника, щоб сформувати новий список. Час обходу та вилучення тут також є O (n).

Що швидше?

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

Коли використовувати список масивів та пов'язаний список?

Список масиву найкраще підходить для менших вимог до даних, коли доступна безперервна пам'ять. Але коли ми маємо справу з величезними обсягами даних, наявність безперервної пам'яті реалізує механізми зберігання даних, будь то невеликі чи величезні. Далі визначте, який вибрати - список масиву або список пов'язаних. Ви можете продовжити список масивів, коли вам просто потрібно зберігання та пошук даних. Але список може допомогти вам поза цим, маніпулюючи даними. Після того як ви вирішили, наскільки часто потрібно обробляти дані, важливо перевірити, який тип пошуку даних ви зазвичай здійснюєте. Коли це просто Отримати або Шукати, тоді краще список списку масивів; для інших операцій, таких як Вставка або Видалення, продовжуйте перелік пов'язаних.

Давайте розглянемо відмінності в табличній формі.

S.No	Поняття	Відмінності
		Список масивів	Пов'язаний список
1	Мода зберігання даних	Використовує послідовне зберігання даних	Використовує непослідовне зберігання даних
2	Схема внутрішнього зберігання	Зберігає внутрішній динамічний масив	Веде список зв’язків
3	Використання пам'яті	Потрібен об'єм пам'яті лише для даних	Потрібен об'єм пам'яті для даних, а також для покажчиків
4	Розмір початкового списку	Потрібно місця для щонайменше 10 предметів	Не потрібен простір, і ми можемо навіть створити порожній список пов'язаних розмірів 0.
5	Отримання даних	Обчислюється як перша позиція даних + 'n', де 'n' - це порядок даних у списку масиву	Обхід від першого або останнього до необхідних даних
6	Кінець даних	Значення Null позначають кінець	Нульовий покажчик знаменує кінець
7	Зворотний обхід	Не дозволяє	Дозволяє це за допомогою десцентратора ()
8	Синтаксис створення списку	Список arraylistsample = новий ArrayList ();	Список linkedlistsample = новий пов'язаний список ();
9	Додавання об’єктів	Arraylistsample.add ("ім'я1");	Linkedlistsample.add ("ім'я3");
10	Отримати або шукати	Займає O (1) час і краще в роботі	Займає O (n) час, а продуктивність залежить від положення даних
11	Вставити або доповнити	Споживає час O (1), за винятком випадків, коли масив заповнений	Споживає O (1) час за будь-яких обставин
12	Видалення або видалення	Займає O (n) час	Займає O (n) час
13	Коли використовувати?	Коли задіяно чимало операцій з пошуку або пошуку; доступність пам'яті повинна бути більшою навіть на початку	Коли операцій "Вставити" та "Видалити" є безліч, і наявність пам'яті не потрібно постійно