Forskjellen mellom Array List og Linked List
Share
Hvordan lagres data?
Array-liste og tilknyttet liste er vanlige vilkår når det gjelder datalagring og gjenfinning. Selv om det er mange lagringsenheter, er de i siste instans avhengige av lagringsmekanismen. Disse to lagringsmekanismer plasserer dataene dine i lagringsenhetene og henter dem når det trengs. La oss se på hvordan de lagrer data i minnet. Array-listen bruker en sekventiell lagring, og dataene lagres hver for seg. Dette er kanskje en enklere form for lagring - det unngår forvirring. Ja, vi kan hente neste gjenstand eller data fra neste minnestilling i matelisten; Det lagres imidlertid ved hjelp av pekere på listen over lenker. Her trenger vi to minnesteder for lagring - en for dataene, den andre for pekeren. En peker adresserer minnestedet til de neste dataene. Vi kan lett forstå at koblet liste aldri lagrer data sekvensielt; heller, det bruker en tilfeldig lagringsmekanisme. Poengene er nøkkelelementene i å finne datalokalene i minnet.
Dynamisk Array og Linked List
Vi har allerede diskutert hvordan begge lagringsmekanismer legger inn data, og vi kan gi et begrep 'dynamisk array' til Array-listen interne lagringsprogram. Det setter bare databitene etter hverandre - derav navnet - mens den tilknyttede listen bruker en intern liste ved hjelp av pekere for å spore neste element. Derfor bruker den en intern koblet liste, som en enkelt eller dobbeltkoblet liste for å vise oss de neste dataene.
Minnebruk
Som Array-liste lagrer bare de faktiske dataene, trenger vi plass bare for dataene vi lagrer. Omvendt, i den kalkulerte listen, bruker vi også pekere. Derfor er det nødvendig med to minnesteder, og vi kan si at koblet liste bruker mer minne enn Array-listen. En fordelaktig side av koblet liste er at det aldri krever kontinuerlige minnesteder å lagre våre data, i motsetning til Array-listen. Pointers er i stand til å holde posisjonen til neste datalokasjon, og vi kan til og med bruke mindre minnespor som ikke er kontinuerlige. Når det gjelder minnebruk, spiller pekere hovedrollen i den koble listen, og det gjør også effektiviteten av dem.
Størrelse på startlisten og tilknyttet liste
Med Array-listen krever selv en tom liste en størrelse på 10, men med en koblet liste trenger vi ikke så stor plass. Vi kan opprette en tom koblet liste med en størrelse på 0. Senere kan vi øke størrelsen etter behov.
Datainnhenting
Datainnhenting er enklere i Array-listen som den lagrer i rekkefølge. Alt det gjør er å identifisere den første datalokasjonen; derfra, er neste plassering tilgjengelig sekvensielt for å hente resten. Den beregner som den første dataposisjonen + 'n', hvor 'n' er rekkefølgen av dataene i Array-listen. Den tilknyttede listen refererer til den første pekeren for å finne den første datalokasjonen, og derfra refererer den pekeren som er knyttet til hver data for å finne neste datalokasjon. Hentingsprosessen er hovedsakelig avhengig av pekerne her, og de viser oss effektivt den neste datalokasjonen.
Slutt av data
Array-listen bruker en nullverdi for å markere slutten av dataene, mens den tilknyttede listen bruker en nullpeker for dette formålet. Så snart systemet gjenkjenner nulldata, stopper Array-listen neste datainnhenting. På samme måte stopper nullpekeren systemet fra å fortsette til neste datainnhenting.
Omvendt traversal
Tilknyttede listen lar oss krysse i omvendte retninger ved hjelp av descendingiterator (). Vi har imidlertid ikke et slikt anlegg i en Array-liste - omvendt traversal blir et problem her.
syntax
La oss se på Java-syntaksen for begge lagringsmekanismer.
Array list opprettelse:
Liste arraylistsample = ny ArrayList ();
Legge til objekter i Array-listen:
Arraylistsample.add ( “name1”);
Arraylistsample.add ( “name2”);
Slik ser den resulterende Array-listen ut - [navn1, navn2].
Opprettelse av tilknyttet liste:
Liste linkedlistsample = new linkedList ();
Legge til objekter i tilknyttet liste:
Linkedlistsample.add ( “NAME3”);
Linkedlistsample.add ( “NAME4”);
Slik ser den resulterende koblede listen ut - [navn3, navn4].
Som er bedre for Get eller Search-operasjonen?
Arraylisten tar O (1) tid til å kjøre noe datasøk, mens den lenkede listen tar deg O (n) for nth datasøk. Derfor bruker en Array-liste alltid en konstant tid for datasøk, men i den kalkulerte listen avhenger avhenger av dataens posisjon. Derfor er Array-lister alltid et bedre valg for Get eller Search-operasjoner.
Hvilken er bedre for innsetting eller tilleggsoperasjon?
Både Array-listen og den tilknyttede listen tar O (1) tid for data tillegg. Men hvis arrayet er fullt, tar Array-listen betydelig tid til å endre størrelsen på den og kopiere elementene til den nyere. I et slikt tilfelle er Linked List det bedre valget.
Som er bedre for fjerning av operasjonen?
Fjernoperasjonen tar omtrent samme tid i både Array-listen og den tilknyttede listen. I Array-listen sletter denne operasjonen dataene og deretter skifter posisjonen til dataene for å danne nyere array - det tar O (n) tid. I tilknyttet liste går denne operasjonen til bestemte data og endrer pekerposisjoner for å danne den nyere listen. Tiden for traversal og fjerning er O (n) her også.
Som er raskere?
Vi vet at en Array-liste bruker et internt array for å lagre de faktiske dataene. Derfor, hvis noen data slettes, trenger alle de kommende dataene et minneskifte. Dette krever åpenbart en betydelig mengde tid og bremser ting ned. Et slikt minneforskyvning er ikke påkrevd i listen over lenker, da alt det gjør er å endre pekerens plassering. Derfor er en tilknyttet liste raskere enn en Array-liste i enhver form for datalagring. Dette er imidlertid bare avhengig av operasjonstypen, dvs. for Get or Search-operasjonen, tar den kalkulerte listen mye mer tid enn en Array-liste. Når vi ser på den generelle ytelsen, kan vi si at Linked List er raskere.
Når skal du bruke en Array List og en tilknyttet liste?
En Array-liste passer best for mindre datakrav hvor kontinuerlig minne er tilgjengelig. Men når vi håndterer store mengder data, sørger tilgjengeligheten for kontinuerlig minne for datalagringsmekanismer, enten det er liten eller stor. Deretter bestemmer hvilken som skal velges - Array-listen eller den tilknyttede listen. Du kan fortsette med en mateliste når du bare trenger lagring og gjenfinning av data. Men en liste kan hjelpe deg utover det ved å manipulere data. Når du bestemmer hvor ofte datamanipulering er nødvendig, er det viktig å sjekke hvilken type datainnhenting du vanligvis utfører. Når det bare er Få eller Søk, er Arraylisten det bedre valget; For andre operasjoner som Insertion eller Deletion, fortsett med Linked List.
La oss se på forskjellene i tabellform.
| S.No | Begreper | forskjeller | |
| Array List | Tilknyttet liste | ||
| 1 | Data Lagring Mote | Bruker sekvensiell datalagring | Bruker ikke-sekventiell datalagring |
| 2 | Intern lagringssystem | Opprettholder et internt dynamisk array | Opprettholder en tilknyttet liste |
| 3 | Minnebruk | Krever minneplass bare for dataene | Krever minneplass for data også for pekere |
| 4 | Størrelsen på den opprinnelige listen | Trenger plass til minst 10 elementer | Trenger ikke plass, og vi kan til og med lage en tom Tilknyttet liste over størrelse 0. |
| 5 | Datainnhenting | Beregner som den første dataposisjonen + 'n', hvor 'n' er rekkefølgen av dataene i Array-listen | Forflytting fra første eller siste til de nødvendige dataene er nødvendig |
| 6 | Slutt av data | Null-verdiene markerer slutten | Null Pointer markerer slutten |
| 7 | Omvendt traversal | Tillater ikke det | Tillater det ved hjelp av descendingiterator () |
| 8 | Synkronisering av listeskaper | Liste arraylistsample = ny ArrayList ();
| Liste linkedlistsample = new linkedList ();
|
| 9 | Legge til objekter | Arraylistsample.add ( “name1”);
| Linkedlistsample.add ( “NAME3”);
|
| 10 | Få eller Søk | Tar O (1) tid og er bedre i ytelse | Tar O (n) tid og ytelse er avhengig av posisjonen til dataene |
| 11 | Sett inn eller legg til | Forbruker O (1) tid bortsett fra når matrisen er full | Går O (1) tid under alle omstendigheter |
| 12 | Sletting eller fjerning | Tar O (n) tid | Tar O (n) tid |
| 1. 3 | Når skal du bruke? | Når det er mange Get or Search-operasjoner involvert; minnetilgjengeligheten skal være høyere selv ved starten | Når det er mange innstikk- eller slettoperasjoner, og minnetilgjengelighet ikke trenger å være kontinuerlig |
