Gekoppelde lijstgegevensstructuur in C ++ met illustratie

linked list data structure c with illustration

Een gedetailleerde studie van gekoppelde lijst in C ++.

Een gekoppelde lijst is een lineaire dynamische gegevensstructuur om gegevensitems op te slaan. We hebben al arrays gezien in onze vorige onderwerpen over basis C ++. We weten ook dat arrays een lineaire gegevensstructuur zijn die gegevensitems op aaneengesloten locaties opslaan.

In tegenstelling tot arrays, slaat de gekoppelde lijst geen gegevensitems op aaneengesloten geheugenlocaties op.

Een gekoppelde lijst bestaat uit items genaamd 'Nodes' die uit twee delen bestaan. Het eerste deel slaat de feitelijke gegevens op en het tweede deel heeft een aanwijzer die naar het volgende knooppunt wijst. Deze structuur wordt gewoonlijk 'Singly linked list' genoemd.

​ Bekijk hier de beste C ++ trainingshandleidingen.

Wat je leert:

• Gekoppelde lijst in C ++
  • Operaties
    • # 1) Invoegen
    • # 2) Verwijderen
  • Tel het aantal knooppunten
  • Arrays en gekoppelde lijsten
  • Toepassingen
  • Gevolgtrekking
  • Aanbevolen literatuur

Gekoppelde lijst in C ++

In deze tutorial zullen we de enkelvoudig gelinkte lijst in detail bekijken.

Het volgende diagram toont de structuur van een enkelvoudig gelinkte lijst.

Zoals hierboven getoond, wordt het eerste knooppunt van de gekoppelde lijst 'head' genoemd en het laatste knooppunt 'Tail'. Zoals we zien, zal het laatste knooppunt van de gekoppelde lijst zijn volgende pointer als null hebben, aangezien er geen geheugenadres naar zal verwijzen.

Aangezien elk knooppunt een pointer naar het volgende knooppunt heeft, hoeven gegevensitems in de gekoppelde lijst niet op aangrenzende locaties te worden opgeslagen. De knooppunten kunnen in het geheugen worden verspreid. We hebben op elk moment toegang tot de knooppunten, omdat elk knooppunt een adres heeft van het volgende knooppunt.

We kunnen gegevensitems aan de gekoppelde lijst toevoegen en items gemakkelijk uit de lijst verwijderen. Zo is het mogelijk om de gekoppelde lijst dynamisch te vergroten of te verkleinen. Er is geen bovengrens voor het aantal gegevensitems dat in de gekoppelde lijst kan staan. Dus zolang er geheugen beschikbaar is, kunnen we zoveel gegevensitems aan de gekoppelde lijst toevoegen.

Afgezien van het eenvoudig invoegen en verwijderen, verspilt de gelinkte lijst ook geen geheugenruimte omdat we niet van tevoren hoeven aan te geven hoeveel items we nodig hebben in de gelinkte lijst. De enige ruimte die door de gekoppelde lijst wordt ingenomen, is voor het opslaan van de aanwijzer naar het volgende knooppunt dat een beetje overhead toevoegt.

Vervolgens bespreken we de verschillende bewerkingen die kunnen worden uitgevoerd op een gekoppelde lijst.

Operaties

Net als bij de andere datastructuren kunnen we ook voor de gekoppelde lijst verschillende bewerkingen uitvoeren. Maar in tegenstelling tot arrays, waarin we rechtstreeks toegang hebben tot het element met behulp van subscript, zelfs als het zich ergens tussenin bevindt, kunnen we niet dezelfde willekeurige toegang doen met een gekoppelde lijst.

Om toegang te krijgen tot een knooppunt, moeten we de gekoppelde lijst vanaf het begin doorlopen en alleen dan hebben we toegang tot het gewenste knooppunt. Vandaar dat het willekeurig toegang krijgen tot de gegevens uit de gekoppelde lijst duur blijkt te zijn.

We kunnen verschillende bewerkingen uitvoeren op een gekoppelde lijst, zoals hieronder weergegeven:

# 1) Invoegen

Invoegbewerking van gekoppelde lijst voegt een item toe aan de gekoppelde lijst. Hoewel het misschien eenvoudig klinkt, gezien de structuur van de gekoppelde lijst, weten we dat wanneer een gegevensitem aan de gekoppelde lijst wordt toegevoegd, we de volgende verwijzingen naar de vorige en volgende knooppunten van het nieuwe item dat we hebben ingevoegd, moeten wijzigen.

Het tweede dat we moeten overwegen, is de plaats waar het nieuwe gegevensitem moet worden toegevoegd.

c ++ vragen en antwoorden

Er zijn drie posities in de gekoppelde lijst waar een data-item kan worden toegevoegd.

# 1) Aan het begin van de gekoppelde lijst

Een gekoppelde lijst wordt hieronder getoond 2-> 4-> 6-> 8-> 10. Als we een nieuw knooppunt 1 willen toevoegen, als het eerste knooppunt van de lijst, dan zal de kop die naar knooppunt 2 wijst nu naar 1 wijzen en zal de volgende aanwijzer van knooppunt 1 het geheugenadres van knooppunt 2 hebben zoals hieronder getoond figuur.

De nieuwe gekoppelde lijst wordt dus 1-> 2-> 4-> 6-> 8-> 10.

# 2) Na het opgegeven knooppunt

Hier wordt een knooppunt gegeven en moeten we een nieuw knooppunt toevoegen na het gegeven knooppunt. In de onderstaande gekoppelde lijst a-> b-> c-> d -> e, als we een knoop f willen toevoegen na knoop c, dan ziet de gekoppelde lijst er als volgt uit:

Dus in het bovenstaande diagram controleren we of het gegeven knooppunt aanwezig is. Als het aanwezig is, maken we een nieuw knooppunt f. Vervolgens wijzen we de volgende wijzer van knooppunt c om naar het nieuwe knooppunt f te wijzen. De volgende wijzer van het knooppunt f wijst nu naar knooppunt d.

# 3) Aan het einde van de gekoppelde lijst

In het derde geval voegen we een nieuw knooppunt toe aan het einde van de gekoppelde lijst. Stel dat we dezelfde gekoppelde lijst a-> b-> c-> d-> e hebben en dat we een knoop f aan het einde van de lijst moeten toevoegen. De gekoppelde lijst ziet er uit zoals hieronder weergegeven na het toevoegen van het knooppunt.

Zo maken we een nieuw knooppunt f. Dan wordt de staartwijzer die naar nul wijst naar f gericht en de volgende wijzer van knooppunt f wordt naar nul verwezen. We hebben alle drie de typen invoegfuncties geïmplementeerd in het onderstaande C ++ -programma.

In C ++ kunnen we een gekoppelde lijst declareren als een structuur of als een klasse. Het declareren van een gekoppelde lijst als een structuur is een traditionele C-stijl declaratie. Een gekoppelde lijst als klasse wordt gebruikt in moderne C ++, meestal tijdens het gebruik van de standaard sjabloonbibliotheek.

In het volgende programma hebben we structuur gebruikt om een ​​gekoppelde lijst te declareren en te creëren. Het heeft gegevens en een verwijzing naar het volgende element als leden.

Uitgang:

Laatste gekoppelde lijst:

30–> 20–> 50–> 10–> 40–> null

Vervolgens implementeren we de bewerking voor het invoegen van gekoppelde lijsten in Java. In Java-taal wordt de gekoppelde lijst geïmplementeerd als een klasse. Het onderstaande programma lijkt qua logica op het C ++ -programma, het enige verschil is dat we een klasse gebruiken voor de gekoppelde lijst.

Uitgang:

Laatste gekoppelde lijst:

10–> 20–> 30–> 40–> 50–> null

In zowel het programma hierboven, C ++ als Java, hebben we aparte functies om een ​​knooppunt toe te voegen vóór de lijst, aan het einde van de lijst en tussen de lijsten die in een knooppunt zijn gegeven. Uiteindelijk printen we de inhoud van de lijst die is gemaakt met behulp van alle drie de methoden.

hoe je een eenvoudige binaire zoekboom implementeert in java

# 2) Verwijderen

Net als bij invoegen, omvat het verwijderen van een knooppunt uit een gekoppelde lijst ook verschillende posities van waaruit het knooppunt kan worden verwijderd. We kunnen het eerste knooppunt, het laatste knooppunt of een willekeurig kth-knooppunt verwijderen uit de gekoppelde lijst. Na verwijdering moeten we de volgende aanwijzer en de andere verwijzingen in de gekoppelde lijst op de juiste manier aanpassen om de gekoppelde lijst intact te houden.

In de volgende C ++ -implementatie hebben we twee verwijderingsmethoden gegeven, d.w.z. het eerste knooppunt in de lijst verwijderen en het laatste knooppunt in de lijst verwijderen. We maken eerst een lijst door knooppunten aan het hoofd toe te voegen. Vervolgens tonen we de inhoud van de lijst na het invoegen en elke verwijdering.

Uitgang:

Gekoppelde lijst gemaakt

10–> 8–> 6–> 4–> 2–
> NULL

Gekoppelde lijst na het verwijderen van het hoofdknooppunt

8–> 6–> 4–> 2–
> NULL

Gekoppelde lijst na het verwijderen van het laatste knooppunt

8–> 6–> 4–> NULL

De volgende is de Java-implementatie voor het verwijderen van knooppunten uit de gekoppelde lijst. De implementatielogica is dezelfde als die wordt gebruikt in het C ++ - programma. Het enige verschil is dat de gekoppelde lijst als klasse wordt gedeclareerd.

Uitgang:

Gekoppelde lijst gemaakt:

9–> 7–> 5–> 3–> 1–
> null

Gekoppelde lijst na het verwijderen van het hoofdknooppunt:

7–> 5–> 3–> 1–
> null

Gekoppelde lijst na het verwijderen van het laatste knooppunt:

7–> 5–> 3–> null

Tel het aantal knooppunten

De bewerking om het aantal knooppunten te tellen kan worden uitgevoerd tijdens het doorlopen van de gekoppelde lijst. We hebben in de bovenstaande implementatie al gezien dat wanneer we een knooppunt moeten invoegen / verwijderen of de inhoud van de gekoppelde lijst moeten weergeven, we de gekoppelde lijst vanaf het begin moeten doorlopen.

Als we een teller bijhouden en deze verhogen terwijl we elk knooppunt passeren, krijgen we het aantal knooppunten dat aanwezig is in de gekoppelde lijst. We laten dit programma over aan de lezers om te implementeren.

Arrays en gekoppelde lijsten

Laten we, nadat we de bewerkingen en implementatie van de gekoppelde lijst hebben gezien, vergelijken hoe arrays en gekoppelde lijst eerlijk zijn in vergelijking met elkaar.

Toepassingen

Aangezien arrays en gekoppelde lijsten beide worden gebruikt om items op te slaan en lineaire gegevensstructuren zijn, kunnen beide structuren op vergelijkbare manieren worden gebruikt voor de meeste toepassingen.

Enkele van de toepassingen voor gekoppelde lijsten zijn als volgt:

• Een gekoppelde lijst kan worden gebruikt om stapels en wachtrijen te implementeren.
• Een gekoppelde lijst kan ook worden gebruikt om grafieken te implementeren wanneer we grafieken moeten weergeven als aangrenzende lijsten.
• Een wiskundig polynoom kan worden opgeslagen als een gekoppelde lijst.
• In het geval van hash-techniek worden de buckets die bij hashing worden gebruikt, geïmplementeerd met behulp van de gekoppelde lijsten.
• Wanneer een programma dynamische toewijzing van geheugen vereist, kunnen we een gekoppelde lijst gebruiken, omdat gekoppelde lijsten in dit geval efficiënter werken.

Gevolgtrekking

Gekoppelde lijsten zijn de gegevensstructuren die worden gebruikt om gegevensitems op een lineaire maar niet-aaneengesloten locaties op te slaan. Een gekoppelde lijst is een verzameling knooppunten die een gegevensdeel bevatten en een volgende aanwijzer die het geheugenadres van het volgende element in de lijst bevat.

Voor het laatste element in de lijst is de volgende pointer ingesteld op NULL, waarmee het einde van de lijst wordt aangegeven. Het eerste element van de lijst wordt het hoofd genoemd. De gekoppelde lijst ondersteunt verschillende bewerkingen zoals invoegen, verwijderen, doorlopen, enz. In het geval van dynamische geheugentoewijzing hebben gekoppelde lijsten de voorkeur boven arrays.

Gelinkte lijsten zijn duur wat betreft hun verplaatsing, omdat we niet willekeurig toegang kunnen krijgen tot de elementen zoals arrays. Invoegbewerkingen zijn echter minder duur in vergelijking met arrays.

In deze tutorial hebben we alles geleerd over lineair gelinkte lijsten. Gekoppelde lijsten kunnen ook circulair of dubbel zijn. We zullen deze lijsten grondig bekijken in onze komende tutorials.

​ Kijk hier voor de complete C ++ trainingsserie.

Aanbevolen literatuur

• Circulaire gekoppelde lijstgegevensstructuur in C ++ met illustratie
• Dubbel gekoppelde lijstgegevensstructuur in C ++ met illustratie
• Wachtrijgegevensstructuur in C ++ met illustratie
• Stapel gegevensstructuur in C ++ met illustratie
• Prioritaire wachtrijgegevensstructuur in C ++ met illustratie
• Top 15 beste gratis tools voor datamining: de meest uitgebreide lijst
• 15 beste ETL-tools in 2021 (een complete bijgewerkte lijst)
• Inleiding tot gegevensstructuren in C ++