Разлика между списъка с масиви и свързания списък

Как се съхраняват данни?

Списъкът с масиви и свързаният списък са общи термини, когато става въпрос за съхранение и извличане на данни. Въпреки че има много устройства за съхранение, в крайна сметка те зависят от механизма за съхранение. Тези два механизма за съхранение поставят вашите данни в устройствата за съхранение и ги извличате, когато е необходимо. Нека да разгледаме как съхраняват данни в паметта си. Списъкът Array използва последователно съхранение и частите данни се съхраняват един след друг. Това е може би по-проста форма на съхранение - избягва объркване. Да, можем да извлечем следващия елемент или данни от следващото място в паметта на списъка с масиви; той обаче се съхранява с помощта на указатели в списъка Свързани. Тук имаме нужда от две места за памет за съхранение - едното за данните, другото за показалеца. Показалец адресира местоположението на паметта на следващите данни. Лесно можем да разберем, че свързаният списък никога не съхранява данни последователно; по-скоро използва механизъм за случайно съхранение. Показалците са ключовите елементи при намирането на местата с данни в паметта.

Динамичен масив и свързан списък

Вече сме обсъдили как двата механизма за съхранение въвеждат данни и можем да дадем термин „динамичен масив“ за вътрешната схема за съхранение на списъка Array. Той просто поставя части от данни едно след друго - оттук и името - докато списъкът Linked използва вътрешен списък с помощта на указатели, за да проследи следващия елемент. Следователно, той използва вътрешен свързан списък, като единично или двойно свързан списък, за да ни покаже следващите данни.

Използване на паметта

Тъй като списъкът с масиви съхранява само действителните данни, ние се нуждаем от място само за данните, които съхраняваме. Обратно, в списъка Свързани също използваме указатели. Следователно са необходими две места в паметта и можем да кажем, че свързаният списък изразходва повече памет от списъка Array. Предимство на списъка на свързаните страни е, че той никога не изисква непрекъснати местоположения в паметта, за да съхранява нашите данни, за разлика от списъка с масиви. Указателите са способни да задържат позицията на следващото местоположение на данни и дори можем да използваме по-малки слотове за памет, които не са непрекъснати. Що се отнася до използването на паметта, указателите играят главната роля в списъка на свързаните лица, а също така и ефективността на тях.

Размер на първоначалния списък на масивите и свързания списък

Със списъка Array дори празният списък изисква размер 10, но със списък на свързаните, не ни трябва такова огромно пространство. Можем да създадем празен свързан списък с размер 0. По-късно можем да увеличим размера според нуждите.

Извличане на данни

Извличането на данни е по-просто в списъка с масиви, тъй като се съхранява последователно. Всичко, което прави, е да идентифицира първото местоположение на данни; от там следващото местоположение се осъществява последователно, за да се изтеглят останалите. Той изчислява като първата позиция на данните + 'n', където 'n' е редът на данните в списъка Array. Списъкът свързан се отнася за първоначалния указател за намиране на първото местоположение на данни, а от там той препраща указателя, свързан с всяка информация, за да намери следващото местоположение на данни. Процесът на извличане зависи основно от указателите тук и те ефективно ни показват следващото местоположение на данни.

Край на данните

Списъкът Array използва нулева стойност, за да маркира края на данните, докато списъкът Linked използва нулев указател за тази цел. Веднага след като системата разпознае нулеви данни, списъкът Array спира следващото извличане на данни. По подобен начин нулевият показалец спира системата да премине към следващото извличане на данни.

Обратно преминаване

Списъкът Свързани ни позволява да се движим в обратните посоки с помощта на низходящия (). В списъка с масиви обаче нямаме такова съоръжение - обратното преминаване се превръща в проблем тук.

Синтаксис

Нека разгледаме синтаксиса на Java и на двата механизма за съхранение.

Създаване на списък от масиви:

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

Добавяне на обекти в списъка с масиви:

Arraylistsample.add ( "NAME1");

Arraylistsample.add ( "NAME2");

Ето как ще изглежда резултатният списък с масиви - [name1, name2].

Създаване на свързан списък:

Списък свързани списъци пример = нов свързан списък ();

Добавяне на обекти към свързания списък:

Linkedlistsample.add ( "NAME3");

Linkedlistsample.add ( "NAME4");

Ето как ще изглежда полученият свързан списък - [name3, name4].

 Кое е по-добро за операцията „Извличане или търсене“?

Списъкът с масиви отнема O (1) време за стартиране на всякакво търсене на данни, докато списъкът свързан отнема u O (n) за n^тата търсене на данни. Следователно списъкът с масиви винаги използва постоянно време за каквото и да е търсене на данни, но в списъка свързан, времето, което отнема, зависи от позицията на данните. Следователно списъците с масиви винаги са по-добър избор за операции Получаване или търсене.

Кое е по-добре за операцията за вмъкване или добавяне?

Както списъкът Array, така и свързаният списък отнемат O (1) време за добавяне на данни. Но ако масивът е пълен, тогава списъкът Array отнема много време, за да го преоразмерите и да копирате елементите в по-новия. В такъв случай списъкът на свързаните лица е по-добрият избор.

Кое е по-добро за операцията за премахване?

Операцията за премахване отнема почти еднакъв период от време както в списъка Array, така и в списъка Linked. В списъка Array тази операция изтрива данните и след това измества позицията на данните, за да образува по-новия масив - отнема време O (n). В списъка Свързани, тази операция преминава към конкретните данни и променя позициите на показалеца, за да образува по-новия списък. Времето за преминаването и отстраняването е O (n) и тук.

Което е по-бързо?

Знаем, че списъкът с масиви използва вътрешен масив за съхранение на действителните данни. Следователно, ако някои данни се изтрият, всички следващи данни се нуждаят от смяна на паметта. Очевидно това изисква значително време и забавя нещата. Такова изместване на паметта не се изисква в списъка на свързаните, тъй като всичко, което прави, е да промени местоположението на показалеца. Следователно, свързаният списък е по-бърз от списъка с масиви при всякакъв вид съхранение на данни. Това обаче зависи изцяло от типа операция, т.е. за операцията Вземете или потърсете, свързаният списък отнема много повече време от списъка с масив. Когато разгледаме цялостната ефективност, можем да кажем, че списъкът на свързаните страни е по-бърз.

Кога да използвате списък с масиви и свързан списък?

Списъкът с масиви е най-подходящ за по-малки изисквания за данни, където е налична непрекъсната памет. Но когато имаме работа с огромни количества данни, наличието на непрекъсната памет реализира механизмите за съхранение на данни, независимо дали е малка или огромна. След това решете кой да изберете - списъка с масиви или свързания списък. Можете да продължите със списък от масиви, когато просто се нуждаете от съхранение и извличане на данни. Но списък може да ви помогне отвъд това чрез манипулиране на данни. След като решите колко често се изисква манипулиране на данни, важно е да проверите какъв тип извличане на данни обикновено извършвате. Когато е просто Get или Search, тогава списъкът с масиви е по-добрият избор; за други операции като вмъкване или изтриване, продължете със списъка на свързаните.

Нека разгледаме разликите в таблична форма.

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