Array og Koblet liste er de to måtene å organisere dataene i minnet på. Før du forstår forskjellene mellom Array og Koblet liste , ser vi først ved en rekke og en koblet liste .
mysql liste alle brukere
Hva er en array?
En datastruktur som inneholder elementene av samme type. En datastruktur er en måte å organisere dataene på; en matrise er en datastruktur fordi den organiserer dataene sekvensielt. En matrise er en stor del av minnet der minnet er delt inn i små-små blokker, og hver blokk er i stand til å lagre en viss verdi.
Anta at vi har laget en matrise som består av 10 verdier, så vil hver blokk lagre verdien til en heltallstype. Hvis vi prøver å lagre verdien i en rekke forskjellige typer, er det ikke en riktig matrise og vil gi en kompileringstidsfeil.
Erklæring av array
En matrise kan deklareres som:
data_type name of the array[no of elements]
For å deklarere en matrise, må vi først spesifisere typen av matrisen og deretter matrisens navn. Innenfor de firkantede parentesene må vi spesifisere antall elementer som matrisen vår skal inneholde.
La oss forstå gjennom et eksempel.
int a[5];
I tilfellet ovenfor har vi erklært en matrise med 5 elementer med ' en ' navn på en heltall data-type.
Hva er koblet liste?
En koblet liste er samlingen av noder som er tilfeldig lagret. Hver node består av to felt, dvs. data og link . Her er data verdien som er lagret på den aktuelle noden, og lenken er pekeren som holder adressen til neste node.
Forskjeller mellom Array og Linked List
Vi kan ikke si hvilken datastruktur som er bedre, dvs. array eller koblet liste . Det kan være en mulighet for at en datastruktur er bedre for en type krav, mens den andre datastrukturen er bedre for en annen type krav. Det er forskjellige faktorer som hva som er de hyppige operasjonene som utføres på datastrukturen eller størrelsen på dataene, og andre faktorer også på hvilket grunnlag datastrukturen er valgt. Nå vil vi se noen forskjeller mellom matrisen og den koblede listen basert på noen parametere.
1. Kostnad for å få tilgang til et element
I tilfelle av en matrise, uavhengig av størrelsen på en matrise, tar en matrise konstant tid for å få tilgang til et element. I en matrise lagres elementene på en sammenhengende måte, så hvis vi kjenner grunnadressen til elementet, kan vi enkelt få adressen til ethvert element i en matrise. Vi må utføre en enkel beregning for å få adressen til ethvert element i en matrise. Så tilgang til elementet i en matrise er O(1) når det gjelder tidskompleksitet.
I den koblede listen lagres ikke elementene på en sammenhengende måte. Den består av flere blokker, og hver blokk er representert som en node. Hver node har to felt, dvs. ett er for datafeltet, og et annet lagrer adressen til neste node. For å finne en node i den koblede listen, må vi først bestemme den første noden kjent som hodenoden. Hvis vi må finne den andre noden i listen, må vi krysse fra den første noden, og i verste fall, for å finne den siste noden, vil vi krysse alle nodene. Gjennomsnittlig tilfelle for tilgang til elementet er O(n).
Vi konkluderer med at kostnaden for å få tilgang til et element i array er mindre enn den koblede listen. Derfor, hvis vi har noen krav for å få tilgang til elementene, er array et bedre valg.
2. Kostnad for å sette inn et element
Det kan være tre scenarier i innsettingen:
uordensgjennomgang av binært tre
I tilfelle av en koblet liste, for å sette inn et element i starten av den koblede listen, vil vi opprette en ny node, og adressen til den første noden legges til den nye noden. På denne måten blir den nye noden den første noden. Så tidskompleksiteten er ikke proporsjonal med størrelsen på listen. Tidskompleksiteten vil være konstant, dvs. O(1).
Hvis matrisen ikke er full, kan vi legge til det nye elementet direkte gjennom indeksen. I dette tilfellet vil tidskompleksiteten være konstant, dvs. O(1). Hvis matrisen er full, må vi først kopiere matrisen til en annen matrise og legge til et nytt element. I dette tilfellet vil tidskompleksiteten være O(n).
For å sette inn et element på slutten av den koblede listen, må vi krysse hele listen. Hvis den koblede listen består av n elementer, vil tidskompleksiteten være O(n).
Anta at vi vil sette inn elementet ved i-enthposisjonen til matrisen; vi må flytte n/2-elementene mot høyre. Derfor er tidskompleksiteten proporsjonal med antall elementer. Tidskompleksiteten vil være O(n) for gjennomsnittstilfellet.
java-sjekken er null
I tilfelle av koblet liste, må vi gå til den posisjonen der vi må sette inn det nye elementet. Selv om vi ikke trenger å utføre noen form for skifting, men vi må traversere til n/2-posisjon. Tiden det tar er proporsjonal med n antall elementer, og tidskompleksiteten for det gjennomsnittlige tilfellet vil være O(n).
Den resulterende tilknyttede listen er:
Implementeringen av en matrise er enkel sammenlignet med den koblede listen. Mens du oppretter et program ved hjelp av en koblet liste, er programmet mer utsatt for feil som segmenteringsfeil eller minnelekkasje. Så, mye forsiktighet må tas når du oppretter et program i den koblede listen.
Den koblede listen er dynamisk i størrelse, mens matrisen er statisk. Her betyr ikke statisk at vi ikke kan bestemme størrelsen på kjøretiden, men vi kan ikke endre den når størrelsen er bestemt.
3. Minnekrav
Ettersom elementene i en matrise lagrer i en sammenhengende minneblokk, er matrisen av fast størrelse. Anta at vi har en matrise med størrelse 7, og matrisen består av 4 elementer, så er resten av plassen ubrukt. Minnet okkupert av de 7 elementene:
Minneplass = 7*4 = 28 byte
Der 7 er antall elementer i en matrise og 4 er antall byte av en heltallstype.
I tilfelle koblet liste er det ikke noe ubrukt minne, men det ekstra minnet er okkupert av pekervariablene. Hvis dataene er av heltallstype, er totalt minne okkupert av en node 8 byte, dvs. 4 byte for data og 4 byte for pekervariabel. Hvis den koblede listen består av 4 elementer, vil minneplassen som opptas av den koblede listen være:
webdriver
Minneplass = 8*4 = 32 byte
Den koblede listen ville være et bedre valg hvis datadelen er større i størrelse. Anta at dataene er på 16 byte. Minneplassen okkupert av matrisen vil være 16*7=112 byte mens den koblede listen opptar 20*4=80, her har vi spesifisert 20 byte som 16 byte for størrelsen på dataene pluss 4 byte for pekervariabelen. Hvis vi velger den større datastørrelsen, vil den koblede listen bruke mindre minne; ellers avhenger det av faktorene vi bruker for å bestemme størrelsen.
La oss se på forskjellene mellom matrisen og den koblede listen i en tabellform.
| Array | Koblet liste |
|---|---|
| En matrise er en samling av elementer av en lignende datatype. | En koblet liste er en samling av objekter kjent som en node der noden består av to deler, dvs. data og adresse. |
| Matriseelementer lagres på en sammenhengende minneplassering. | Koblede listeelementer kan lagres hvor som helst i minnet eller tilfeldig lagres. |
| Array fungerer med et statisk minne. Her betyr statisk minne at minnestørrelsen er fast og ikke kan endres under kjøretiden. | Den koblede listen fungerer med dynamisk minne. Her betyr dynamisk minne at minnestørrelsen kan endres på kjøretiden i henhold til våre krav. |
| Matriseelementer er uavhengige av hverandre. | Koblede listeelementer er avhengige av hverandre. Siden hver node inneholder adressen til den neste noden for å få tilgang til neste node, må vi få tilgang til den forrige noden. |
| Array tar mer tid mens du utfører operasjoner som innsetting, sletting osv. | Koblet liste tar mindre tid mens du utfører operasjoner som innsetting, sletting osv. |
| Tilgang til ethvert element i en matrise er raskere ettersom elementet i en matrise kan nås direkte gjennom indeksen. | Tilgang til et element i en koblet liste er tregere ettersom det begynner å krysse fra det første elementet i den koblede listen. |
| Når det gjelder en matrise, tildeles minne ved kompilering. | I tilfellet med en koblet liste, tildeles minne ved kjøring. |
| Minneutnyttelse er ineffektiv i matrisen. For eksempel, hvis størrelsen på matrisen er 6, og matrisen består av bare 3 elementer, vil resten av plassen være ubrukt. | Minneutnyttelse er effektiv i tilfelle av en koblet liste, da minnet kan tildeles eller deallokeres på kjøretiden i henhold til vårt krav. |