Verschil tussen matrixlijst en gekoppelde lijst Verschil tussen
Hoe worden gegevens bewaard?
Arraylijst en gekoppelde lijst zijn algemene termen als het gaat om gegevensopslag en het ophalen. Hoewel er veel opslagapparaten zijn, zijn ze uiteindelijk afhankelijk van het opslagmechanisme. Deze twee opslagmechanismen plaatsen uw gegevens in de opslagapparaten en halen ze op wanneer dat nodig is. Laten we eens kijken hoe ze gegevens in hun geheugen opslaan. De Array-lijst gebruikt een sequentiële opslag en de stukjes data worden na elkaar opgeslagen. Dit is misschien een eenvoudiger vorm van opslag - het voorkomt verwarring. Ja, we kunnen het volgende item of de volgende gegevens ophalen van de volgende geheugenlocatie van de arraylijst; het wordt echter opgeslagen met behulp van aanwijzers in de gekoppelde lijst. Hier hebben we twee geheugenlocaties nodig voor opslag - één voor de gegevens, de andere voor de aanwijzer. Een pointer adresseert de geheugenlocatie van de volgende gegevens. We kunnen gemakkelijk begrijpen dat gekoppelde lijst nooit gegevens opeenvolgend opslaat; in plaats daarvan gebruikt het een willekeurig opslagmechanisme. De wijzers zijn de belangrijkste elementen bij het lokaliseren van de datalocaties in het geheugen.
Dynamische matrix en gekoppelde lijst
We hebben al besproken hoe beide opslagmechanismen gegevens invoeren en we kunnen een term 'dynamische array' geven voor het interne opslagschema van de arraylijst. Het plaatst gewoon de datastukken een voor een - vandaar de naam - terwijl de gekoppelde lijst een interne lijst gebruikt met behulp van pointers om het volgende item te volgen. Daarom gebruikt het een interne gekoppelde lijst, zoals een enkelvoudige of dubbel gekoppelde lijst om ons de volgende gegevens te tonen.
Geheugengebruik
Omdat de Arraylijst alleen de werkelijke gegevens opslaat, hebben we alleen ruimte nodig voor de gegevens die we opslaan. Omgekeerd gebruiken we in de gekoppelde lijst ook verwijzingen. Daarom zijn twee geheugenlocaties vereist en we kunnen zeggen dat gekoppelde lijst meer geheugen gebruikt dan de Array-lijst. Een voordelige kant van gekoppelde lijst is dat er nooit continue geheugenlocaties nodig zijn om onze gegevens op te slaan, in tegenstelling tot de Array-lijst. De wijzers kunnen de positie van de volgende gegevenslocatie vasthouden en we kunnen zelfs kleinere geheugenslots gebruiken die niet continu zijn. Als het op geheugengebruik aankomt, spelen aanwijzers de hoofdrol in de gekoppelde lijst, en dat geldt ook voor de effectiviteit ervan.
Grootte van oorspronkelijke arraylijst en gekoppelde lijst
Met de arraylijst heeft zelfs een lege lijst een grootte van 10, maar met een gekoppelde lijst hebben we zo'n enorme ruimte niet nodig. We kunnen een lege gekoppelde lijst maken met een grootte van 0. Later kunnen we de grootte naar behoefte vergroten.
Data Retrieval
Het ophalen van gegevens is eenvoudiger in de Array-lijst als deze opeenvolgend wordt opgeslagen. Het enige dat het doet is de eerste gegevenslocatie identificeren; vanaf daar is de volgende locatie sequentieel toegankelijk om de rest op te halen.Het wordt berekend als de eerste gegevenspositie + 'n', waarbij 'n' de volgorde is van de gegevens in de lijst Array. De gekoppelde lijst verwijst naar de eerste aanwijzer om de eerste gegevenslocatie te vinden en van daaruit verwijst de aanwijzer naar elke gegevens om de volgende gegevenslocatie te vinden. Het ophaalproces is hier voornamelijk afhankelijk van de pointers en ze tonen ons effectief de volgende datalocatie.
Einde gegevens
De matrixlijst gebruikt een nulwaarde om het einde van de gegevens te markeren, terwijl de gekoppelde lijst hiervoor een lege aanwijzer gebruikt. Zodra het systeem null-gegevens herkent, stopt de Array-lijst met het ophalen van de volgende gegevens. Op een vergelijkbare manier stopt de nul-aanwijzer het systeem om door te gaan naar de volgende gegevensherstel.
Omgekeerd Traversal
De gekoppelde lijst stelt ons in staat om in omgekeerde richting te reizen met behulp van descendingiterator (). We hebben echter niet zo'n faciliteit in een Array-lijst - omgekeerde traversal wordt hier een probleem.
Syntaxis
Laten we de Java-syntax van beide opslagmechanismen bekijken.
Arraylijst maken:
Lijstarraylistsample = new ArrayList ();
Objecten toevoegen aan de lijst met arrays:
Arraylistsample. toe te voegen (“name1”);
Arraylistsample. toe te voegen (“name2”);
Zo ziet de resulterende matrixlijst er uit: [naam1, naam2].
Maken van gekoppelde lijsten:
Lijst linkedlistsample = nieuwe linkedList ();
Objecten toevoegen aan de gekoppelde lijst:
Linkedlistvoorbeeld. toe te voegen (“NAME3”);
Linkedlistsample. toe te voegen (“NAME4”);
Dit is hoe de resulterende gekoppelde lijst eruit zal zien - [naam3, naam4].
Wat is beter voor de zoek- of zoekbewerking?
De arraylijst neemt O (1) de tijd om gegevens te doorzoeken, terwijl de gekoppelde lijst u O (n) voor het zoeken naar gegevens n th gebruikt. Daarom gebruikt een matrixlijst altijd een constante tijd voor het zoeken naar gegevens, maar in de lijst Gekoppeld hangt de tijd af van de positie van de gegevens. Daarom zijn matrixlijsten altijd een betere keuze voor bewerkingen voor zoeken of zoeken.
Wat is beter voor de invoeg- of optelbewerking?
Zowel de matrixlijst als de gekoppelde lijst nemen O (1) tijd voor het toevoegen van gegevens. Maar als de array vol is, kost het een aanzienlijke hoeveelheid tijd om de array-lijst te wijzigen en de items naar de nieuwere te kopiëren. In een dergelijk geval is de gekoppelde lijst de betere keuze.
Wat is beter voor de verwijderingsbewerking?
Het verwijderen duurt bijna even lang in zowel de lijst Array als de lijst Gekoppeld. In de lijst Array worden met deze bewerking de gegevens verwijderd en wordt de positie van de gegevens verschoven naar de nieuwere array - deze duurt O (n). In de lijst Gekoppeld doorloopt deze bewerking de betreffende gegevens en wijzigt de aanwijzerpositie om de nieuwere lijst te vormen. De tijd voor het traversaal en de verwijdering is hier ook O (n).
Welke is sneller?
We weten dat een matrixlijst een interne array gebruikt om de feitelijke gegevens op te slaan. Daarom, als gegevens worden verwijderd, hebben alle aankomende gegevens een geheugenverschuiving nodig.Uiteraard vereist dit een aanzienlijke hoeveelheid tijd en vertraagt het de situatie. Zo'n geheugenverschuiving is niet vereist in de gekoppelde lijst, omdat het alleen de locatie van de aanwijzer verandert. Daarom is een gelinkte lijst sneller dan een matrixlijst in elke vorm van gegevensopslag. Dit is echter puur afhankelijk van het type operatie, i. e. Voor de bewerking Get of Zoeken kost de gekoppelde lijst veel meer tijd dan een Array-lijst. Wanneer we kijken naar de algehele prestaties, kunnen we zeggen dat de gekoppelde lijst sneller is.
Wanneer een matrixlijst en een gekoppelde lijst gebruiken?
Een arraylijst is het meest geschikt voor kleinere gegevensvereisten waarbij continu geheugen beschikbaar is. Maar wanneer we omgaan met enorme hoeveelheden gegevens, implementeert de beschikbaarheid van continu geheugen de mechanismen voor gegevensopslag, of deze nu klein of groot zijn. Bepaal vervolgens welke u moet kiezen: de Array-lijst of de gekoppelde lijst. U kunt doorgaan met een arraylijst als u alleen opslag en het ophalen van gegevens nodig heeft. Maar een lijst kan u verder helpen door gegevens te manipuleren. Zodra u beslist hoe vaak gegevensmanipulatie nodig is, is het belangrijk om te controleren welk type gegevensherstel u gewoonlijk uitvoert. Wanneer het alleen maar Get of Search is, dan is de Array-lijst de betere keuze; voor andere bewerkingen zoals invoegen of verwijderen, ga je gang met de gekoppelde lijst.
Laten we de verschillen in tabelvorm bekijken.
