Tutorial met gekoppelde lijst: – Aan de slag met dynamische gegevensopslag

Openbaarmaking: Uw steun helpt de site draaiende te houden! We verdienen een verwijzingsvergoeding voor sommige van de services die we op deze pagina aanbevelen.


Gekoppelde lijsten kunnen een waardevol hulpmiddel zijn bij het structureren van verschillende datasets en het organiseren van lineaire informatie voor een programma. Ze worden vaak gebruikt als vervanging voor een array omdat ze bepaalde voordelen hebben bij het gebruik ervan.

In de kern is een gekoppelde lijst een eenvoudige gegevensstructuur met een reeks knooppunten. Elk knooppunt heeft zijn eigen gegevens, plus een aanwijzer naar een ander knooppunt. Ze worden zelfs vaak gegeven om studenten vertrouwd te maken met aanwijzers.

Hieronder leert u wat gekoppelde lijsten zijn, waarom ze waardevol zijn en hoe u ze kunt maken. We bieden ook een paar extra bronnen om je opleiding te bevorderen.

Wat zijn gekoppelde lijsten?

Simpel gezegd, een gekoppelde lijst is een geordende verzameling gegevens. Het is bedoeld voor lineaire gegevensstructuren en is een van de gemakkelijkste dynamische gegevensstructuren om te implementeren. Elk gegevenselement wordt een knooppunt genoemd en bevat een enkele waarde en een aanwijzer naar het volgende knooppunt in de lijst. Als de aanwijzer een NULL-waarde heeft, is dat knooppunt het laatste in de lijst.

Om het concept te begrijpen, is hier een voorbeeld buiten computertechnologie:

Stel dat u elke persoon in een kantoor beoordeelt op typsnelheid. Je lijst zou beginnen met Ann omdat iedereen weet dat ze de snelste is – je kunt het geluid uit haar kast horen. Ze is verteld dat de volgende snelste persoon Steve is. Steve weet dat zijn typsnelheid dicht bij die van Ann ligt, maar niet zo goed. Hij weet ook dat Karen bijna net zo snel is als hij, maar niet helemaal. De lijst kan dan op deze manier doorgaan. Elk lid beschikt over unieke informatie, plus een indicator voor wie de volgende snelste typist is.

Omdat knooppunten onafhankelijk van elkaar bestaan, behalve door de aanwijzerrelatie, is het heel eenvoudig om ze toe te voegen, te verwijderen en te verplaatsen.

Soorten gekoppelde lijsten

Er zijn een paar verschillende soorten gekoppelde lijsten. Een enkele gekoppelde lijst, een dubbel gekoppelde lijst, een meerkoppige lijst en een circulaire gekoppelde lijst. We verkennen ze hieronder allemaal in meer detail. Met gekoppelde lijsten kunt u invoeg-, verwijderings- en verplaatsingsbewerkingen uitvoeren.

1. Enkele gekoppelde lijst

Een enkele gekoppelde lijst is een verzameling gegevensobjecten die met elkaar zijn verbonden door bepaalde verwijzingen van het ene naar het andere object. Deze objecten worden vaak knooppunten genoemd. Elk knooppunt bevat ten minste één gegevensveld en een verwijzing naar het volgende knooppunt. Enkelvoudige gekoppelde lijsten zijn toegankelijk via het eerste knooppunt en kunnen worden doorlopen tot het einde van de lijst.

2. Dubbel gekoppelde lijst

Dubbel gekoppelde lijsten hebben twee referenties per knooppunt. De verwijzingen wijzen naar het volgende knooppunt en het vorige knooppunt. Met deze structuur heb je in twee richtingen toegang tot de dataset en het biedt je meer flexibiliteit en snelheid, omdat je door je lijst in beide richtingen kunt navigeren.

3. Lijst met meerdere links

Multilinked-lijsten zijn algemene gekoppelde lijsten met meerdere aanvullende lijsten van een bepaald knooppunt. De nieuwe lijsten kunnen in elk van de hier genoemde stijlen voorkomen. Deze lijststijl kan handig zijn om een ​​lijst te sorteren die is onderverdeeld op naam en leeftijd van de gebruiker. Of andere datasets, waarbij elk datapunt verdere classificaties heeft.

4. Circulaire gekoppelde lijst

Het laatste type gekoppelde lijst wordt een circulaire gekoppelde lijst genoemd. In plaats van dat het laatste knooppunt een NULL-opdracht heeft, verwijst het terug naar de kop van de lijst. De structuur van de lijst is vergelijkbaar met de bovenstaande opties.

Waarom gekoppelde lijsten belangrijk zijn

Gelinkte lijsten zijn nuttig vanwege hun dynamische karakter. In rekenkundige zin wijst het alleen geheugen toe wanneer dat nodig is. Dus als u een toepassing heeft die regelmatig moet worden aangepast, verwijderd, ingevoegd en gegevensupdates nodig hebben, dan is een gekoppelde lijst perfect.

Gekoppelde lijsten worden vaak gebruikt om grafieken, stapels, wachtrijen en andere soortgelijke programma’s te implementeren. Met een gekoppelde lijst kunt u items overal in de lijst invoegen. Bovendien hoeft u niet van tevoren de grootte van de definitieve lijst te weten. Het kan naar eigen inzicht groter of kleiner worden.

Het eenvoudig invoegen en verwijderen is een groot voordeel voor gekoppelde lijsten. U kunt bijvoorbeeld een array gebruiken, maar met arrays kunt u alleen het laatste object in de reeks toevoegen en verwijderen zonder een heleboel gegevens te verplaatsen om een ​​open slot te creëren. Gekoppelde lijsten zorgen voor een gemakkelijke manipulatie van opeenvolgende datasets, zonder een enorme belasting van de geheugenbronnen.

De meeste computerwetenschappelijke programma’s blijven studenten leren hoe ze gekoppelde lijsten kunnen implementeren, als een solide introductie tot dynamische gegevensstructuren die u misschien in echte programma’s wilt gebruiken. En zelfs als u nooit een gekoppelde lijst gebruikt, krijgt u voldoende inzicht om verwijzingen te gebruiken. U zult zeker veel aanwijzers gebruiken in veel van uw echte programma’s.

Nadelen van gekoppelde lijst

Gekoppelde lijsten zijn geweldig voor het maken van een eenvoudig te wijzigen lijst. Ze zijn echter niet de perfecte oplossing voor elk programma, zoals je hieronder zult zien:

  1. Gelinkte lijsten bieden geen willekeurig toegangspunt. Om een ​​bepaald item in uw lijst te bereiken, moet u tot dat moment elk item in de lijst herhalen.
  2. De code kan een beetje ingewikkeld worden omdat zowel dynamische geheugentoewijzing als pointers nodig zijn om de code te laten werken.
  3. De totale overhead voor een gekoppelde lijst kan hoger zijn dan een array, omdat de lijsten dynamisch worden toegewezen.

Dat gezegd hebbende, als u weet hoe u gekoppelde lijsten moet gebruiken, kunt u het gebruik van verwijzingen onder de knie krijgen en een beter begrip krijgen van dynamische gegevenssets als geheel.

Tutorial voor gekoppelde lijsten

Hieronder leert u hoe u een eenvoudige gelinkte lijst maakt en implementeert. We beginnen met het maken van een enkele gekoppelde lijst en dit zijn knooppunten en laten zien hoe u nieuwe knooppunten verwijdert en invoegt.

Een knooppuntstructuur maken

Een gekoppelde lijst bestaat uit verschillende knooppunten, dus we moeten een structuur maken die een knooppunt definieert. Dit moet ten minste één variabele voor gegevens bevatten en één aanwijzer om naar het volgende knooppunt te verwijzen. Voor ons doel houden we vast aan ons voorbeeld van de typesnelheid en gebruiken we de naam en snelheid van de persoon en onze gegevens. In C zouden de gegevens als volgt in een structuur worden gedefinieerd:

struct knooppunt {
string naam [32];
int snelheid;
struct node * volgende;
}

Het belangrijkste hier is de volgende aanwijzer, waarmee we ons een weg door de lijst kunnen banen.

Een gekoppelde lijst maken

Nu moeten we een lijst maken, die eigenlijk alleen het eerste knooppunt maakt. Dus we definiëren het, wijzen voldoende geheugen toe voor een enkel knooppunt en zetten de volgende aanwijzer op NULL zodat we weten dat dit het einde van de lijst is. Je stelt er ook de head pointer op in, want hier begint de gekoppelde lijst.

Vervolgens kunt u de informatie voor dit knooppunt invullen: de naam van de werknemer en hun typsnelheid.

Een knooppunt invoegen

Nu onze basislijst is gemaakt, kunnen we beginnen met het toevoegen van elementen aan de lijst. Stel dat je bent begonnen met Karen, die een typsnelheid heeft van 58 woorden per minuut. Vervolgens wil je Steve invoeren met een snelheid van 63. Je zou een knooppunt voor hem maken en de gegevens invullen. Vervolgens zou u de gekoppelde lijst doorzoeken, maar in dit geval zou er maar één element zijn. Je zou merken dat Steve een hogere typsnelheid heeft, dus je zou zijn volgende aanwijzer instellen op Karen’s aanwijzer. Aangezien de aanwijzer van Karen ook de aanwijzer van het hoofd is, zou je het hoofd naar het knooppunt van Steve wijzen.

Nu heb je de gekoppelde lijst die begint met het knooppunt van Steve. Het volgende zou verwijzen naar het knooppunt van Karen. En Karen’s knooppunt zou naar NULL wijzen, wat aangeeft dat haar knooppunt het laatste in de lijst is.

Als een werknemer zou worden aangenomen met een typsnelheid tussen Karen en Steve, zou er een knooppunt voor hen worden gecreëerd. Maar dan zou de volgende van Steve naar de nieuwe werknemer wijzen en die van de nieuwe werknemer zou naar die van Karen wijzen.

Aan de andere kant, als een werknemer zou worden aangenomen met een typsnelheid die lager is dan die van Karen, zou er opnieuw een knooppunt voor hen worden gecreëerd. Maar dan zou de volgende van Karen naar de nieuwe werknemer wijzen en de volgende van de nieuwe werknemer zou naar NULL wijzen.

Een knooppunt verwijderen

Het verwijderen van een knooppunt uit een gekoppelde lijst is eigenlijk een vrij eenvoudig proces. We zouden de volgende aanwijzer van de werknemer vóór de werknemer die we willen verwijderen, wijzen naar de werknemer na de werknemer die we willen verwijderen. We zouden dan het geheugen van het verwijderde knooppunt vrijgeven of we zouden een geheugenlek krijgen.

Je kunt natuurlijk nog veel meer doen met gekoppelde lijsten. Als u geïnteresseerd bent in het nog verder verkennen van gekoppelde lijsten, bekijk dan de hieronder gemarkeerde bronnen.

Bronnen voor gekoppelde lijsten

Zodra u het basisconcept van gekoppelde lijsten begrijpt, is het tijd om uw kennis te vergroten. Hieronder bieden we een paar extra bronnen om te helpen bij het echt beheersen van gekoppelde lijsten en om een ​​dieper begrip van gegevensstructuren te krijgen:

  • Data Structures and Algorithms Made Easy (2016) van Narasimha Karumanchi: een geweldig boek over datastructuren dat je veel verder brengt dan gekoppelde lijsten.
  • Basisbeginselen van gekoppelde lijsten (pdf): deze pdf van 26 pagina’s biedt u alles wat u maar wilt weten met pseudo-code en voorbeelden van C-talen.
  • Een zachte introductie tot gegevensstructuren: deze eenvoudige introductie leidt u helemaal door het maken van uw eerste gelinkte lijstprogramma.
  • Tutorials met gekoppelde lijsten: dit is een verzameling van 7 korte video’s over het maken van gekoppelde lijsten in C++.
  • Learn-C.org Gekoppelde lijsten Pagina: deze pagina begeleidt u bij het maken van een eenvoudige C-taal gekoppelde lijst.
  • Gegevensstructuren met Javascript: leer gekoppelde lijsten rechtstreeks in uw browser met deze JavaScript-zelfstudie.

Overzicht

Gekoppelde lijsten bieden een geweldig concept en praktische methode voor het beheren en maken van dynamische gegevenssets. Hopelijk heeft de bovenstaande informatie u geholpen bij het begrijpen en implementeren van een eenvoudige gelinkte lijst, en u zult verder gaan.

Jeffrey Wilson Administrator
Sorry! The Author has not filled his profile.
follow me