Een inleiding tot het gebruik van gelinkte lijsten in Java

Een gegevensstructuur gebruikt verschillende vooraf gedefinieerde methoden om gegevens op te slaan, op te halen en te verwijderen, wat culmineert in het creëren van efficiënte programma's. Een gekoppelde lijst is een populaire gegevensstructuur, die bestaat uit een lijst van knooppunten die zijn verbonden (of gekoppeld).

Maar hoe maak je een gekoppelde lijst in Java? Laten we kijken.

Elke gekoppelde lijst begint met een speciaal knooppunt dat vaak wordt aangeduid als de "kop", die de verantwoordelijkheid heeft om te allen tijde naar het begin van de lijst te verwijzen. De kop is belangrijk omdat elk knooppunt in een gekoppelde lijst zijn opvolger niet fysiek hoeft te volgen (wat betekent dat een voorganger en een opvolger niet fysiek aangrenzend hoeven te zijn).

Zoals elke gegevensstructuur, vergemakkelijkt de gekoppelde lijst het maken, ophalen, invoegen en vernietigen door middel van een reeks vooraf gedefinieerde functies die door elke ontwikkelaar kunnen worden gebruikt.

Een Java-programma dat is ontworpen om gekoppelde lijsten te maken en te manipuleren, heeft drie onderscheidende secties; de knooppuntklasse, de gekoppelde lijstklasse en het stuurprogramma. Hoewel deze drie secties in één bestand kunnen worden gecombineerd, is er een ontwerpprincipe in de informatica dat bekend staat als 'scheiding van zorgen' dat elke ontwikkelaar zou moeten kennen.

Het principe van de scheiding van zorgen dicteert dat elke sectie van de code die een specifiek probleem behandelt, moet worden gescheiden. Dit principe helpt je om schonere (leesbare) code te maken en is ideaal voor het maken van datastructuren.

De eerste stap bij het maken van een gekoppelde lijst in Java is het maken van een knooppuntklasse. Een knooppuntklasse moet twee attributen hebben; een van de attributen vertegenwoordigt het gegevensgedeelte van het knooppunt, terwijl het andere attribuut het gekoppelde gedeelte vertegenwoordigt. Een knooppuntklasse moet ook een constructor, getters en setters hebben.

Verwant: Leer hoe u klassen in Java kunt maken

De getters en setters zullen andere klassen (zoals de gekoppelde lijstklasse) toegang geven tot de verschillende knooppunten binnen de gekoppelde lijst.

Voorbeeld van knooppuntklasse

Hieronder vindt u een voorbeeld van een knooppuntklasse om een ​​idee te krijgen van wat we bedoelen:

openbare klasse Knooppunt {
privé int Gegevens;
privé Knooppunt Volgende Knooppunt;
//constructor
openbare Node() {
Gegevens = 0;
VolgendeNode = null;
}
//getters en setters
openbare int getData() {
gegevens retourneren;
}
public void setData (int data) {
Gegevens = gegevens;
}
openbare Node getNextNode() {
retourneer NextNode;
}
public void setNextNode (Node nextNode) {
NextNode = nextNode;
}
}

In dit voorbeeld slaat het data-attribuut gehele waarden op. Nu je de node-klasse hebt, is het tijd om verder te gaan naar de gekoppelde lijst.

Hieronder ziet u een voorbeeld van een gekoppelde lijst in Java.

openbare klasse LinkedList {
privé knooppunthoofd;
//constructor
openbare LinkedList() {
Hoofd = nul;
}
}

De bovenstaande code zal een gekoppelde lijstklasse maken, maar zonder de verschillende bewerkingen kan de klasse worden gezien als het equivalent van een lege shell. De gegevensstructuur van de gekoppelde lijst heeft verschillende bewerkingen die kunnen worden gebruikt om deze te vullen:

• Inzet aan de voorkant.
• In het midden invoegen.
• Invoegen aan de achterkant.

Verwant: Hoe gegevensstructuren te bouwen met JavaScript ES6-klassen

De gekoppelde lijstverzameling van invoegmethoden is een reden waarom een ​​ontwikkelaar ervoor zou kunnen kiezen om deze gegevens te gebruiken structuur over een andere gegevensstructuur, zoals stapels (waarbij alleen invoeging en verwijdering van bovenaf mogelijk is).

De methode Invoegen aan de voorkant gebruiken

De methode 'insert at the front' voegt, zoals de naam al doet vermoeden, nieuwe gegevens (of nieuwe knooppunten) aan de voorkant van de gekoppelde lijst in.

Invoegen aan de voorkant Methode Voorbeeld

Hieronder ziet u een voorbeeld van hoe u nieuwe gegevens vooraan uw lijst zou invoegen.

 //insert node at front methode
public void insertAtFront (int-sleutel) {
// maak een nieuw knooppunt met behulp van de knooppuntklasse
Knooppunt Temp = nieuw Knooppunt();
// controleer of het Temp-knooppunt met succes is gemaakt
// wijs de gegevens toe die door de gebruiker zijn verstrekt
if (Temp != null) {
Temp.setData (sleutel);
Temp.setNextNode (null);
// controleer of de kop van de gekoppelde lijst leeg is
// wijs het knooppunt dat zojuist is gemaakt toe aan de koppositie
if (Hoofd == null) {
Hoofd = Temp;
}
// als er al een knoop op de koppositie staat
// voeg het nieuwe knooppunt eraan toe en stel het in als het hoofd
anders {
Temp.setNextNode (Hoofd);
Hoofd = Temp;
}
}
}

De invoegenAtFront Met de methode in het bovenstaande voorbeeld kan een gebruiker nieuwe knooppunten toevoegen aan een bepaalde gekoppelde lijst.

Het inzetstuk aan de voorkant toepassen Voorbeeld

Hieronder ziet u een voorbeeld van hoe u inzet aan de voorzijde zou aanbrengen.

openbare klasse chauffeur {
//voert het programma uit
public static void main (String[] args) {
// maak een nieuwe gekoppelde lijst met de naam Lijst
LinkedList-lijst = nieuwe LinkedList();
// voeg elke waarde toe aan de voorkant van de gekoppelde lijst als een nieuw knooppunt
Lijst.insertAtFront (10);
Lijst.insertAtFront (8);
Lijst.insertAtFront (6);
Lijst.insertAtFront (4);
Lijst.insertAtFront (2);
}
}

De Bestuurder class (de naam die vaak wordt toegewezen aan de uitvoerbare klasse in Java), gebruikt de klasse LinkedList om een ​​gekoppelde lijst van vijf even getallen te maken. Als je naar de bovenstaande code kijkt, zou het gemakkelijk moeten zijn om te zien dat het nummer "2" op de koppositie in de gekoppelde lijst staat. Maar hoe kunt u dit bevestigen?

De methode Alle knooppunten weergeven gebruiken

De methode om alle knooppunten weer te geven is een essentiële gekoppelde lijstmethode. Zonder dit kan een ontwikkelaar de knooppunten in een gekoppelde lijst niet zien. Het reist door de gekoppelde lijst (beginnend bij de kop) en drukt de gegevens af die zijn opgeslagen in elk knooppunt dat de lijst vormt.

Voorbeeld van methode voor alle knooppunten weergeven

Hieronder ziet u een voorbeeld van het gebruik van de methode 'alle notities weergeven' in Java.

// toon alle knooppunten methode
public void displayAllNodes() {
// maak een nieuwe node-oproep Temp en wijs deze toe aan de kop van de gekoppelde lijst
// als de kop een null-waarde heeft, is de gekoppelde lijst leeg
Knooppunttemperatuur = Hoofd;
if (Hoofd == null){
System.out.println("De lijst is leeg.");
opbrengst;
}
System.out.println("De lijst:");
while (Temp != null) {
// print de gegevens in elk knooppunt naar de console (beginnend bij het hoofd)
System.out.print (Temp.getData() + " ");
Temp = Temp.getNextNode();
} 
}

Nu dat de toonAllNodes methode is toegevoegd aan de Gelinkte lijst klasse kunt u de gekoppelde lijst bekijken door een enkele regel code toe te voegen aan de chauffeursklasse.

Voorbeeld van de methode Toon alle knooppunten gebruiken

Hieronder ziet u hoe u de methode 'alle knooppunten weergeven' zou gebruiken.

// print de knooppunten in een gekoppelde lijst
Lijst.displayAllNodes(); 

Het uitvoeren van de bovenstaande regel code zal de volgende uitvoer in de console produceren:

De lijst:

2 4 6 8 10

De Find Node-methode gebruiken

Er zullen gevallen zijn waarin een gebruiker een specifiek knooppunt in een gekoppelde lijst wil vinden.

Het zou bijvoorbeeld niet praktisch zijn voor een bank met miljoenen klanten om alle klanten in hun database af te drukken wanneer ze alleen de details van een specifieke klant hoeven te zien.

Daarom, in plaats van het gebruik van de toonAllNodes methode, is een efficiëntere methode om het enkele knooppunt te vinden dat de vereiste gegevens bevat. Dit is de reden waarom het zoeken naar een methode met één knooppunt belangrijk is in de gegevensstructuur van de gekoppelde lijst.

Voorbeeld van knooppuntmethode zoeken

Hieronder ziet u een voorbeeld van het gebruik van de find node-methode.

// zoek naar een enkel knooppunt met behulp van een sleutel
public boolean findNode (int-sleutel) {
// maak een nieuw knooppunt en plaats het bovenaan de gekoppelde lijst
Knooppunttemperatuur = Hoofd;
// terwijl het huidige knooppunt niet leeg is
// controleer of de gegevens overeenkomen met de sleutel die door de gebruiker is verstrekt
while (Temp != null) {
if (Temp.getData() == sleutel) {
System.out.println("Het knooppunt staat in de lijst"); 
retourneer waar;
}
// ga naar het volgende knooppunt
Temp = Temp.getNextNode();
}
//als de sleutel niet werd gevonden in de gekoppelde lijst
System.out.println("Het knooppunt staat niet in de lijst"); 
onwaar retourneren;
}

Met de toonAllNodes methode, heb je bevestigd dat de Gelinkte lijst bevat 5 even getallen van 2 tot 10. De findNode Het bovenstaande voorbeeld kan bevestigen of een van die even getallen het cijfer 4 is door simpelweg de methode in de driverklasse aan te roepen en het getal als parameter op te geven.

Het voorbeeld van de Find Node-methode gebruiken

Hieronder ziet u een voorbeeld van hoe u de find node-methode in de praktijk zou gebruiken.

// controleer of een knooppunt in de gekoppelde lijst staat
Lijst.findNode (4);

De bovenstaande code produceert de volgende uitvoer in de console:

Het knooppunt staat in de lijst

De methode Een knooppunt verwijderen gebruiken

Met hetzelfde bankvoorbeeld van hierboven, zou een klant in de database van de bank zijn rekening willen sluiten. Dit is waar de methode delete a node nuttig zal zijn. Het is de meest complexe gekoppelde lijstmethode.

De methode Een knooppunt verwijderen zoekt naar een bepaald knooppunt, verwijdert dat knooppunt en koppelt het vorige knooppunt aan het knooppunt dat volgt op het verwijderde knooppunt.

Voorbeeld van een knooppuntmethode verwijderen

Hieronder ziet u een voorbeeld van de methode delete a node.

public void findAndDelete (int-toets) { 
Knooppunttemperatuur = Hoofd; 
Knooppunt vorig = null; 
// controleer of het hoofdknooppunt de gegevens bevat 
//en verwijder het 
if (Temp != null && Temp.getData() == sleutel) { 
Head = Temp.getNextNode(); 
opbrengst; 
} 
// zoek de andere knooppunten in de lijst 
//en verwijder het 
while (Temp != null) { 
if (Temp.getNextNode().getData() == sleutel) { 
prev = Temp.getNextNode().getNextNode(); 
Temp.setNextNode (vorige); 
opbrengst; 
} 
Temp = Temp.getNextNode(); 
} 
} 

Het voorbeeld van de methode Een knooppunt verwijderen gebruiken

Hieronder ziet u een voorbeeld van het gebruik van de methode delete a node in de praktijk.

// verwijder het knooppunt dat de gegevens bevat 4
Lijst.findAndDelete (4);
// print alle knooppunten in de gekoppelde lijst
Lijst.displayAllNodes();

Het gebruik van de twee coderegels hierboven in de reeds bestaande Driver-klasse zal de volgende uitvoer in de console produceren:

De lijst:
2 6 8 10

Als je het einde van dit zelfstudieartikel hebt gehaald, heb je het volgende geleerd:

• Hoe een node-klasse te maken.
• Een gekoppelde lijstklasse maken.
• Hoe een gekoppelde lijstklasse te vullen met zijn vooraf gedefinieerde methoden.
• Hoe u een chauffeursklasse maakt en de verschillende gekoppelde lijstmethoden gebruikt om het gewenste resultaat te bereiken.

Een gekoppelde lijst is slechts een van de vele datastructuren die u kunt gebruiken om gegevens op te slaan, op te halen en te verwijderen. Aangezien je alles hebt wat je nodig hebt om aan de slag te gaan, waarom probeer je deze voorbeelden dan niet zelf in Java?

Bewerkingen maken en uitvoeren op arrays in Java

Java leren? Laat arrays uw gegevens gemakkelijk verwerken.

Lees volgende

Over de auteur