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

Sette inn elementet i begynnelsen:For å sette inn det nye elementet i begynnelsen, må vi først flytte elementet mot høyre for å lage et mellomrom i den første posisjonen. Så tidskompleksiteten vil være proporsjonal med størrelsen på listen. Hvis n er størrelsen på matrisen, vil tidskompleksiteten være O(n).

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).

Sette inn et element på slutten

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).

Sette inn et element i midten

Anta at vi vil sette inn elementet ved i-en^thposisjonen 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:

Brukervennlighet

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.

Dynamisk i størrelsen

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.