TechCodeview

Array og Linket liste er de to måder at organisere dataene i hukommelsen på. Før du forstår forskellene mellem Array og Linket liste , ser vi først ved et array og en linket liste .

mysql liste over alle brugere

Hvad er et array?

En datastruktur, der indeholder elementer af samme type. En datastruktur er en måde at organisere data på; et array er en datastruktur, fordi det sekventielt organiserer dataene. Et array er en stor del af hukommelsen, hvor hukommelsen er opdelt i små-små blokke, og hver blok er i stand til at lagre en vis værdi.

Antag, at vi har oprettet et array, der består af 10 værdier, så vil hver blok gemme værdien af ​​en heltalstype. Hvis vi forsøger at gemme værdien i et array af forskellige typer, så er det ikke et korrekt array og vil give en kompileringsfejl.

Deklaration af array

Et array kan erklæres som:

 data_type name of the array[no of elements] 

For at erklære et array skal vi først angive typen af ​​arrayet og derefter arrayets navn. Inden for firkantede parenteser skal vi angive antallet af elementer, som vores array skal indeholde.

Lad os forstå gennem et eksempel.

 int a[5]; 

I ovenstående tilfælde har vi erklæret en matrix af 5 elementer med ' -en ' navn på en heltal datatype.

Hvad er linket liste?

En sammenkædet liste er samlingen af ​​noder, der er tilfældigt gemt. Hver node består af to felter, dvs. data og link . Her er data den værdi, der er gemt på den pågældende node, og linket er den markør, der holder adressen på den næste node.

Forskelle mellem Array og Linked list

Vi kan ikke sige, hvilken datastruktur der er bedre, dvs. array eller linket liste . Der kan være en mulighed for, at den ene datastruktur er bedre til én slags krav, mens den anden datastruktur er bedre til en anden form for krav. Der er forskellige faktorer som, hvad der er de hyppige operationer, der udføres på datastrukturen eller størrelsen af ​​dataene, og andre faktorer også på hvilket grundlag datastrukturen er valgt. Nu vil vi se nogle forskelle mellem arrayet og den sammenkædede liste baseret på nogle parametre.

1. Omkostninger ved adgang til et element

I tilfælde af et array, uanset størrelsen af ​​et array, tager et array en konstant tid for at få adgang til et element. I et array er elementerne gemt på en sammenhængende måde, så hvis vi kender grundadressen på elementet, så kan vi nemt få adressen på ethvert element i et array. Vi skal udføre en simpel beregning for at få adressen på ethvert element i et array. Så adgang til elementet i et array er O(1) med hensyn til tidskompleksitet.

I den linkede liste er elementerne ikke gemt på en sammenhængende måde. Den består af flere blokke, og hver blok er repræsenteret som en node. Hver knude har to felter, dvs. et er til datafeltet, og et andet gemmer adressen på den næste knude. For at finde en hvilken som helst knude på den sammenkædede liste, skal vi først bestemme den første knude kendt som hovedknuden. Hvis vi skal finde den anden knude på listen, så skal vi krydse fra den første knude, og i værste fald, for at finde den sidste knude, vil vi krydse alle knudepunkterne. Den gennemsnitlige sag for at få adgang til elementet er O(n).

Vi konkluderer, at omkostningerne ved at få adgang til et element i array er mindre end den linkede liste. Derfor, hvis vi har noget krav for at få adgang til elementerne, så er array et bedre valg.

2. Omkostninger ved indsættelse af et element

Der kan være tre scenarier i indsættelsen:

json i json eksempel

Indsættelse af elementet i begyndelsen:For at indsætte det nye element i begyndelsen, skal vi først flytte elementet mod højre for at skabe et mellemrum i den første position. Så tidskompleksiteten vil være proportional med listens størrelse. Hvis n er størrelsen af ​​arrayet, ville tidskompleksiteten være O(n).

I tilfælde af en linket liste, for at indsætte et element i starten af ​​den linkede liste, vil vi oprette en ny node, og adressen på den første node tilføjes til den nye node. På denne måde bliver den nye node den første node. Så tidskompleksiteten er ikke proportional med listens størrelse. Tidskompleksiteten ville være konstant, dvs. O(1).

Indsættelse af et element til sidst

Hvis arrayet ikke er fuldt, så kan vi direkte tilføje det nye element gennem indekset. I dette tilfælde ville tidskompleksiteten være konstant, dvs. O(1). Hvis arrayet er fyldt, skal vi først kopiere arrayet til et andet array og tilføje et nyt element. I dette tilfælde ville tidskompleksiteten være O(n).

For at indsætte et element i slutningen af ​​den linkede liste, skal vi gennemse hele listen. Hvis den sammenkædede liste består af n elementer, vil tidskompleksiteten være O(n).

Indsættelse af et element i midten

Antag, at vi vil indsætte elementet ved i^thpositionen af ​​arrayet; vi skal flytte n/2 elementerne mod højre. Derfor er tidskompleksiteten proportional med antallet af elementer. Tidskompleksiteten ville være O(n) for det gennemsnitlige tilfælde.

cpp er lig med

I tilfælde af sammenkædet liste, skal vi gå til den position, hvor vi skal indsætte det nye element. Selvom vi ikke skal udføre nogen form for skift, men vi skal krydse til n/2 position. Den tid, det tager, er proportional med antallet af n elementer, og tidskompleksiteten for den gennemsnitlige sag ville være O(n).

Den resulterende linkede liste er:

Brugervenlighed

Implementeringen af ​​et array er let sammenlignet med den linkede liste. Mens du opretter et program ved hjælp af en sammenkædet liste, er programmet mere tilbøjeligt til fejl som segmenteringsfejl eller hukommelseslækage. Så der skal udvises meget omhu, når du opretter et program på den linkede liste.

Dynamisk i størrelsen

Den sammenkædede liste er dynamisk i størrelse, mens arrayet er statisk. Her betyder statisk ikke, at vi ikke kan bestemme størrelsen på køretiden, men vi kan ikke ændre den, når først størrelsen er besluttet.

3. Hukommelseskrav

Da elementerne i et array lagrer i en sammenhængende hukommelsesblok, er arrayet af fast størrelse. Antag, at vi har et array med størrelse 7, og arrayet består af 4 elementer, så er resten af ​​rummet ubrugt. Hukommelsen optaget af de 7 elementer:

Hukommelsesplads = 7*4 = 28 bytes

Hvor 7 er antallet af elementer i en matrix, og 4 er antallet af bytes af en heltalstype.

I tilfælde af sammenkædet liste er der ingen ubrugt hukommelse, men den ekstra hukommelse er optaget af pointervariablerne. Hvis dataene er af heltalstypen, er den samlede hukommelse optaget af en knude 8 bytes, dvs. 4 bytes for data og 4 bytes for pointervariablen. Hvis den sammenkædede liste består af 4 elementer, vil hukommelsespladsen, der optages af den sammenkædede liste, være:

webdriver

Hukommelsesplads = 8*4 = 32 bytes

Den sammenkædede liste ville være et bedre valg, hvis datadelen er større i størrelse. Antag, at dataene er på 16 bytes. Hukommelsespladsen optaget af arrayet ville være 16*7=112 bytes, mens den linkede liste optager 20*4=80, her har vi specificeret 20 bytes som 16 bytes for størrelsen af ​​dataene plus 4 bytes for pointervariablen. Hvis vi vælger den større størrelse af data, vil den sammenkædede liste forbruge mindre hukommelse; ellers afhænger det af de faktorer, vi anvender til at bestemme størrelsen.

Lad os se på forskellene mellem matrixen og den linkede liste i en tabelform.