Разлика између Арраи листе и повезане листе

Како се чувају подаци?

Листа матрица и повезана листа су уобичајени појмови када је у питању складиштење и преузимање података. Иако постоји пуно уређаја за складиштење, на крају, они зависе од механизма за складиштење. Ова два механизма за чување смештају ваше податке у уређаје за чување података и проналазе их по потреби. Погледајмо како они чувају податке у својој меморији. Листа матрица користи секвенцијалну меморију, а делови података се чувају један за другим. Ово је можда једноставнији облик складиштења - избегава се забуна. Да, следећу ставку или податке можемо да пронађемо са следеће меморијске локације на листи низова; међутим, чува се уз помоћ показивача на листи за повезане. Овде су нам потребне две меморијске локације за складиштење - једна за податке, а друга за показивач. Показивач адресира меморијску локацију следећих података. Лако можемо схватити да Повезана листа никада не чува податке узастопно; радије користи механизам случајног складиштења. Показивачи су кључни елементи у проналажењу локација података у меморији.

Динамички низ и повезана листа

Већ смо разговарали о томе како оба механизма за складиштење убацују податке и можемо дати термин „динамички низ“ за интерну шему листе Арраи листе. Једноставно поставља дијелове података један за другим - отуда и назив - док Линкед листа користи интерну листу уз помоћ показивача за праћење следеће ставке. Стога користи интерну повезану листу, попут појединачно или двоструко повезане листе да би нам показао следеће податке.

Употреба меморије

Како Арраи листа похрањује само стварне податке, потребан нам је простор само за податке које похрањујемо. Супротно томе, на листи повезаних линкова користимо и показиваче. Стога су потребне двије меморијске локације и можемо рећи да повезана листа троши више меморије него листа Арраи. Повољна страна Повезане листе је та што никада не захтева непрекидне меморијске локације за чување наших података, за разлику од Арраи листе. Показивачи су способни да задрже позицију следеће локације података, а ми чак можемо да користимо мање меморијске слотове који нису непрекидни. Када је у питању употреба меморије, показивачи играју главну улогу на листи повезаних, а тиме и ефикасност истих.

Величина почетне листе матрица и повезане листе

Са списком Арраи, чак и празна листа захтева величину 10, али са повезаном листом не треба нам толико огроман простор. Можемо да направимо празну Повезану листу величине 0. Касније можемо повећати величину по потреби.

Дохват података

Дохваћање података је на листи Арраи-а једноставније јер се чува узастопно. Све што треба је идентификовати прву локацију података; одатле се следећој локацији приступа узастопно да би се преузело остало. Израчунава се као први положај података + 'н', при чему је 'н' редослед података на листи Арраи. Повезана листа односи се на почетни показивач како би се пронашла прва локација података, а одатле се упућује показивач повезан са сваким подацима да би се пронашла следећа локација података. Процес преузимања углавном зависи од овде приказаних показатеља и они нам ефективно показују следећу локацију података.

Крај података

Листа Арраи користи нулту вредност за означавање краја података, док Линкед лист користи нулл поинтер за ову сврху. Чим систем препозна нулте податке, листа Арраи зауставља наредно преузимање података. На сличан начин, нулта показивач спречава систем да пређе на следеће претраживање података.

Реверсе Траверсал

Повезана листа омогућава нам кретање у обрнутим правцима уз помоћ десцендингитератора (). Међутим, немамо такав објекат на листи Арраи - обрнути прелаз постаје проблем овде.

Синтакса

Погледајмо Јава синтаксу оба механизма за складиштење.

Стварање листе арраи:

Листа арраилистсампле = нови АрраиЛист ();

Додавање објеката у Арраи листу:

Арраилистсампле.адд ("име1");

Арраилистсампле.адд ("име2");

Овако ће изгледати резултирајућа листа Арраи - [наме1, наме2].

Израда повезане листе:

Листа повезанихлиста пример = нови повезани списак ();

Додавање објеката на списак повезаних:

Линкедлистсампле.адд ("име3");

Линкедлистсампле.адд ("име4");

Овако ће изгледати резултирајућа везана листа - [име3, име4].

 Шта је боље за операцију Дохвати или Претражите?

Листа Арраи треба О (1) времена за покретање било које претраге података, док Линкед листа узима у О (н) за н^тх претрага података. Због тога, листа Арраи увек користи константно време за било коју претрагу података, али на листи повезаних података време потребно зависи од положаја података. Стога су Арраи листе увек бољи избор за Гет или Сеарцх операције.

Шта је боље за убацивање или додавање?

И листа Арраи и повезана листа узимају О (1) време за додавање података. Али ако је низ пун, тада је листи Арраи потребно доста времена да је промијените и промијените величину те копирате ставке на новију. У таквом случају, Линкед лист је бољи избор.

Које је боље за операцију уклањања?

Операција уклањања траје готово једнаку количину времена и на листи Арраи и на листи Линкед. На листи Арраи, ова операција брише податке, а затим помера положај података да би се формирао новији низ - потребно је О (н) време. На Повезаној листи, ова операција прелази на одређене податке и мења положаје показивача како би формирала новију листу. Вријеме проласка и уклањања је и О (н) такође.

Што је брже?

Знамо да листа Арраи користи интерну матрицу за чување стварних података. Стога, ако се било који податак избрише, тада је свим наредним подацима потребан помак у меморији. Очито, за то је потребно доста времена и ствари успоравају. Овакав помак у меморији није потребан на листи повезаних, јер све што ради је промена локације показивача. Стога је Повезана листа бржа од Арраи листе у било којој врсти података. Међутим, то чисто овиси о врсти операције, тј. За операцију Гет или Сеарцх, Повезана листа захтијева пуно више времена него листа Арраи. Када погледамо цјелокупне перформансе, можемо рећи да је Линкед лист бржи.

Када треба користити листу арраи и повезану листу?

Листа арраи-ова је најприкладнија за мање потребе за подацима где је доступна непрекидна меморија. Али када се бавимо огромним количинама података, доступност континуиране меморије имплементира механизме за чување података, било да је мала или огромна. Затим одлучите коју да одаберете - Арраи лист или Линкед лист. Можете наставити са списком низа кад вам је само потребно складиштење и преузимање података. Али листа вам може помоћи и даље од манипулације подацима. Једном када одлучите колико често је потребна манипулација подацима, важно је да проверите који тип података обично обављате. Кад је само Дохвати или Претражи, тада је Арраи листа бољи избор; за остале операције као што су убацивање или брисање, идите напријед са списком повезане.

Погледајмо разлике у табеларном облику.

С.Но	Појмови	Разлике
		Низ листа	Повезана листа
1	Мода за похрану података	Користи секвенцијално чување података	Користи несеквенцијално чување података
2	Интерна шема складиштења	Одржава интерни динамички низ	Одржава повезану листу
3	Употреба меморије	Захтијева меморијски простор само за податке	Захтева меморијски простор и за податке као и за показиваче
4	Величина иницијалне листе	Потребно је простора за најмање 10 предмета	Не треба простора и чак можемо да направимо празну Повезану листу величине 0.
5	Дохват података	Израчунава као први положај података + 'н', при чему је 'н' редослед података на листи Арраи	Обилазак од првог или последњег до тражења потребних података
6	Крај података	Нулл вредности означавају крај	Нулл Поинтер означава крај
7	Реверсе Траверсал	Не дозвољава	Омогућава га уз помоћ десцендингитератор ()
8	Синтакса за креирање листе	Листа арраилистсампле = нови АрраиЛист ();	Листа повезанихлиста пример = нови повезани списак ();
9	Додавање објеката	Арраилистсампле.адд ("име1");	Линкедлистсампле.адд ("име3");
10	Претражите или претражите	Потребно је О (1) и бољи је у перформансама	Заузима О (н) време и перформансе зависе од положаја података
11	Убаци или додај	Потроши О (1) време, осим када је низ пун	Конзумира О (1) време под свим околностима
12	Брисање или уклањање	Потребно је О (н) време	Потребно је О (н) време
13	Када користити?	Када је укључено пуно операција за преузимање или претрагу; доступност меморије би требала бити већа чак и на старту	Када постоји пуно операција Уметање или брисање, а расположивост меморије не мора бити континуирана