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, was in der Erstellung effizienter Programme gipfelt. 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.

---

---

Wie funktioniert eine verlinkte Liste?

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.

Erstellen einer verknüpften Liste in Java

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:


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 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.

Beispiel für eine verknüpfte Liste

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

public class LinkedList {
private Node Head;
//constructor
public LinkedList() {
Head = 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 Auflistung von Einfügemethoden in verknüpften Listen ist ein Grund, warum ein Entwickler diese Datenstruktur möglicherweise einer anderen Datenstruktur wie Stapeln vorzieht (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.

//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;
}
}
}


Die 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.

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);
}
}


Die 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?

kabellose maus funktioniert nicht windows 10

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. Sie 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.

//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();
}
}

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.

//print the nodes in a linked list
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.

//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;
}

Mit dem displayAllNodes Methode haben Sie bestätigt, dass die LinkedList enthält 5 gerade Zahlen von 2 bis 10. Die 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.

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


Der obige Code erzeugt die folgende Ausgabe in der Konsole:

The node is in the list

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 Delete a Node sucht nach einem bestimmten Knoten, löscht diesen Knoten und verknüpft den vorherigen Knoten mit dem, der auf den 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 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();
}
}

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.

So verringern Sie die Dateigröße von JPEG

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

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

The List:
2 6 8 10

Jetzt können Sie verknüpfte Listen in Java erstellen

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.

Teilen Teilen Tweet Email Erstellen und Ausführen von Operationen auf Arrays in Java

Java lernen? Lassen Sie Arrays Ihre Daten problemlos verarbeiten.

Weiter lesen Verwandte Themen

• Programmierung
• Java
• Programmierung
• Codierungstipps

Über den Autor Kadeisha Kean(21 Artikel veröffentlicht)

Kadeisha Kean ist Full-Stack-Software-Entwicklerin und technische/Technologie-Autorin. Sie hat die ausgeprägte Fähigkeit, einige der komplexesten technologischen Konzepte zu vereinfachen; Herstellung von Material, das von jedem Technikneuling leicht verstanden werden kann. Sie schreibt leidenschaftlich gerne, entwickelt interessante Software und bereist die Welt (durch Dokumentationen).

Mehr von Kadeisha Kean

Abonniere unseren Newsletter

Abonnieren Sie unseren Newsletter für technische Tipps, Rezensionen, kostenlose E-Books und exklusive Angebote!

Klicken Sie hier, um zu abonnieren