Een inleiding tot het gebruik van gelinkte lijsten in Java

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.



Hoe werkt een gekoppelde lijst?

Elke gekoppelde lijst begint met een speciale knoop die 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 gekoppelde lijst maken in Java

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:


public class Node {
private int Data;
private Node NextNode;
//constructor
public Node() {
Data = 0;
NextNode = null;
}
//getters and setters
public int getData() {
return Data;
}
public void setData(int data) {
Data = data;
}
public Node getNextNode() {
return 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.

Voorbeeld van gekoppelde lijst

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

public class LinkedList {
private Node Head;
//constructor
public LinkedList() {
Head = null;
}
}

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 gegevensstructuur te gebruiken boven 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 method
public void insertAtFront(int key) {
//create a new node using the node class
Node Temp = new Node();
//check if the Temp node was successfully created
//assign the data that was provides by the user to it
if(Temp != null) {
Temp.setData(key);
Temp.setNextNode(null);

//check if the head of the linked list is empty
//assign the node that was just created to the head position
if(Head == null) {
Head = Temp;
}
//if a node is already at the head position
//add the new node to it and set it as the head
else {
Temp.setNextNode(Head);
Head = 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.

public class Driver {
//executes the program
public static void main(String[] args) {
//create a new linked list called List
LinkedList List = new LinkedList();
//add each value to the front of the linked list as a new node
List.insertAtFront(10);
List.insertAtFront(8);
List.insertAtFront(6);
List.insertAtFront(4);
List.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?

hoe het standaard gmail-account in chrome te wijzigen

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.

//display all nodes method
public void displayAllNodes() {
//create a new node call Temp and assign it to the head of the linked list
//if the head has a null value then the linked list is empty
Node Temp = Head;
if (Head == null){
System.out.println('The list is empty.');
return;
}
System.out.println('The List:');

while(Temp != null) {
//print the data in each node to the console(starting from the head)
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 the nodes in a linked list
List.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.

//search for a single node using a key
public boolean findNode(int key) {
//create a new node and place it at the head of the linked list
Node Temp = Head;
//while the current node is not empty
//check if its data matches the key provided by the user
while (Temp != null) {
if (Temp.getData() == key) {
System.out.println('The node is in the list');
return true;
}
//move to the next node
Temp = Temp.getNextNode();
}
//if the key was not found in the linked list
System.out.println('The node is not in the list');
return false;
}

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.

//check if a node is in the linked list
List.findNode(4);

De bovenstaande code produceert de volgende uitvoer in de console:

The node is in the list

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 key) {
Node Temp = Head;
Node prev = null;
//check if the head node holds the data
//and delete it
if (Temp != null && Temp.getData() == key) {
Head = Temp.getNextNode();
return;
}
//search the other nodes in the list
//and delete it
while (Temp != null) {
if (Temp.getNextNode().getData() == key ) {
prev = Temp.getNextNode().getNextNode();
Temp.setNextNode(prev);
return;
}
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.

hoe iemands webcamera te hacken
//delete the node that holds the data 4
List.findAndDelete(4);
//print all nodes in the linked list
List.displayAllNodes();

Als u de twee coderegels hierboven gebruikt in de reeds bestaande Driver-klasse, wordt de volgende uitvoer in de console geproduceerd:

The List:
2 6 8 10

Nu kunt u gelinkte lijsten maken in Java

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?

Deel Deel Tweeten E-mail Bewerkingen maken en uitvoeren op arrays in Java

Java leren? Laat arrays uw gegevens gemakkelijk verwerken.

Lees volgende Gerelateerde onderwerpen
  • Programmeren
  • Java
  • Programmeren
  • Codeertips
Over de auteur Kadeisha Kean(21 artikelen gepubliceerd)

Kadeisha Kean is een full-stack softwareontwikkelaar en technisch/technologisch schrijver. Ze heeft het onmiskenbare vermogen om enkele van de meest complexe technologische concepten te vereenvoudigen; materiaal produceren dat gemakkelijk kan worden begrepen door elke technologiebeginner. Ze is gepassioneerd door schrijven, interessante software ontwikkelen en de wereld rondreizen (via documentaires).

Meer van Kadeisha Kean

Abonneer op onze nieuwsbrief

Word lid van onze nieuwsbrief voor technische tips, recensies, gratis e-boeken en exclusieve deals!

Klik hier om je te abonneren