Array En Gekoppelde lijst zijn de twee manieren om de gegevens in het geheugen te organiseren. Voordat u de verschillen tussen de Array en de Gekoppelde lijst , wij kijken eerst bij een array En een gekoppelde lijst .
overerving in c++
Wat is een array?
Een gegevensstructuur die de elementen van hetzelfde type bevat. Een datastructuur is een manier om de gegevens te organiseren; een array is een datastructuur omdat deze de gegevens opeenvolgend ordent. Een array is een groot stuk geheugen waarin het geheugen is verdeeld in kleine en kleine blokken, en elk blok kan een bepaalde waarde opslaan.
Stel dat we een array hebben gemaakt die uit 10 waarden bestaat, dan zal elk blok de waarde van een geheel getal opslaan. Als we proberen de waarde in een array van verschillende typen op te slaan, is het geen correcte array en ontstaat er een compileerfout.
Verklaring van array
Een array kan worden gedeclareerd als:
data_type name of the array[no of elements]
Om een array te declareren, moeten we eerst het type array opgeven en vervolgens de naam van de array. Binnen de vierkante haakjes moeten we het aantal elementen specificeren dat onze array moet bevatten.
Laten we het begrijpen aan de hand van een voorbeeld.
int a[5];
In het bovenstaande geval hebben we een array van 5 elementen gedeclareerd met ' A ' naam van een geheel getal data type.
Wat is een gekoppelde lijst?
Een gekoppelde lijst is de verzameling knooppunten die willekeurig worden opgeslagen. Elk knooppunt bestaat uit twee velden, d.w.z. gegevens En koppeling . Hier zijn gegevens de waarde die is opgeslagen op dat specifieke knooppunt, en de link is de aanwijzer die het adres van het volgende knooppunt bevat.
Verschillen tussen array en gekoppelde lijst
We kunnen niet zeggen welke datastructuur beter is, dat wil zeggen array of gekoppelde lijst . Het kan mogelijk zijn dat de ene datastructuur beter is voor één soort vereiste, terwijl de andere datastructuur beter is voor een ander soort vereiste. Er zijn verschillende factoren, zoals de frequente bewerkingen die op de datastructuur worden uitgevoerd of de grootte van de data, en ook andere factoren op basis waarvan de datastructuur wordt geselecteerd. Nu zullen we enkele verschillen zien tussen de array en de gekoppelde lijst op basis van enkele parameters.
1. Kosten voor toegang tot een element
In het geval van een array heeft een array, ongeacht de grootte van een array, een constante tijd nodig om toegang te krijgen tot een element. In een array worden de elementen op een aaneengesloten manier opgeslagen, dus als we het basisadres van het element kennen, kunnen we gemakkelijk het adres van elk element in een array achterhalen. We moeten een eenvoudige berekening uitvoeren om het adres van elk element in een array te verkrijgen. Dus toegang tot het element in een array is dat wel O(1) in termen van tijdscomplexiteit.
In de gekoppelde lijst worden de elementen niet aaneengesloten opgeslagen. Het bestaat uit meerdere blokken en elk blok wordt weergegeven als een knooppunt. Elk knooppunt heeft twee velden, d.w.z. één is voor het gegevensveld en een ander bevat het adres van het volgende knooppunt. Om een knooppunt in de gekoppelde lijst te vinden, moeten we eerst het eerste knooppunt bepalen dat bekend staat als het hoofdknooppunt. Als we het tweede knooppunt in de lijst moeten vinden, moeten we vanaf het eerste knooppunt doorlopen, en in het ergste geval, om het laatste knooppunt te vinden, moeten we alle knooppunten doorkruisen. Het gemiddelde geval voor toegang tot het element is O(n).
tekenreeks concat java
We concluderen dat de kosten voor toegang tot een element in de array lager zijn dan die van de gekoppelde lijst. Daarom, als we enige vereiste hebben voor toegang tot de elementen, is array een betere keuze.
2. Kosten voor het invoegen van een element
Er kunnen drie scenario's zijn bij het invoegen:
Als we in het geval van een gekoppelde lijst een element aan het begin van de gekoppelde lijst willen invoegen, maken we een nieuw knooppunt aan en wordt het adres van het eerste knooppunt aan het nieuwe knooppunt toegevoegd. Op deze manier wordt het nieuwe knooppunt het eerste knooppunt. De tijdscomplexiteit is dus niet evenredig aan de omvang van de lijst. De tijdscomplexiteit zou constant zijn, dat wil zeggen O(1).
Als de array niet vol is, kunnen we het nieuwe element rechtstreeks via de index toevoegen. In dit geval zou de tijdscomplexiteit constant zijn, dat wil zeggen O(1). Als de array vol is, moeten we eerst de array naar een andere array kopiëren en een nieuw element toevoegen. In dit geval zou de tijdscomplexiteit O(n) zijn.
Om een element aan het einde van de gekoppelde lijst in te voegen, moeten we de hele lijst doorkruisen. Als de gekoppelde lijst uit n elementen bestaat, zou de tijdscomplexiteit O(n) zijn.
Stel dat we het element op de i willen invoegenepositie van de array; we moeten de n/2 elementen naar rechts verschuiven. Daarom is de tijdscomplexiteit evenredig met het aantal elementen. De tijdscomplexiteit zou O(n) zijn voor het gemiddelde geval.
centos versus rhel
In het geval van een gekoppelde lijst moeten we naar die positie gaan waar we het nieuwe element moeten invoegen. Ook al hoeven we geen enkele verschuiving uit te voeren, maar moeten we naar positie n/2 gaan. De benodigde tijd is evenredig met het n aantal elementen, en de tijdscomplexiteit voor het gemiddelde geval zou O(n) zijn.
De resulterende gekoppelde lijst is:
De implementatie van een array is eenvoudig in vergelijking met de gekoppelde lijst. Bij het maken van een programma met behulp van een gekoppelde lijst is het programma gevoeliger voor fouten zoals segmentatiefouten of geheugenlekken. Er moet dus veel zorg worden besteed aan het maken van een programma in de gekoppelde lijst.
De gekoppelde lijst is dynamisch van formaat, terwijl de array statisch is. Statisch betekent hier niet dat we de grootte niet tijdens de uitvoering kunnen bepalen, maar we kunnen deze niet wijzigen zodra de grootte is bepaald.
3. Geheugenvereisten
Omdat de elementen in een array in één aaneengesloten geheugenblok worden opgeslagen, heeft de array een vaste grootte. Stel dat we een array van maat 7 hebben, en de array bestaat uit 4 elementen, dan is de rest van de ruimte ongebruikt. Het geheugen dat wordt ingenomen door de 7 elementen:
Geheugenruimte = 7*4 = 28 bytes
Waarbij 7 het aantal elementen in een array is en 4 het aantal bytes van het type geheel getal.
In het geval van een gekoppelde lijst is er geen ongebruikt geheugen, maar wordt het extra geheugen ingenomen door de pointervariabelen. Als de gegevens van het integer-type zijn, bedraagt het totale geheugen dat door één knooppunt wordt ingenomen 8 bytes, dat wil zeggen 4 bytes voor gegevens en 4 bytes voor pointervariabelen. Als de gekoppelde lijst uit 4 elementen bestaat, zou de geheugenruimte die door de gekoppelde lijst wordt ingenomen:
webstuurprogramma
Geheugenruimte = 8*4 = 32 bytes
De gekoppelde lijst zou een betere keuze zijn als het gegevensgedeelte groter is. Stel dat de gegevens 16 bytes groot zijn. De geheugenruimte die door de array wordt ingenomen, zou 16*7=112 bytes zijn, terwijl de gekoppelde lijst 20*4=80 in beslag neemt. Hier hebben we 20 bytes gespecificeerd als 16 bytes voor de grootte van de gegevens plus 4 bytes voor de pointervariabele. Als we de grotere gegevensomvang kiezen, zou de gekoppelde lijst minder geheugen in beslag nemen; anders hangt het af van de factoren die we gebruiken om de maat te bepalen.
Laten we de verschillen tussen de array en de gekoppelde lijst in tabelvorm bekijken.
| Array | Gekoppelde lijst |
|---|---|
| Een array is een verzameling elementen van een vergelijkbaar gegevenstype. | Een gekoppelde lijst is een verzameling objecten die bekend staat als een knooppunt, waarbij het knooppunt uit twee delen bestaat, namelijk gegevens en adres. |
| Array-elementen worden opgeslagen op een aaneengesloten geheugenlocatie. | Gekoppelde lijstelementen kunnen overal in het geheugen worden opgeslagen of willekeurig worden opgeslagen. |
| Array werkt met een statisch geheugen. Statisch geheugen betekent hier dat de geheugengrootte vast is en tijdens de uitvoering niet kan worden gewijzigd. | De gekoppelde lijst werkt met dynamisch geheugen. Dynamisch geheugen betekent hier dat de geheugengrootte tijdens de runtime kan worden gewijzigd volgens onze vereisten. |
| Array-elementen zijn onafhankelijk van elkaar. | Gekoppelde lijstelementen zijn van elkaar afhankelijk. Omdat elk knooppunt het adres van het volgende knooppunt bevat, moeten we, om toegang te krijgen tot het volgende knooppunt, toegang krijgen tot het vorige knooppunt. |
| Array kost meer tijd bij het uitvoeren van bewerkingen zoals invoegen, verwijderen, enz. | Gekoppelde lijst kost minder tijd bij het uitvoeren van bewerkingen zoals invoegen, verwijderen, enz. |
| Toegang tot elk element in een array gaat sneller omdat het element in een array rechtstreeks toegankelijk is via de index. | Toegang krijgen tot een element in een gekoppelde lijst gaat langzamer omdat het begint met het doorlopen van het eerste element van de gekoppelde lijst. |
| In het geval van een array wordt geheugen toegewezen tijdens het compileren. | In het geval van een gekoppelde lijst wordt tijdens runtime geheugen toegewezen. |
| Het geheugengebruik in de array is inefficiënt. Als de grootte van de array bijvoorbeeld 6 is en de array uit slechts 3 elementen bestaat, zal de rest van de ruimte ongebruikt zijn. | Het geheugengebruik is efficiënt in het geval van een gekoppelde lijst, omdat het geheugen tijdens de runtime kan worden toegewezen of ongedaan gemaakt, afhankelijk van onze vereisten. |