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, weil nicht jeder Knoten in einer verknüpften Liste seinem Nachfolger physisch folgen muss (was bedeutet, dass ein Vorgänger und ein Nachfolger nicht physisch benachbart sein müssen).

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.

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

Verwandte: 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 Methode insertAtFront 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 Driver- Klasse (dies ist der Name, der der ausführbaren Klasse in Java oft zugewiesen wird) verwendet die LinkedList-Klasse, um eine verknüpfte Liste von 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.

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

Nachdem die Methode displayAllNodes der Klasse LinkedList hinzugefügt wurde, 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 Methode displayAllNodes zu verwenden, besteht daher eine effizientere Methode darin, 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 der Methode displayAllNodes haben Sie bestätigt, dass die LinkedList 5 gerade Zahlen von 2 bis 10 enthält. Das obige findNode- Beispiel kann bestätigen, ob eine dieser geraden Zahlen die Zahl 4 ist, indem Sie einfach die Methode in der Treiberklasse aufrufen und die Zahl als a . angeben Parameter.

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

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

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