Eine Einführung in die Verwendung von verknüpften Listen in Java

Eine Datenstruktur verwendet verschiedene vordefinierte Methoden zum Speichern, Abrufen und Löschen von Daten, die in der Erstellung effizienter Programme gipfeln. Eine verknüpfte Liste ist eine beliebte Datenstruktur, die aus einer Liste von Knoten besteht, die verbunden (oder verknüpft) sind.

Aber wie erstellt man eine verknüpfte Liste in Java? Lass uns mal sehen.

Jede verkettete Liste beginnt mit einem speziellen Knoten, der oft als "Kopf" bezeichnet wird und der dafür verantwortlich ist, jederzeit auf den Anfang der Liste zu zeigen. Der Kopf ist wichtig, da nicht jeder Knoten in einer verketteten Liste seinem Nachfolger physisch folgen muss (d. h. ein Vorgänger und ein Nachfolger müssen nicht physisch benachbart sein).

Wie jede Datenstruktur erleichtert die verknüpfte Liste das Erstellen, Abrufen, Einfügen und Vernichten durch eine Reihe vordefinierter Funktionen, die von jedem Entwickler verwendet werden können.

Ein Java-Programm, das zum Erstellen und Bearbeiten von verknüpften Listen entwickelt wurde, hat drei unterschiedliche Abschnitte; die Knotenklasse, die verknüpfte Listenklasse und den Treiber. Obwohl diese drei Abschnitte in einer Datei kombiniert werden können, gibt es in der Informatik ein Designprinzip, das als "Trennung von Bedenken" bekannt ist und das jeder Entwickler kennen sollte.

Das Prinzip der Trennung von Anliegen schreibt vor, dass jeder Abschnitt des Kodex, der ein bestimmtes Anliegen anspricht, getrennt werden sollte. Dieses Prinzip hilft Ihnen, saubereren (leserlichen) Code zu erstellen und ist ideal zum Erstellen von Datenstrukturen.

Der erste Schritt beim Erstellen einer verknüpften Liste in Java besteht darin, eine Knotenklasse zu erstellen. Eine Knotenklasse sollte zwei Attribute haben; eines der Attribute stellt den Datenteil des Knotens dar, während das andere Attribut den verknüpften Teil darstellt. Eine Knotenklasse sollte auch einen Konstruktor, Getter und Setter haben.

Verwandt: Erfahren Sie, wie Sie Klassen in Java erstellen

Die Getter und Setter erlauben anderen Klassen (wie der Linked-List-Klasse) den Zugriff auf die verschiedenen Knoten innerhalb der Linked-List.

Beispiel für eine Knotenklasse

Nachfolgend finden Sie ein Beispiel für eine Knotenklasse, damit Sie eine Vorstellung davon bekommen, was wir meinen:

Knoten der öffentlichen Klasse {
private int-Daten;
privater Knoten NextNode;
//constructor
öffentlicher Knoten() {
Daten = 0;
NextNode = null;
}
//Getter und Setter
public int getData() {
Daten zurückgeben;
}
public void setData (int data) {
Daten = Daten;
}
öffentlicher Knoten getNextNode() {
NextNode zurückgeben;
}
public void setNextNode (Knoten nextNode) {
NextNode = nextNode;
}
}

In diesem Beispiel speichert das Datenattribut ganzzahlige Werte. Da Sie nun über die Knotenklasse verfügen, ist es an der Zeit, zur verknüpften Liste überzugehen.

Unten ist ein Beispiel für eine verknüpfte Liste in Java.

öffentliche Klasse LinkedList {
privater Knotenkopf;
//constructor
öffentliche LinkedList() {
Kopf = null;
}
}

Der obige Code erstellt eine Linked-List-Klasse, jedoch kann die Klasse ohne ihre verschiedenen Operationen als das Äquivalent einer leeren Shell angesehen werden. Die Datenstruktur der verknüpften Liste verfügt über mehrere Operationen, mit denen sie gefüllt werden kann:

• Vorne einsetzen.
• In der Mitte einsetzen.
• Hinten einsetzen.

Verwandt: So erstellen Sie Datenstrukturen mit JavaScript ES6-Klassen

Die Linked-List-Sammlung von Einfügemethoden ist ein Grund, warum ein Entwickler diese Daten verwenden könnte Struktur über eine andere Datenstruktur wie Stacks (die nur das Einfügen und Löschen von oben zulässt).

Verwenden der Insert-an-the-Front-Methode

Die Methode Insert at the front fügt, wie der Name schon sagt, neue Daten (oder neue Knoten) am Anfang der verknüpften Liste ein.

Einfügen an der Vorderseite Methodenbeispiel

Unten sehen Sie ein Beispiel dafür, wie Sie neue Daten am Anfang Ihrer Liste einfügen würden.

 //Knoten an Front-Methode einfügen
public void insertAtFront (int-Schlüssel) {
//Erzeuge einen neuen Knoten mit der Knotenklasse
Knotentemp = neuer Knoten();
//überprüfe, ob der Temp-Knoten erfolgreich erstellt wurde
// ihm die vom Benutzer bereitgestellten Daten zuordnen
if (Temp != null) {
Temp.setData (Schlüssel);
Temp.setNextNode (null);
//überprüfe ob der Kopf der verlinkten Liste leer ist
// Weisen Sie den soeben erstellten Knoten der Kopfposition zu
if (Kopf == null) {
Kopf = Temperatur;
}
//wenn sich ein Knoten bereits an der Kopfposition befindet
// füge den neuen Knoten hinzu und setze ihn als Kopf
anders {
Temp.setNextNode (Kopf);
Kopf = Temperatur;
}
}
}

Das einfügenAtFront -Methode im obigen Beispiel ermöglicht es einem Benutzer, einer gegebenen verknüpften Liste neue Knoten hinzuzufügen.

Anwenden des Einsatzes an der Vorderseite Beispiel

Unten sehen Sie ein Beispiel dafür, wie Sie die Einlage vorne anbringen würden.

Fahrer der öffentlichen Klasse {
// führt das Programm aus
public static void main (String[] args) {
//Erstelle eine neue verknüpfte Liste namens List
LinkedList-Liste = new LinkedList();
// Füge jeden Wert als neuen Knoten an den Anfang der verknüpften Liste
List.insertAtFront (10);
List.insertAtFront (8);
List.insertAtFront (6);
List.insertAtFront (4);
List.insertAtFront (2);
}
}

Das Treiber class (das ist der Name, der in Java oft der ausführbaren Klasse zugewiesen wird) verwendet die LinkedList-Klasse, um eine verknüpfte Liste mit fünf geraden Zahlen zu erstellen. Wenn man sich den obigen Code ansieht, sollte es leicht zu erkennen sein, dass die Zahl "2" an der Kopfposition in der verknüpften Liste steht. Aber wie kann man das bestätigen?

Verwenden der Methode Alle Knoten anzeigen

Die Methode zum Anzeigen aller Knoten ist eine wesentliche Methode der verketteten Liste. Ohne sie kann ein Entwickler die Knoten in einer verknüpften Liste nicht sehen. Es durchläuft die verknüpfte Liste (beginnend mit dem Kopf) und druckt die Daten, die in jedem Knoten gespeichert sind, der die Liste bildet.

Beispiel für eine Methode zum Anzeigen aller Knoten

Unten sehen Sie ein Beispiel für die Verwendung der Methode Alle Notizen anzeigen in Java.

//alle Knoten anzeigen Methode
public void displayAllNodes() {
//Erzeuge einen neuen Knoten, rufe Temp auf und weise ihn dem Kopf der verknüpften Liste zu
// Wenn der Kopf einen Nullwert hat, ist die verknüpfte Liste leer
Knotentemperatur = Kopf;
wenn (Kopf == null){
System.out.println("Die Liste ist leer.");
Rückkehr;
}
System.out.println("Die Liste:");
while (Temp != null) {
// die Daten in jedem Knoten an die Konsole ausgeben (beginnend mit dem Kopf)
System.out.print (Temp.getData() + " ");
Temp = Temp.getNextNode();
} 
}

Jetzt, da die displayAllNodes Methode wurde hinzugefügt LinkedList -Klasse können Sie die verknüpfte Liste anzeigen, indem Sie der Treiberklasse eine einzelne Codezeile hinzufügen.

Verwenden des Methodenbeispiels „Alle Knoten anzeigen“

Unten sehen Sie, wie Sie die Methode zum Anzeigen aller Knoten verwenden.

//die Knoten in einer verknüpften Liste drucken
List.displayAllNodes(); 

Die Ausführung der obigen Codezeile erzeugt die folgende Ausgabe in der Konsole:

Die Liste:

2 4 6 8 10

Verwenden der Find Node-Methode

Es wird Fälle geben, in denen ein Benutzer einen bestimmten Knoten in einer verknüpften Liste finden möchte.

Es wäre beispielsweise für eine Bank mit Millionen von Kunden nicht praktikabel, alle Kunden in ihrer Datenbank auszudrucken, wenn sie nur die Details eines bestimmten Kunden sehen müssen.

Anstatt die displayAllNodes -Methode ist es effizienter, den einzelnen Knoten zu finden, der die erforderlichen Daten enthält. Aus diesem Grund ist die Suche nach einer Single-Node-Methode in der Linked-List-Datenstruktur wichtig.

Beispiel für eine Methode zum Suchen von Knoten

Unten sehen Sie ein Beispiel für die Verwendung der Find-Node-Methode.

//Suche nach einem einzelnen Knoten mit einem Schlüssel
public boolescher findNode (int-Schlüssel) {
//Erzeuge einen neuen Knoten und platziere ihn an den Anfang der verknüpften Liste
Knotentemperatur = Kopf;
// solange der aktuelle Knoten nicht leer ist
//überprüfe, ob seine Daten mit dem vom Benutzer bereitgestellten Schlüssel übereinstimmen
while (Temp != null) {
if (Temp.getData() == Schlüssel) {
System.out.println("Der Knoten ist in der Liste"); 
true zurückgeben;
}
//zum nächsten Knoten gehen
Temp = Temp.getNextNode();
}
//wenn der Schlüssel nicht in der verlinkten Liste gefunden wurde
System.out.println("Der Knoten ist nicht in der Liste"); 
falsch zurückgeben;
}

Mit dem displayAllNodes Methode haben Sie bestätigt, dass die LinkedList enthält 5 gerade Zahlen von 2 bis 10. Das findNode Das obige Beispiel kann bestätigen, ob eine dieser geraden Zahlen die Zahl 4 ist, indem einfach die Methode in der Treiberklasse aufgerufen und die Zahl als Parameter bereitgestellt wird.

Verwenden des Beispiels für die Find Node-Methode

Unten finden Sie ein Beispiel dafür, wie Sie die Find-Node-Methode in der Praxis verwenden würden.

//überprüfe, ob ein Knoten in der verknüpften Liste enthalten ist
List.findNode (4);

Der obige Code erzeugt die folgende Ausgabe in der Konsole:

Der Knoten ist in der Liste

Verwenden der Methode zum Löschen eines Knotens

Anhand des gleichen Bankbeispiels von oben möchte ein Kunde in der Datenbank der Bank möglicherweise sein Konto schließen. Hier ist die Methode zum Löschen eines Knotens nützlich. Es ist die komplexeste Linked-List-Methode.

Die Methode "Knoten löschen" sucht nach einem bestimmten Knoten, löscht diesen Knoten und verknüpft den vorherigen Knoten mit dem, der dem gelöschten Knoten folgt.

Beispiel einer Knotenmethode löschen

Unten sehen Sie ein Beispiel für die Methode zum Löschen eines Knotens.

public void findAndDelete (int-Schlüssel) { 
Knotentemperatur = Kopf; 
Knoten prev = null; 
//überprüfe, ob der Kopfknoten die Daten enthält 
//und löschen 
if (Temp != null && Temp.getData() == Schlüssel) { 
Kopf = Temp.getNextNode(); 
Rückkehr; 
} 
//die anderen Knoten in der Liste durchsuchen 
//und löschen 
while (Temp != null) { 
if (Temp.getNextNode().getData() == Schlüssel) { 
prev = Temp.getNextNode().getNextNode(); 
Temp.setNextNode (zurück); 
Rückkehr; 
} 
Temp = Temp.getNextNode(); 
} 
} 

Verwenden des Methodenbeispiels zum Löschen eines Knotens

Nachfolgend finden Sie ein Beispiel für die praktische Anwendung der Methode zum Löschen eines Knotens.

// den Knoten löschen, der die Daten enthält 4
List.findAndDelete (4);
//alle Knoten in der verknüpften Liste drucken
List.displayAllNodes();

Die Verwendung der beiden obigen Codezeilen in der bereits vorhandenen Driver-Klasse erzeugt die folgende Ausgabe in der Konsole:

Die Liste:
2 6 8 10

Wenn Sie es bis zum Ende dieses Tutorial-Artikels geschafft haben, haben Sie Folgendes gelernt:

• So erstellen Sie eine Knotenklasse.
• So erstellen Sie eine verknüpfte Listenklasse.
• So füllen Sie eine verknüpfte Listenklasse mit ihren vordefinierten Methoden.
• So erstellen Sie eine Treiberklasse und verwenden die verschiedenen verknüpften Listenmethoden, um das gewünschte Ergebnis zu erzielen.

Eine verknüpfte Liste ist nur eine von vielen Datenstrukturen, die Sie zum Speichern, Abrufen und Löschen von Daten verwenden können. Da Sie alles haben, was Sie für den Einstieg benötigen, probieren Sie diese Beispiele selbst in Java aus.

Erstellen und Ausführen von Operationen auf Arrays in Java

Java lernen? Lassen Sie Arrays Ihre Daten problemlos verarbeiten.

Weiter lesen

Über den Autor